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