# 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’…

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

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

Since $\displaystyle F_{0}=0$, it follows from (2) that $\displaystyle 2$ devides $\displaystyle 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
$\displaystyle \sum_{k=0}^{n} \binom {n}{k} \cdot F_{k}= F_{2n}$ (1)
See here

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

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

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

And it follows that we have: $\displaystyle \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 $\displaystyle f_{n \cdot m}$ is a multiple of $\displaystyle 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

$\displaystyle 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 $\displaystyle n$.

5. Alternatively, consider the Fibonacci sequence modulo 2.

The first few terms are

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

Can you spot a pattern and prove it?