# Thread: [SOLVED] Fibonacci. Prove: If 3|n, then 2|Fn

1. ## [SOLVED] Fibonacci. Prove: If 3|n, then 2|Fn

Prove that if Fn is the "nth" Fibonacci number that if 3|n (3 divides n) then 2|Fn
(2 divides the nth Fibonacci number).

THIS PROBLEM HAS BEEN SOLVED.

THANKS TO ALL WHO HELPED!!

2. In…

http://mathworld.wolfram.com/FibonacciNumber.html

… you can find the following ‘finite sums’…

$\sum_{k=0}^{n} \binom {n}{k} \cdot F_{k}= F_{2n}$ (1)

$\sum_{k=0}^{n} \binom {n}{k} \cdot 2^{k}\cdot F_{k}= F_{3n}$ (2)

Since $F_{0}=0$, it follows from (2) that $2$ devides $F_{3n}$

Regards

3. Read this post here, it is even more general than what you need. (It uses the Euclidean Algorithm)

Proofs for the formulas that appear above in this thread:

Originally Posted by chisigma
$\sum_{k=0}^{n} \binom {n}{k} \cdot F_{k}= F_{2n}$ (1)
See here

Originally Posted by chisigma
$\sum_{k=0}^{n} \binom {n}{k} \cdot 2^{k}\cdot F_{k}= F_{3n}$ (2)
Simply consider $(2\cdot F+\text{Id})^n$. We have $2\cdot F+\text{Id}=F^3$, the rest follows like in the previous link.

(Again $F = \left( {\begin{array}{*{20}c}
1 & 1 \\
1 & 0 \\

\end{array} } \right)$
)

In fact this gets even more general since we have: $
f_{m } \cdot F + f_{m-1} \cdot {\rm{Id}} = F^m
$
(this may be proven by induction quite easily since
$
F^2 = F + {\rm{Id}}
$
) thus: $
\left( {f_{m } \cdot F + f_{m-1} \cdot {\rm{Id}}} \right)^n = F^{n \cdot m}
$

And it follows that we have: $
\sum\limits_{k = 0}^n {\binom{n}{k}\cdot f_{m } ^k\cdot f_k \cdot f_{m-1} ^{n - k} } =f_{n\cdot m}
$

From there check that $
f_{n \cdot m}
$
is a multiple of $
f_m
$

4. Originally Posted by MathGeezer
I'm stalled on writing a couple Fibonacci proofs for a paper I'm working on.

Specifically, if Fn is the "nth" Fibonacci number I need to prove:

1) That if 3|n (3 is a factor of n) then 2|Fn (2 is a factor of the nth Fibonacci number).
[snip]
Since

$F_{3n} = F_{3n-1} + F_{3n-2} = F_{3n-2} + F_{3n-3} + F_{3n-2} = 2 F_{3n-2} + F_{3n-3}$

the result follows easily by induction on $n$.

5. Alternatively, consider the Fibonacci sequence modulo 2.

The first few terms are

$1,1,0,1,1,0,1,1,0,\ldots$

Can you spot a pattern and prove it?