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