1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of Fibonacci sequence

  1. Apr 1, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove for k >= 0, r >= 2

    F_(k+r) = F_k * F_(r-2) + F_(k+1) * F_(r-1)

    2. Relevant equations

    I wonder if one should use induction ? If so, I don't know how to do it with two variables.

    If not, should I use the Fibonacci definition F_n = F_n-1 + F_n-2 in some way by substitution and renaming
    subindexes?

    3. The attempt at a solution

    Have only tried to substitute index like k + r = m, r-2 = m etc but no luck :(
     
  2. jcsd
  3. Apr 1, 2009 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    If you fix k then you can easily do induction on r, and that works out. So if you can also show that it holds for r = 2 for this fixed k, then you have your result (k being arbitrary).
     
  4. Apr 1, 2009 #3
    Ok cool, I solved it!

    Now my next problem is to prove F_2n = (F_n-1)^2 + (F_n)^2

    So I tried to set r = k in the previous identity but I didn't get a solution.

    Here's my attempt

    r = k

    F_2k = F_k * F_k-2 + F_k+1 * F_k-1

    = (F_k-1 + F_k-2) * F_k-2 + F_k+1 * F_k-1

    = F_k-1 * F_k-2 + (F_k-2)^2 + F_k+1 * F_k-1

    = F_k-1 * F_k-2 + (F_k-2)^2 + (F_k + F_k-1) * F_k-1

    = F_k-1 * F_k-2 + (F_k-2)^2 + F_k * F_k-1 + (F_k-1)^2

    = (F_k-2)^2 + F_k-1 * (F_k + F_k-2) + (F_k-1)^2

    = (F_k-2)^2 - (F_k-1)^2 + (F_k-1)^2 (attention " - " before the second term)

    = (F_k-2)^2 = (F_k + F_k-1)^2 = (F_k)^2 + 2F_k * F_k-1 + (F_k-1)^2

    So how do I get rid of th second term? ;)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof of Fibonacci sequence
  1. Fibonacci sequence (Replies: 5)

  2. Fibonacci Sequence (Replies: 8)

  3. Fibonacci Sequence (Replies: 13)

Loading...