# Thread: Need help on Fibonacci proof

1. ## Need help on Fibonacci proof

Let Fn be the nth Fibonaaci number.

Prove the for all $m$ and $n$,

If $m|n$, then $F_m|F_n$.

I have proved three previous results which might be useful in proving the above.

For all $m$>= 1 and all $n$ >= 0 $F_{m+n} = F_{m-1}F_n +F_mF_{n+1}$

For all $m$>=1 and all $n$ >=1, $F_{m+n} = F_{m+1}F_{n+1} - F_{m-1}F_{n-1}$

$F_(2n+1) = (F_n)^2 + (F_{n+1})^2$ and $F_{2n+2} = (F_{n+2})^2 - (F_n)^2$

Thank you very much!

2. You can use induction on the quotient, that is you prove the base case, that is $F_n|F_{n\cdot 0}$

And then you prove that $F_{n}|F_{n\cdot{q}}$ for $q=0, 1, ..., m$ implies that $F_{n}|F_{n\cdot{(m+1)}}$ (inductive step)

To prove this you will need the results you have proven.

Of course it may be done in other ways.

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

\end{array} } \right)
$
this matrix satisfies: $
F^n = \left( {\begin{array}{*{20}c}
{f_{n + 1} } & {f_n } \\
{f_n } & {f_{n - 1} } \\

\end{array} } \right)
$
for all $
n \in \mathbb{N}
$
(if you define $f_{-1}$ to be 1) -this is an easy induction-

Now it is easy to see that: $
f_n \cdot F + f_{n - 1} \cdot {\text{Id}}_{2 \times 2} = F^n
$
(just use the definition of the Fibonacci Numbers) thus: $
\left( {f_n \cdot F + f_{n - 1} \cdot {\text{Id}}_{2 \times 2} } \right)^m = F^{n \cdot m}
$

But note that if 2 matrixes commute (i.e. $AB=BA
$
) , then we have: $
\left( {A + B} \right)^m = \sum_{k=0}^m\binom{m}{k}\cdot{A^k}\cdot{B^{m-k}}
$
(The typical combinatorial proof of the Binomial Theorem)

Thus: $
F^{n \cdot m} = \left( {f_n \cdot F + f_{n - 1} \cdot {\text{Id}}_{2 \times 2} } \right)^m = \sum\limits_{k = 0}^m \binom{m}{k} {F^k \cdot f_n ^k \cdot f_{n - 1} ^{m - k} }
$
and now read off the entries: $
f_{n \cdot m} = \sum\limits_{k = 0}^m \binom{m}{k}{f_k \cdot f_n ^k \cdot f_{n - 1} ^{m - k} }
$
which is a multiple of $f_n$ - since $f_0=0$ - $\square$

3. ## Thanks!

Thank you very much. I was obsessed with varying both m and n, and then it was just too hard to deal with that case.