Strong Induction with Fibonacci numbers

[gwial]

Homework Statement

Use strong mathematical induction to prove that the Fibonacci numbers satisfy the inequality fn > (√2)n

Homework Equations

for all integers n > 6. The Fibonacci numbers fn are defined recursively
by: f0 =0,f1 =1

For all n > 1, fn = fn−1 + fn−2

The Attempt at a Solution

My problem is, i really don't know where to start. I assuming that I am trying to prove that LHS>RHS in my base cases, instead of LHS=RHS. I started by attempting bases cases of 0 and 1. Those attempts really lead me nowhere. I then attempted 2 and 3 as my base cases. I got LHS<RHS for both, which based on my assumption is the inverse of what I am trying to accomplish.

Should i be looking at larger numbers for my base cases? "for all integers n >6" does this mean i should start bases at 7 and 8? And should i still use my assumption to prove LHS>RHS or should i be trying to make LHS=RHS anyways.

Thanks

 

[ystael]

Should i be looking at larger numbers for my base cases? "for all integers n >6" does this mean i should start bases at 7 and 8?

Yes, it does, because the statement is not true when n \leq 6.

And should i still use my assumption to prove LHS>RHS or should i be trying to make LHS=RHS anyways.

You should be trying to use the inductive hypotheses f_{n-2} &gt; \sqrt{2}(n - 2) and f_{n-1} &gt; \sqrt{2}(n-1) to prove the next case of the statement, f_n &gt; \sqrt{2}\,n.

 

[gwial]

Ok perfect thanks for the right direction.

 

[ryou00730]

It's exactly the same method as last proof, except we use base case of 7 and 8, then set up the same way as last proof we did on the previous assignment, you get down to f(n)> (root2)^(n-1) + (root2)^(n-2) and we are guaranteed that (root2)^(n-2) is always less than (root2)^(n-1) for n>6. So make the substitution where you have (root2)^(n-1) with (root2)^(n-2) to get f(n)> 2(root2)^(n-2) which you can then write as f(n)> (root2)² x (root2)^(n-2) which you can see as it is like bases becomes (root2)^(n-2+2) which simplifies to (root2)⁽ⁿ⁾ . Qed. correct?

 

[HallsofIvy]

What you really NEED to do is state the problem correctly! As given, you cannot prove that "Fibonacci numbers satisfy the inequality fn > (√2)n" because it is NOT true. f0= 0 is NOT larger than 0\sqrt{2}. f1= 1 is NOT larger than 1\sqrt{2}. f2= 2 is NOT larger than 2\sqrt{2}. f3= 3 is NOT larger than 3\sqrt{2}. f4= 5 is NOT larger than 4\sqrt{2}. f5= 8 Is larger than 5\sqrt{2}. Was the problem to prove that &quot;Fibonacci numbers satisfy the inequality fn &gt; (√2)n as long as n&gt; 4&quot;?

 

[ryou00730]

No it should have said for n>6.

 

[epenguin]

Says Polya in "How to solve it" - 'when you have the answer it isn't finished.'

Can you generalise your result? You would then see the question less from under the floorboards if you know what I mean, get more confidence.

This statement with √2 and 6 in it is almost misleadingly special. You could make a more general statement. You don't even have to work out anything involving particular numbers.

 

[gwial]

Ok, sorry if i put one line in section 2 when it was suppose to be in section 1. Thats just how our prof stated the question