# Thread: Need help on Fibonacci proof

1. ## Need help on Fibonacci proof

Let Fn be the nth Fibonaaci number.

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

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

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

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

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

$\displaystyle F_(2n+1) = (F_n)^2 + (F_{n+1})^2$ and $\displaystyle 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 $\displaystyle F_n|F_{n\cdot 0}$

And then you prove that $\displaystyle F_{n}|F_{n\cdot{q}}$ for $\displaystyle q=0, 1, ..., m$ implies that $\displaystyle 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 $\displaystyle F = \left( {\begin{array}{*{20}c} 1 & 1 \\ 1 & 0 \\ \end{array} } \right)$ this matrix satisfies: $\displaystyle F^n = \left( {\begin{array}{*{20}c} {f_{n + 1} } & {f_n } \\ {f_n } & {f_{n - 1} } \\ \end{array} } \right)$ for all $\displaystyle n \in \mathbb{N}$ (if you define $\displaystyle f_{-1}$ to be 1) -this is an easy induction-

Now it is easy to see that: $\displaystyle f_n \cdot F + f_{n - 1} \cdot {\text{Id}}_{2 \times 2} = F^n$ (just use the definition of the Fibonacci Numbers) thus: $\displaystyle \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. $\displaystyle AB=BA$) , then we have: $\displaystyle \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: $\displaystyle 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: $\displaystyle 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 $\displaystyle f_n$ - since $\displaystyle f_0=0$ - $\displaystyle \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.