Thread replies: 24
Thread images: 7
Thread images: 7
File: 2457245721.png (2KB, 105x29px) Image search:
[Google]
2KB, 105x29px
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
>>
>>8461534
Oh yeah sorry, forgot to mention that. It's with fibonacci numbers
>>
>>8461534
Its Fibonacci numbers.
>>8461521
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
>>
>>
>>8461544
>>8461539
Alright, then I'll have to move F(n-1) somehow right? Isn't my goal to make it match the original statement?
>>
>>8461556
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.
>>
>>8461566
Ill try working on it with this in mind.
How is it that I can substitute
F(n-1) with (3/2)^(n-2)?
>>
>>8461566
>>8461577
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
>>
>>8461577
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).
>>8461586
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
>>
>>8461594
Ah, that makes sense.
How do I have (3/2)^n-1 to start with? Is it the result of the first fraction reduced?
>>
>>8461610
Yes. (3/2)^n-1 is equal to (3^n-1)/(2^n-1)
>>
>>8461614
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) ....
>>
>>8461637
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.
>>
>>8461649
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
>>
>>8461671
forgot the extra parentheses, it's added now though
>>
>>8461671
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.
>>
>>8461679
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?
>>
>>8461693
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.
>>
>>8461696
You were really helpful. Thank you very much for the time
Thread posts: 24
Thread images: 7
Thread images: 7