Results 1 to 3 of 3

Thread: Need help on Fibonacci proof

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    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!
    Last edited by armeros; Apr 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 $\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$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    55
    Thanks
    1

    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: Feb 5th 2011, 02:47 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Nov 28th 2009, 10:21 PM
  3. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 2nd 2008, 05:12 PM
  4. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 26th 2007, 07:37 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum