Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fibonacci Proof by Induction

  1. Apr 12, 2012 #1
    I've been having a lot of trouble with this proof lately:

    Prove that,


    Where the subscript denotes which Fibonacci number it is. I'm not sure how to prove this by straight induction so what I did was first prove that,


    And then used that in the other proof.

    For F[itex]_{2}[/itex]+F[itex]_{4}[/itex]+...+F[itex]_{2n}[/itex]=F[itex]_{2n+1}[/itex]-1

    For n=1 (base case)



    =F[itex]_{2k+5}[/itex]-1 = F[itex]_{2(k+2)+1}[/itex]-1

    Proving that F[itex]_{2k}[/itex]=F[itex]_{2k+1}[/itex]-1 for all k+1.

    Now my question is, would this be a valid method for the proof first stated:




    Then the equation becomes:


    Something doesn't sit right with me. I feel like this is incorrect. If it is, any and all help would be appreciated. Thank you.
  2. jcsd
  3. Apr 12, 2012 #2
    It's quite a cute proof by induction, actually, if you can prove (or already know) that [itex]\sum_{k=1}^n F_k^2 = F_n F_{n+1}[/itex].

    Let's assume [itex]F_1 = F_2 = 1[/itex] and [itex]F_{n+2} = F_{n+1} + F_n[/itex] for natural numbers n. Since the recursive relation refers to two lesser naturals, we should proceed with strong induction and two base cases.

    Hence, for n = 1 we have:
    [tex]\sum_{k=1}^{2} F_k F_{k+1} = F_1 F_2 + F_2 F_3 = 1 + 2 = 3 = 4 - 1 = 2^2 - 1 = F_3^2 - 1 = F_{2(1)+1}^2 - 1.[/tex]
    For n = 2 we have:
    [tex]\sum_{k=1}^{4} F_k F_{k+1} = 3 + F_3 F_4 + F_4 F_5 = 3 + 6 + 15 = 24 = 25 - 1 = 5^2 - 1 = F_5^2 - 1 = F_{2(2)+1}^2 - 1.[/tex]
    Now suppose that [itex]\sum_{k=1}^{2j} F_k F_{k+1} = F_{2j+1}^2 - 1[/itex] for all [itex]j < n[/itex]. We want to show it's true for n itself. Break up the sum into recognizable parts:
    [tex]\sum_{k=1}^{2n} F_k F_{k+1} = F_1 F_2 + \sum_{k=2}^{2n} F_k F_{k+1} = 1 + \sum_{k=2}^{2n} F_k (F_k + F_{k-1}) = 1 + \sum_{k=2}^{2n} F_k^2 + \sum_{k=2}^{2n} F_k F_{k-1}.[/tex]
    The middle sum is 1 less than the identity at the start of my post. Note that [itex]F_k[/itex] and [itex]F_{k-1}[/itex] commute (luckily!) and so that last sum looks familiar, almost. Write it out in full, cut out a slice to which the induction hypothesis applies, and then deal with the rest.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook