# 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?

-
Induction on $n$. – Your Ad Here Feb 19 '14 at 15:20

Let us do an induction on $n$.

• Induction start. $f(1)=5=3\cdot 2-1$ and $f(2)=13=3\cdot 4+1$ (note that we really need the first two values in the induction start, because the recurrence uses the preceeding two values).

• Induction hypothesis. For some $n\ge 1$, we assume that we proved the formula for all $k\le n$.

• Induction step. We show that the formula then also holds for $n+1\ge 2$:

$$f(n+1)=2f(n-1)+f(n)=2\cdot (3\cdot 2^{n-1}+(-1)^{n-1})+3\cdot 2^n + (-1)^n=3\cdot 2^{n+1}+(-1)^{n+1}$$

-
That helped a lot! Thanks! – Brian Feb 19 '14 at 15:33
See my answer for a general view on why this works – Bill Dubuque Feb 19 '14 at 15:37

Hint: Try induction. Assume that the statement holds for $n$ and from that, prove it holds for $n+1$.

-

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.

-
I wish I had an upvote left for today. You always know how to surprise with a general perspective. – Your Ad Here Feb 19 '14 at 15:42