1

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?

Arturo Magidin
  • 398,050
lampShade
  • 1,053
  • 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 09 '11 at 04:07

2 Answers2

4

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

Leonardo Fontoura
  • 1,259
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\:.$

Bill Dubuque
  • 272,048