Need Help With Strong Induction 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*}$$

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