3
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – nbro Mar 27 '15 at 19:59
  • $\begingroup$ @Rinzler It will always be your choice to make. $\endgroup$ – Nathanson Mar 27 '15 at 20:02
  • $\begingroup$ 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? $\endgroup$ – nbro Mar 27 '15 at 21:16
  • 1
    $\begingroup$ 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$ $\endgroup$ – nbro Mar 27 '15 at 21:23
  • 1
    $\begingroup$ @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. $\endgroup$ – Nathanson Mar 27 '15 at 21:28
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.