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!!
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!!
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
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:
See here
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
$