# Prove by induction that numbers of Fibonacci of the form $F_{3n}$ are even

I am not quite asking to solve this problem, but I am asking what they are asking me. This is the problem:

The Fibonacci numbers $F_n$ for $n \in \mathbb{N}$ are defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n−2} + F_{n−1}$ for $n \geq 2$. Prove (by induction) that the numbers $F_{3n}$ are even for any $n \in \mathbb{N}$.

We all know what the Fibonacci numbers are, and I also know in general how proofs by induction work: assume for $n$ case, prove by $n + 1$ case. Very nice!

My problem is: what the heck are they asking me? What do you think they mean by $F_{3n}$? Are they maybe asking us to prove for the cases $3n$? For example, instead of for $n=1$ we prove for $n=3$, instead of $2$ we have $6$, and so on?

So, if my reasonings are correct, for example, the base case would be $n = 0$ and $n = 1$ as usual, but we then use the new formula $F_{3n}$.

Thus we would have to show $F_{3*0}=F_{0} = 0$ and $F_{3*1} = F_{3} = (F_{2} = 1 + F_{1} = 1) = 2$.

Well, we have show that they are even, so they are of the form $F_n = 2k$.

What exactly am I suppose to do?

• Yes it means show $F_3$ is even, $F_6$ is even, $F_9$ is even, $F_{12}$ is even, etc... – Gregory Grant Mar 27 '15 at 19:43
• – Martin Sleziak Apr 1 '15 at 11:22

A proof by induction could go more or less like this.

$F_1=1$, $F_2=1$, and $F_3=2$. So, $F_{3\cdot1}=2$ is even.

Assume that $F_{3n}$ is even.

Now, $F_{3n+3}=F_{3n+2}+F_{3n+1}=F_{3n+1}+F_{3n}+F_{3n+1}=2F_{3n+1}+F_{3n}$.

Since $F_{3n}$ is even and $2F_{3n+1}$ is also even we get $F_{3(n+1)}=F_{3n+3}$ is even because it is the sum of these two even numbers.

• Actually, I was not asking for the solution, but in case I am not able to do it, it could also be helpful. But until I don't try to do it by myself, I will not look at yours :D – nbro Mar 27 '15 at 19:59
• @Rinzler It will always be your choice to make. – Nathanson Mar 27 '15 at 20:02
• I think your proof cannot be correct. $F_{3n + 2}$ is not the previous element of the sequence of the type $F_{3n}$. The previous element is $F_{3(n - 1)}$. So, in the case of $F_{3(n+1)} = F_{3n + 3}$ the previous element of the sequence would be $F_{3n}$. Why did you do that? – nbro Mar 27 '15 at 21:16
• For example, if you have the index $12 = 3*4 = 3*(3 + 1) = 9 + 3 = 12$, but if you just remove $1$, you will have index $11$. Does not make sense, because the previous element is $F_9$ – nbro Mar 27 '15 at 21:23
• @Rinzler $F_{12}=F_{11}+F_{10}=F_{10}+F_9+F_{10}=2F_{10}+F_9$. $2F_{10}$ is even because it has a $2$ in front, and $F_9$ is even because it is the previous term that we know is even. – Nathanson Mar 27 '15 at 21:28

You can also do it in modulo 2. In this case every Fibbonaci number is 1 or 0.

Since in modulo 2 (1+1=0): So $$F_0=0$$, $$F_1=1$$, $$F_2=1$$, $$F_3=0$$,...

We know that some even Fibonacci number exists. By the Well Ordering Principle, every non-empty subset of the positive integers has a least element. Let $$F_k$$ be the smallest even Fibonacci number greater than zero.

Then $$F_k=0$$ for some $$k$$. Since it is the least even Fibonacci, $$F_{k-1}$$=1.

Given the above and by definition of the Fibonacci numbers, $$F_{k+1}=1, F_{k+2}=1,$$ and $$F_{k+3}=0$$, and is therefor even.

We have thus proven that if $$F_k=0, k>0$$, then $$F_{k+3}=0$$. This provides the induction step for all $$F_{3n}$$.