Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Induction on $n$. – Your Ad Here Feb 19 '14 at 15:20
up vote 4 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer

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.

share|cite|improve this 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.