<s>[INST] Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula. Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$
Basis:
$a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$
$a_2 = 2^2 + 1 = 4 + 1 = 5$ $\checkmark$
Inductive Hypothesis:
$a_k = 2^k + 1$ , where $n = k$ 
$a_k = 3a_{k-1} - 2a_{k-2}$
Inductive Step: 
$$\begin{align}
\ a_{k+1} & = 3a_k - 2a_{k-1} \\
& = 3(2^k + 1) - 2(2^{k-1} + 1) \\
& = \color{red}{6^k} + 3 - \color{red}{4^{k-1}} - 2 \\
& = \color{red}{6^k} - \color{red}{4^{k-1}} + 1
\end{align}$$
Now, the $ + 1$ looks very promising, but $6^k - 4^{k-1}$ makes me sick. Anyone have some good hints? That second recurrence ( $2a_{n-2}$ ) seems to be stumping me.
 [/INST] $$3\cdot 2^k - 2\cdot 2^{k-1}= 3\cdot 2^k -2^k=2^k(3-1)=2^k\cdot2=2^{k+1}$$
Notice that $$ 3\cdot 2^k = 2^k + 2^k + 2^k$$
While
$$ 6^k=(3 \cdot 2)^k=3^k\cdot 2^k=2^k + 2^k ....... + 2^k$$ 
The last line shows $2^k$ being added $3^k$. There is a way to show this better in latex (a bracket under the ellipses) but I don't know how.
</s>