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} > \sqrt{2}(n - 2)$$ and $$f_{n-1} > \sqrt{2}(n-1)$$ to prove the next case of the statement, $$f_n > \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 "Fibonacci numbers satisfy the inequality fn > (√2)n as long as n> 4"?$

 

[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