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