# Can I rewrite part of this induction?

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?

-
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

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$.
Or more simply, $f_n\geq 0$ for all $n$. –  Arturo Magidin Mar 9 '11 at 4:47
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\:.$