0
$\begingroup$

Question: The Fibonacci numbers are $1,1,2,3,5,8,13,21,34,\dotsc$ In general, the Fibonacci numbers are defined by $f_1=1$, $f_2=1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \geq 3$. Prove that the $n$-th Fibonacci number $f_n$ satisfies $f_n < 2^n$.

I know that I am supposed to use induction to prove this. I'm just not sure where to start. I set $n=1$, which made $f_n = f_1 < 2^1$. Therefore, I believe $n=1$ satisfies $f_n < 2^n$. I think I now need to set $n= k + 1$ where $k$ is some integer. I do not know where I should plug this in. Looking for some guidance please!

$\endgroup$
  • $\begingroup$ Please use Math Jax (Latex code) in the future. Thank you. I edited your question accordingly. $\endgroup$ – amsmath Aug 28 '18 at 23:15
  • $\begingroup$ That is to say, the sequence less than doubles between terms asymptotically $\endgroup$ – Jacob Wakem Aug 28 '18 at 23:15
  • $\begingroup$ Possible duplicate of math.stackexchange.com/questions/894743/… $\endgroup$ – lhf Sep 4 '18 at 10:19
3
$\begingroup$

Hint $$2^{n-1}+2^n < 2^n+2^n=2^{n+1}$$

$\endgroup$
0
$\begingroup$

It is easily verified that the sequence never doubles between subsequent terms, except trivially. This is sufficient to show it never on average exceeds doubling between its subsequent terms.

$\endgroup$
0
$\begingroup$

Because $f_n = f_{n-1} + f_{n-2}$ you will need to do a 2 step induction. I.e. show it is true for $f_1$ and $f_2$, then assuming it is true for $n-2$ and $n-1$ show it is also true for $n$.

$\endgroup$
  • $\begingroup$ Really? Explain please. $\endgroup$ – Paul Childs Aug 28 '18 at 23:23
  • $\begingroup$ Oh ok, sorry. I did not read carefully enough. My bad. However, what you suggest is not a "2 step induction" for me. I will delete my comment. $\endgroup$ – amsmath Aug 28 '18 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.