1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Fibonacci Proofs via Induction

  1. Feb 3, 2010 #1
    So I am looking at the following two proofs via induction, but I have not a single idea where to start.
    The First is:
    1. Suppose hat F1=1, F2=1, F3=2, F4=3, F5=5 where Fn is called a Fibonacci number and in general:
    Fn=Fn-1+Fn-2 for n>/= 3. Prove that:

    Secondly is:
    2. Prove that F1+F2+F5+...+F2n-1=F2n

    Any help. I am looking for a proof via induction with a base case and induction step.
  2. jcsd
  3. Feb 3, 2010 #2
    You could start by trying a base case. Let n=3. What can you conclude from this? Is the statement valid?
  4. Feb 3, 2010 #3
    The base case part I think is more straight foward, but when I try to see if this hold for some k+1, things start to get tricky...
  5. Feb 3, 2010 #4
    I find it easier to work in summation notation here to keep it neat.
    Take the sum from i=1 to n+1 of fi. You can take fn+1 out of the sum and then apply the induction hypothesis to the other term. Then use the recursion formula for the fibonacci sequence to simplify.
  6. Feb 3, 2010 #5
    So we I seperate out the summation and apply the induction hypothesis to the other side I get:
    [tex]\Sigma[/tex]Fj+Fk+Fk-1=(Fk+2 + Fk+1) -1
    So I basically want to move the Fk+1 from the RHS to the LHS, but I would have to subtract it, and that gets me nowhere...
  7. Feb 3, 2010 #6
    Simplify fn+1 + fn+2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook