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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question about induction ?
  1. Induction question (Replies: 3)

  2. Induction question (Replies: 3)

  3. Induction Question (Replies: 4)

Loading...