1
$\begingroup$

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?

  • 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).2011-03-09

2 Answers 2

3

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$.

  • 0
    Or more simply, $f_n\geq 0$ for all $n$.2011-03-09
2

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\:.$