Solve the following recurrences using backward substitutions:

Question

Solve the following recurrences using backward substitutions: $x(n) = 3x(n-1)$, for $n > 1$; $x(1) = 4$

Answer 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)$.

Answer 2

try showing by induction that $x_n = 4\times3^{n-1}$