Results 1 to 3 of 3

Math Help - Need help on Fibonacci proof

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    50

    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!
    Last edited by armeros; April 23rd 2009 at 08:32 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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 <br />
F = \left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right)<br />
this matrix satisfies: <br />
F^n  = \left( {\begin{array}{*{20}c}<br />
   {f_{n + 1} } & {f_n }  \\<br />
   {f_n } & {f_{n - 1} }  \\<br /> <br />
 \end{array} } \right)<br />
for all <br />
n \in \mathbb{N}<br />
(if you define f_{-1} to be 1) -this is an easy induction-

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

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

    Thus: <br />
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} } <br />
and now read off the entries: <br />
f_{n \cdot m}  = \sum\limits_{k = 0}^m \binom{m}{k}{f_k  \cdot f_n ^k  \cdot f_{n - 1} ^{m - k} } <br />
which is a multiple of f_n - since f_0=0 - \square
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    50

    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.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 5th 2011, 02:47 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 28th 2009, 10:21 PM
  3. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2008, 05:12 PM
  4. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 26th 2007, 07:37 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum