In our notation we have that $F_{n-1}$ is the $n$th Fibonacci number since we start with $F_{0}=1$.
We want to prove that every third Fibonacci number is divisible by $F_{2}=2$.

The proof is the following using induction:
$F_{3n+2}=F_{3n}+F_{3n-1}+F_{3n-1}+F_{3n-2}$ (A)
$F_{3n+2}=F_{3n-1}+F_{3n-2}+F_{3n-1}+F_{3n-2}$ (B)
I don't understand how you go from step (A) to step (B) can anyone explain this to me?


There's a missing term in (B) as you noticed. A correct proof is by induction. Show that $F_2$ is even (immediate). Then write

$$ \begin{align} F_{3n+2} &= F_{3n+1} + F_{3n} \\ &= 2F_{3n} + F_{3n-1} \\ &= 2F_{3n} + F_{3(n-1)+2} \enspace, \end{align} $$

which is even because it's the sum of two even numbers. ($F_{3(n-1)+2}$ is even by the induction hypothesis.)


There is a well-known property of Fibonacci numbers: $$ \gcd(F_n,F_m)=F_{\gcd(n,m)} \tag{1} $$ Since $F_3=2$, $$ \gcd(F_{3n},2)=\gcd(F_{3n},F_3)=F_{\gcd(3,3n)} = F_3 = 2 \tag{2} $$ hence every Fibonacci number of the form $F_{3n}$ is even.


Base case:

$F_1=1\\ F_2=1\\ F_3=2$

Inductive hypothesis: Suppose $F_{3k-2}$ is odd, and $F_{3k-1}$ is odd, and $F_{3k}$ even.

We must show that $F_{3(k+1)-2}$ and $F_{3(k+1)-1}$ are odd, and $F_{3(k+1)}$ is even

$F_{3(k+1)-2} = F_{3k-1}+F_{3k}$

Based on the inductive hypothesis, $F_{3(k+1)-2}$ must be odd as the sum of an odd number and an even number are odd.

I will leave it to you to finish from here.


The rank of apparition of $2$, denoted $\omega(2)$, in the Fibonacci sequence is $3$; that is, the first term in the Fibonacci sequence that contains $2$ as a divisor is $F_{3} = 2$.

Since the Fibonnacci sequence is a member of the family of Lucas sequences, divisibility properties of the Lucas sequences are inherited by the Fibonacci sequence. Hence, $F_{3} | F_{k}$ if and only if $k = r\omega(2) = 3r$, for any positive integer $r$.

Therefore $2$ divides $F_{3}$ and every third term thereafter (and no others) in the Fibonacci sequence.


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.