Hi, I have do a proof by induction and I just can't seem to get it. It's the induction step that's tricky.
Not sure on how to write equations here, so I have to prove that
[PIC], for every n = {6, 7, 8,...}
Basic step I guess is to show that F_n0 is true, which is F_6.
or
8 >= 7.59
Now for the induction step, where I assume that F(k) is true, but where do I start when I have to prove that it also counts for P(k+1)?
what is Fn tho
Oh yeah sorry, forgot to mention that. It's with fibonacci numbers
Its Fibonacci numbers.
You prove the base case where F(n) = 6 which you seem to have already done. Then you need to prove the F(n+1) case which is greater than or equal to (3/2) ^ (n)
You can break down F(n+1) to F(n) + f(n-1) because of the definition of Fibonacci numbers and you can use your assumption that the proof works for all 6,7,8,...,n to prove F(n+1)
Sorry I don't know latex hope this helps.
Start off by Substituting N+1 where N is into the equation. In this case, show that the equation with substitution > equation of just N. You have to manipulate the equation/function to show it has the function of the same form, just of [(N+1)-1]=N. In this case the last thing you show is the statement is true for the lowest N integer you consider, which makes it true for all N bigger than it.
I've gotten this far, only just reduced it a little. It's what I have to do next I don't really understand
Use the definition of Fibonacci numbers you posted in this.To break down F(n+1) to F(n) + F(n-1)
Alright, then I'll have to move F(n-1) somehow right? Isn't my goal to make it match the original statement?
Your goal with the induction step is to show that F(n+1) >= (3/2)^n.
This is generally done by changing things on the left side of the equation to match the right side of the equation. In this case after substituting F(n) + F(n-1) in for F(n+1), you use the fact that you proved the base case and are assuming the original formula holds for all 6, 7, 8, ... , n.
By doing this, you can substitute F(n) with (3/2)^(n-1) and F(n-1) with (3/2)^(n-2). And you do some algebra to show that this is less than or equal to (3/2)^n.
Ill try working on it with this in mind.
How is it that I can substitute
F(n-1) with (3/2)^(n-2)?