Take the 2-minute tour ×
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.

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|improve this question
    
Induction on $n$. –  Your Ad Here Feb 19 at 15:20

3 Answers 3

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|improve this answer
    
That helped a lot! Thanks! –  Brian Feb 19 at 15:33
    
See my answer for a general view on why this works –  Bill Dubuque Feb 19 at 15:37

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

share|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|improve this answer
1  
I wish I had an upvote left for today. You always know how to surprise with a general perspective. –  Your Ad Here Feb 19 at 15:42

Your Answer

 
discard

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.