Results 1 to 3 of 3

Math Help - Fibonacci Numbers Proof

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    Fibonacci Numbers Proof

    Hey all, not sure how to proceed with the following proposition:

    For all k , m, in the Natural Numbers, where m >= 2,

    fib(m+k) = fib(m-1)*fib(k) + fib(m)*fib(k+1)

    Tried to fix m and do induction on k, leading to the base case:

    fib(m+1) = fib(m-1) + fib(m) which is correct by the definition of fibonacci numbers.

    Assume P(n) is true: fib(m+n) = fib(m-1)*fib(n) + fib(m)*fib(n+1)
    Now for the inductive step:

    fib(m+n+1) = fib(m-1)*fib(n+1) + fib(m)*fib(n+2)

    Tried plugging in from P(n) but that doesn't seem to be leading anywhere. I feel like we may need to use strong induction here but I'm not sure how. Any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    Re: Fibonacci Numbers Proof

    First I'd like to TeX this so that others can read what you wrote. (Please consider writing your problem in LaTeX next time.) You are trying to show that for all integers k,m (where m\geq 2), that

    F_{m+k}=F_{m-1}F_k+F_m F_{k+1}

    I think that using induction is a fine idea. The only slight change I would make is to use strong induction, where we assume that the formula works for 1,2,\ldots, k. The reason for this is that the Fibonnaci numbers are defined by the previous two terms in the sequence:

    F_{k+1}=F_{k}+F_{k-1}

    Weak induction would technically only allow us to say something about the F_k term, but not the other F_{k-1} term.

    Technical details aside, to complete the induction, you tried to show that the formula works for F_{m+k+1}, but got stuck. I recommend using that recursion relation above:

    F_{m+k+1}=F_{m+k}+F_{m+k-1}

    Now you have the induction assumption up to k so you could write F_{m+k} and F_{m+k-1} using the formula. Try it out and see where it goes. (I haven't actually carried it out myself, but I would expect it to work.) Let us know how it turns out.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Fibonacci Numbers Proof

    it does work.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof about Fibonacci and Lucas numbers (GCD)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2010, 09:26 AM
  2. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 06:28 AM
  3. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 16th 2009, 09:46 AM
  4. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 18th 2008, 11:33 PM
  5. Fibonacci Numbers - proof.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2007, 09:08 AM

Search Tags


/mathhelpforum @mathhelpforum