# Proof by induction involving fibonacci numbers

The Fibonacci numbers are defined as follows: $f_0=0$, $f_1=1$, and $f_n=f_{n−1}+f_{n−2}$ for $n≥2$. Prove each of the following three claims:

(i) For each $n≥0$, $f_{3n}$ is even.

(ii) For each $n≥0$, $f_{3n+1}$ is odd.

(iii) For each $n≥0$, $f_{3n+2}$ is odd.

Solution

(i) Base case: $n=0$, $f_{3(0)}=f_0=0$ (it is even)

(ii) Base case: $n=0$, $f_{3(0)+1}=f_1=1$ (it is odd)

(iii) Base case: $n=0$, $f_{3(0)+2}= f_1+f_0 = 1+0 =1$ (it is odd)

As you can see, I can only answer the base case. I don't even know where to start for the inductive step. For example, for (i), will I start the inductive step by showing it is true for $f_{3n-1}$ and show it is true for $f_{3n}$. And if so, how do I do that?

-
I have edited your question with MathJax. Please use MathJax for formatting Math next time. – shaurya gupta Feb 9 '14 at 12:05

Hint: odd+odd=even; odd+even=odd. You never get two evens in a row. Do induction on $n$ so that there are three cases for each $n$, and you have the base case. Assume the three cases for $n$, and show that they together imply the three cases for $n+1$.
Assume that $f(3n)$ is even, $f(3n+1)$ is odd, $f(3n+2)$ is odd. Then check the parity of $f(3(n+1))=f(3n+3)$, $f(3(n+1)+1)=f(3n+4)$ and $f(3(n+1)+2)=f(3n+5)$. – Mark Bennet Feb 9 '14 at 12:20