Solve the following recurrences using backward substitutions: $x(n) = 3x(n-1)$, for $n > 1$; $x(1) = 4$
Asked
Active
Viewed 80 times
2 Answers
1
HINT: Just start substituting:
$$\begin{align*} x(n)&=3x(n-1)\\ &=3\big(3x(n-2)\big)\\ &=3^2x(n-2)\\ &=3^2\big(3x(n-3)\big)\\ &=3^3x(n-3)\;, \end{align*}$$
and so on. In general, when you’ve worked back $k$ steps you’ll have $x(n)$ equal to some multiple of $x(n-k)$; what will that multiple be if the pattern holds up?
Now take $k=n-1$, and you’ll get a closed form for $x(n)$.
Brian M. Scott
- 616,228
-
I'm sorry I'm still confused. Would the multiple be 3^k? – zmart372 Mar 21 '16 at 21:40
-
@zmart372: Yes, it would. Each time you step back, you multiply by $3$, so when you’ve stepped back $k$ times (to reach $x(n-k)$), you’ve multiplied by $3$ $k$ times, or by $3^k$. – Brian M. Scott Mar 21 '16 at 21:41
-
Ok I got it, thank you very much! – zmart372 Mar 21 '16 at 21:49
-
@zmart372: You’re welcome! – Brian M. Scott Mar 21 '16 at 21:52
