# 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 $f_n$ where $f$(1)=1, and $f$(2)=1, and $f_(n)=f(n-1)+(n-2)($ for all $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 $P(k)$) consist of three parts:

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

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

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

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

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

Knowing $Q(k)$ just is not enough to be able to prove $Q(k+1)$. Therefore, we strengthen the induction statement from $Q(k)$ to $P(k)$. Now, in proving that $P(k)$ implies $P(k+1)$, we have more to prove (three substatements of $P(k+1)$ instead of just one of $Q(k+1)$), but we also have a stronger assumption $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 $P(k)$ implies $P(k+1)$ for all $k\ge 1$. So write carefully what you know, i.e., $P(k)$, and what you need to prove, i.e., $P(k+1)$, and the proof should be pretty straightforward.