Induction and the Fibonacci Sequence

[cragar]

Homework Statement

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

The Attempt at a Solution

But I am a little confused if i should add another term or just plug in k+1
so the Fibonacci sequence is F_{n}=F_{n-1}+F_{n-2}
so then should k+1 be F_{k+1}= F_{k}+F_{k-1}+F_{k-2}
or should it beF_{k+1}=F_{k}+F_{k-1}

 

[Dick]

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.

 

[cragar]

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 into all the terms?

 

[Dick]

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 into all the terms?

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??

 

[cragar]

ok so the Fibonacci sequence is
F_{n}= \frac{a^{n+1}-b^{n+1}}{w}
so F_n is the formula for the sequence and a,b,w are fixed numbers and n is any integer and I am trying to prove the sequence with induction only I am not sure where to put the n+1

 

[Dick]

ok so the Fibonacci sequence is
F_{n}= \frac{a^{n+1}-b^{n+1}}{w}
so F_n is the formula for the sequence and a,b,w are fixed numbers and n is any integer and I am trying to prove the sequence with induction only I am not sure where to put the n+1

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.