# Fibonacci number Induction Proof

• Nov 17th 2009, 11:30 AM
Pi R Squared
Fibonacci number Induction Proof
Prove every third Fibonacci number is even.-- The Fibonacci numbers are the sequence 1,1,2,3,5,8,13,..., given by \$\displaystyle f_n\$ where \$\displaystyle f\$(1)=1, and \$\displaystyle f\$(2)=1, and \$\displaystyle f_(n)=f(n-1)+(n-2)(\$ for all \$\displaystyle n\$.

This is the problem...

This is what I have...
Base Case:
f(3k-2) if k=1 then f(3(1)-2)=f(1)=1 odd #
f(3k-1) f(3(1)-1)=f(2)=1 odd #
f(3k) f(3(1) =f(3)=2 even #

so f(1)+f(2)=f(3)
an odd+odd=even

Inductive step:

Suppose it is true for k+1
f(3(k+1)-2)=f(3k+1)
f(3(k+1)-1)=f(3k+2)
f(3(k+1)) =f(3K+3)

I do not know where to go from here...
• Nov 17th 2009, 03:09 PM
emakarov
First let me note that it's very good that you made your induction statement (let's call it \$\displaystyle P(k)\$) consist of three parts:

\$\displaystyle P(k)\$ is (\$\displaystyle f(3k-2)\$ is odd) and (\$\displaystyle f(3k-1)\$ is odd) and (\$\displaystyle f(3k)\$ is even)

The original assertion to prove (let's call it \$\displaystyle Q(k)\$) is just:

\$\displaystyle Q(k)\$ is (\$\displaystyle f(3k)\$ is even)

However, this is not enough to prove the induction step, which is the following statement:

for all \$\displaystyle k \ge 1\$, \$\displaystyle Q(k)\$ implies \$\displaystyle Q(k+1)\$

Knowing \$\displaystyle Q(k)\$ just is not enough to be able to prove \$\displaystyle Q(k+1)\$. Therefore, we strengthen the induction statement from \$\displaystyle Q(k)\$ to \$\displaystyle P(k)\$. Now, in proving that \$\displaystyle P(k)\$ implies \$\displaystyle P(k+1)\$, we have more to prove (three substatements of \$\displaystyle P(k+1)\$ instead of just one of \$\displaystyle Q(k+1)\$), but we also have a stronger assumption \$\displaystyle P(k)\$. This technique -- strengthening the induction statement in order for the induction step to go through -- is very common in mathematics.

End of a long digression. Concerning your proof, why do you say "Suppose it is true for k+1"? Inductive step is usually "suppose it is true for k; we need to prove it for k+1", i.e., one has to prove \$\displaystyle P(k)\$ implies \$\displaystyle P(k+1)\$ for all \$\displaystyle k\ge 1\$. So write carefully what you know, i.e., \$\displaystyle P(k)\$, and what you need to prove, i.e., \$\displaystyle P(k+1)\$, and the proof should be pretty straightforward.