The problem is:
$$F_n \leqslant 2F_{n-1}\quad\text{for every integer} \quad n \geqslant 2.$$
I got the smallest case, I just don't know how to get the assumption and the rest of it
$\begingroup$ $\endgroup$
2 
- 1$\begingroup$ Remember that $F_n = F_{n-1} + F_{n-2}$. What relation between $F_{n-1}$ and $F_{n-2}$ gives you the desired conclusion? $\endgroup$Daniel Fischer– Daniel Fischer2014-09-29 14:40:52 +00:00Commented Sep 29, 2014 at 14:40
- $\begingroup$ After i do the smallest case which is n = 2, could I get help with the assumption? is it just Fk <= 2Fk-1 ??? $\endgroup$Jacolby Hartson– Jacolby Hartson2014-09-29 14:44:46 +00:00Commented Sep 29, 2014 at 14:44
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
You use complete induction: assume that $F_m \leqslant 2F_{m-1}$ for all $m<n$ and prove it for $n$:
$F_n = F_{n-1}+F_{n-2} \le 2F_{n-2}+2F_{n-3} = 2(F_{n-2}+F_{n-3}) = 2F_{n-1}$
You need to start by proving it for $n=2$ and $n=3$.
$\begingroup$ $\endgroup$
5 Yes, you assume that $F_k \lt 2F_{k-1}$ and want to prove that $F_{k+1} \lt 2F_k$ So write $F_{k+1}= $ (what? you only know one thing about it) then apply what you know about the numbers to put an upper bound on this. You do need to know the Fibonacci numbers are positive. You might look at this answer
- $\begingroup$ So would the final solution be Fk+1 <= 2Fk-1 + Fk-2 ? $\endgroup$Jacolby Hartson– Jacolby Hartson2014-09-29 15:02:23 +00:00Commented Sep 29, 2014 at 15:02
- $\begingroup$ Why do we need to know the Fibonacci numbers are positive? $\endgroup$lhf– lhf2014-09-29 15:03:10 +00:00Commented Sep 29, 2014 at 15:03
- $\begingroup$ Knowing that the Fibonacci numbers are non-negative tells you that the sequence is non-decreasing, so $F_{k + 1} = F_k + F_{k - 1} \leq F_k + F_k = 2F_k$. $\endgroup$N. F. Taussig– N. F. Taussig2014-09-29 15:30:00 +00:00Commented Sep 29, 2014 at 15:30
- $\begingroup$ @N.F.Taussig, that's one way but I had something different in mind. See my answer. $\endgroup$lhf– lhf2014-09-29 15:53:41 +00:00Commented Sep 29, 2014 at 15:53
- $\begingroup$ @N.F.Taussig: Exactly. $\endgroup$Ross Millikan– Ross Millikan2014-09-29 19:33:12 +00:00Commented Sep 29, 2014 at 19:33