Results 1 to 6 of 6

Math Help - Strong induction on Fibonacci numbers

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    15

    Strong induction on Fibonacci numbers

    Hi,

    today I'm really stuck with strong inductions...

    Let F_n be the n^{th} Fibonacci number. Prove that for all m ≥ 1 and all n, F_{m+n} = F_{m-1} F_n + F_m F_{n+1}.

    Can someone help me with it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    769

    Response

    Recently got a book by Posamentier on Fibonacci numbers that I believe discusses strong induction on them. I'll look it up when I get home and let you know what I find out.

    Question for you. Have you tried Googling for an answer?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    15
    Quote Originally Posted by wonderboy1953 View Post
    Question for you. Have you tried Googling for an answer?
    Yes I tried but this particular proof is not explained. I can only find the strong induction proof of the fibonacci numbers defined as F_n = F_{n-1} + F_{n-2} with F_0 = 0 and F_1 = 1 with n \ge 2.

    Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by TheFangel View Post
    Hi,

    today I'm really stuck with strong inductions...

    Let F_n be the n^{th} Fibonacci number. Prove that for all m ≥ 1 and all n, F_{m+n} = F_{m-1} F_n + F_m F_{n+1}.

    Can someone help me with it?
    Hi The Fangel,

    P(k)

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

    P(k+1)

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

    Proof

    F_{k+1}=F_k+F_{k-1}\ \Rightarrow\ F_k=F_{k+1}-F_{k-1}

    and

    F_{k+2}=F_{k+1}+F_k\ \Rightarrow\ F_{k+1}=F_{k+2}-F_k

    then it follows

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

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

    =F_{m-1}F_{k+1}-F_{m-1}F_{k-1}+F_mF_{k+2}-F_mF_k+F_{m+k-1}

    =F_{m-1}F_{k+1}+F_mF_{k+2}+\left(F_{m+k-1}-F_mF_k-F_{m-1}F_{k-1}\right)

    as the part in brackets is zero based on P(k), then

    F_{m+k+1}=F_{m-1}F_{k+1}+F_mF_{k+2}+0
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    769

    Answer

    Looked it up in my book. Here's how it describes it (reworded of course):

    First it describes it as a lemma, which needs to be proven (using the statements for n = k - 1 and for n = k to prove the statement for n = k + 1 so you'll be needing two base cases instead of just one meaning we have to check for n = 1 and n = 2).

    When n = 1, we have to verify that . Now since , we must verify that which must be true since it's a defining relationship for the Fibonacci numbers.

    When n = 2, then we need to verify that . Now since and , then we need to verify that which is true based on the following:



    Next we assume the statement holds for n = k - 1 and n = k or

    and which is the
    induction hypothesis. From out of the next series of equations:


    =
    =
    =
    =
    =

    we have which is the statement for n = k + 1 which completes the proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2010
    Posts
    15
    Thank you very much to both of you!

    In the end I chose the one of wonderboy because it shows in a clearer way the strong induction mechanism, even though both are very valid.

    Thanks again for your time!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] induction problem with fibonacci numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 5th 2011, 09:00 PM
  2. Fibonacci numbers pattern--induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 8th 2009, 01:56 PM
  3. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  4. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 AM
  5. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 07:37 AM

Search Tags


/mathhelpforum @mathhelpforum