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?
Best Answer
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$.