Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $f_0 = 1$, and $f_1 = 1$, and $f_n = f_{n-1}+f_{n-2}$ when $n \gt 1$ (the Fibonacci sequence)

Prove using induction that $f_n\gt 2n$, when $n \geq 6$. (note the $f_6 = 13$, $f_7=21$)

I want to rewrite $f_n \gt 2n$ as $f_n\gt f_{2n}$ is this legal?

share|improve this question
9  
Nobody will haul you off to jail, but it will be false. $2n$ is not the same thing as $f_{2n}$. The 8th Fibonacci number is not the same thing as $8$. (And since the Fibonacci sequence is increasing, there is no value of $n$ that makes $f_n\gt f_{2n}$ true). –  Arturo Magidin Mar 9 '11 at 4:07
add comment

2 Answers

It's not correct, as $f_{n} = f_{n-1} + f_{n-2}$, so, if you recursively write $f_{2n}$ in terms of $f_{n}$ and $f_{n-1}$, you'll, see that $f_{2n}\gt f_{n}$ if $n\geq 1$.

share|improve this answer
    
Or more simply, $f_n\geq 0$ for all $n$. –  Arturo Magidin Mar 9 '11 at 4:47
add comment

HINT $\ $ Prove by induction that any increasing sequence, once positive, remains positive, then apply that to $\rm\ g_{\:n} =\ f_n - 2\ n\:,\: $ which is increasing since $\rm\ g_{\:n+1}-g_{\:n}\ =\ f_{n-1} - 2\ >\ 0\ $ for $\rm\ n \ge 6\:.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.