Proof of closed form of recursively defined sequence Let $f:\mathbb{N} \rightarrow \mathbb{N}$ be defined by $f(1) = 5, f(2) = 13$, and for $n \ge 2, f(n) = 2f(n - 2) + f(n - 1)$. Prove that $f(n) = 3\cdot 2^n + (-1)^n$ for all $n \in N$
So far I've proved that $f(n)$ is true when $n = 1, 2$.
For $k \ge 3$, assume that $p(j)$ is true for all $j \in N, j < k$
Now I want to prove that $p(k)$ is true for all $k \in N$
How would I go about doing that?

Hint $\ $ Let $\,S g(n) = g(n\!+\!1)$ be the shift operator. $(S-2)(2^n) = 0 = (S+1)(-1^n)$ so their product $(S-2)(S+1) = S^2\!-S-2$ kills $\, f_n = c\,2^n + d (-1)^n\,$ for any $\,c,d\,$ independent of $\,n.$ Therefore we deduce $\, 0 = (S^2\!-S-2)f_n = f_{n+2} - f_{n} - 2f_n,\ $ i.e $\ f_{n+2} = f_{n+1} + 2 f_n.$
Remark $\ $ See this answer for another example and further explanation. This explains how the proof works in TooOldForMath's answer. 
