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: Question about induction ?

  1. Jul 22, 2011 #1
    1. The problem statement, all variables and given/known data
    If i want to use induction to prove the Fibonacci sequence I first check that 0 satisfies both sides of the equation. then i assume its true for n=k then show that it for works for n=k+1
    3. The attempt at a solution
    But im a little confused if i should add another term or just plug in k+1
    so the Fibonacci sequence is [itex] F_{n}=F_{n-1}+F_{n-2} [/itex]
    so then should k+1 be [itex] F_{k+1}= F_{k}+F_{k-1}+F_{k-2} [/itex]
    or should it be[itex] F_{k+1}=F_{k}+F_{k-1} [/itex]
     
  2. jcsd
  3. Jul 22, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Of course, you 'plug in' k+1. You don't add another term. It's not exactly clear what you are trying to prove here.
     
  4. Jul 22, 2011 #3
    ok for example if we have 1+2+3+4+...n= n(n+1)/2
    ow we assume its true for n=k and then plug in k=k+1 but on the left side we add the k+1 term to to previous sequence but on the right we plug in k+1
    so we get 1+2+3+4+....k+(k+1)=(k+1)(k+1+1)/2
    but with the Fibonacci sequence It seems a little strange to me
    do i just add the next term or plug k+1 in to all the terms?
     
  5. Jul 22, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    This all depends on what you are trying to prove. In this example, the left side is a sum, so sure, to go to the n+1 case you need to add a term. The right side is the formula for the sum, so to go to the n+1 case you change n to n+1. What exactly are you trying to prove about the Fibonacci sequence??
     
  6. Jul 22, 2011 #5
    ok so the Fibonacci sequence is
    [itex] F_{n}= \frac{a^{n+1}-b^{n+1}}{w} [/itex]
    so F_n is the formula for the sequence and a,b,w are fixed numbers and n is any integer and im trying to prove the sequence with induction only im not sure where to put the n+1
     
  7. Jul 22, 2011 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, so you are talking about an explicit formula for the Fibonacci sequence. You put x^(n+1) into the recurrence relation for the Fibonacci sequence. You'll get a quadatic formula for value of x which has two solutions, call them a and b. Find them. Then you know c*a^(n+1)+d*b^(n+1) also satisfies the recurrence relation for any c and d. Now use the initial conditions F_0=1 and F_1=1 to fix c and d. There's really no 'induction' in this derivation. I think it would be really awkward to try to show this by induction.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook