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)?
So my calculator came out with the left side. Can this just get reduced to 3/2+3/2? That wouldn't make much sense to me if that was the case
By doing the base case you prove that the formula holds for the the very first value. Before the induction step, you assume that the formula holds for all values between the base case (in this case 6) and n (6, 7, 8, .. n -1, n) so that you can prove it holds for n+1. Thus you know that it holds for F(n) and F(n-1) (because of your assumption that it is true).
What you have now is that (3/2)^(n-1) + some positive number (because (3/2)^(n-2) is positive for all n) is greater than (3/2)^(n-1) which is true.
you basically have to show that the rate of growth of Fibonacci numbers is higher than 3/2, which is true and easy to prove.( use the fact that Fibonacci numbers are strictly increasing after the first two terms)
show that F_n+1>3/2 F_n
Ah, that makes sense.
How do I have (3/2)^n-1 to start with? Is it the result of the first fraction reduced?
Yes. (3/2)^n-1 is equal to (3^n-1)/(2^n-1)
How do I know that (3/2)^(n-2) is positive for all n?
Does this prove it then? I'm still confused
F(n+2)=F(n+1) + F(n) >= (1+3/2) * (3/2)^(n-1)
= (10/4)(3/2)^(n-1) >= (9/4)(3/2)^(n-1) ....
I was looking at the wrong things so ignore that post I had above.
Now that you have the fractions, you can pull out (3/2)^n from both leaving you with (3/2)^n * ( (3/2)^-1 + (3/2)^-2) >= (3/2)^n.
This should be correct and true unless I'm going full retard right now.
This just seem to make it more complex to me, when the equation becomes even longer. I'm not sure how to conclude this proof
forgot the extra parentheses, it's added now though
The right hand side should be (3/2)^n. And from there you know that (3/2)^-1 + (3/2)^-2 is positive (you can find the exact value if you want) thus that positive number * (3/2)^n is greater than (3/2)^n.
I got confused because in some of your pictures the right hand side changed when it should just remain (3/2)^n as we are doing nothing to change it.
Ahh right, it's clearer now.
Yeah I know, I made mistakes in some of those pictures, which also confused me lol.
Though, doesn't the right hand side needs to be (3/2)^n-1 in the end, or doesn't it matter since
(3/2)^n > (3/2)^n-1?
Originally in the base case you proved F(n) >= (3/2)^n-1. After that you wanted to prove the n+1 case so F(n+1) >= (3/2)^n so the right hand side should be (3/2)^n. Anyways I have to go so good luck with figuring it out hopefully I was at least a little helpful.
You were really helpful. Thank you very much for the time