Proving the Recursion Formula for $(x_n)$ Using Strong Induction

[KOO]

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 = x_1$ TRUE
For $n = 2$, we have $2^2 + 3^1 = 7 = x_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*}$$

What Next?

 

[MarkFL]

Are you required to use induction, or did you choose to do so, because there is a much simpler way to derive the closed form for the recursion.

 

[KOO]

Are you required to use induction, or did you choose to do so, because there is a much simpler way to derive the closed form for the recursion.

We are required to use induction.

 

[MarkFL]

Okay as your next step, I would distribute on the right side, keeping in mind that $6=2\cdot3$.

 

[blue_raver22]

Next, we can simplify the expression by expanding the terms and combining like terms:

$$\begin{align*}
x_{k+1} &= 5\cdot 2^k + 5\cdot 3^{k-1} - 6\cdot 2^{k-1} - 6\cdot 3^{k-2}\\
&= 2\cdot 2^k + 3^{k} - 6\cdot 2^{k-1} - 2\cdot 3^{k-1} - 6\cdot 3^{k-2}\\
&= 2^{k+1} + 3^{k} - 3\cdot 2^{k} - 2\cdot 3^{k-1}\\
&= 2^{k+1} + 3^{k} - 3\cdot 2^{k} - 2\cdot 3^{k-1} + 2\cdot 2^{k} - 2\cdot 2^{k}\\
&= 2^{k+1} + 3^{k} - 2\cdot 2^{k} + 2\cdot 2^{k} - 2\cdot 3^{k} - 2\cdot 3^{k-1}\\
&= 2^{k+1} + 3^{k} - 2\cdot 3^{k}\\
&= 2^{k+1} + 3^{k+1-1}
\end{align*}$$

Therefore, we have shown that $x_{k+1} = 2^{k+1} + 3^{k}$, which completes the induction step. Thus, by strong induction, we can conclude that for all $n\in\Bbb N$, $x_n = 2^n + 3^{n-1}$. This proves the recursion formula for $(x_n)$.