4

Let $(X_n)$ be a sequence given by the following recursion formula:

$$X_1 = 3, X_2 = 7,\text{ and }X_{n+1} = 5X_n - 6X_{n-1}$$

Prove that for all $n\in\Bbb N$, $X_n = 2^n + 3^{n-1}$.

Attempt:

For $n = 1$, we have $2^1 + 3^0 = 3 = a_1$ TRUE
For $n = 2$, we have $2^2 + 3^1 = 7 = a_2$ TRUE

Assume $X_k = 2^k + 3^{k-1}$ for some $k\in\Bbb N$.

Now, for $n = k+1$:

$$\begin{align*} X_{k+1} &= 5X_k - 6X_{k-1}\\ &= 5\left(2^k + 3^{k-1}\right) - 6\left(2^{k-1} + 3^{k-2}\right) \end{align*}$$

Brian M. Scott
  • 616,228
user109886
  • 498
  • 1
  • 6
  • 12

1 Answers1

4

Yes, go on. Use $2^k=2\cdot 2^{k-1}$ and associate the terms: $$X_{k+1}=5\cdot(2^k+3^{k-1})\ -\ 6\cdot(2^{k-1}+3^{k-2}) = 2^{k-1}\cdot(10-6)+3^{k-2}\cdot(15-6)=\\ =4\cdot 2^{k-1}+9\cdot 3^{k-2}=2^{k+1}+3^k\,.$$

Berci
  • 90,745