Prove that the Fibonacci recursion diverges I have this sequence with $ n \in \mathbb{N} $
$ f(1) = f(2) = 1 $ and $ f(n) = f(n-1) + f(n-2) $ for $n \ge 3$
I think this sequence is bounded below and unbounded above.
So it's clear that this recursive sequence diverges.

Questions:


*

*Is this correct?

*How can I write my reflections down in a formally correct way?

 A: If $f(1), f(2) \ge 0$ and the right hand side adds the preceding two terms (always adding previous two positives). Then isnt it obvious that $f(n+1)\gt f(n)$ for all $n\ge 2$ and that $f(n+1) - f(n) \ge f(1)$.
A: Hint
Show by induction that $f(n)$ is increasing. Thus, $f(n)\ge f(1)$ which shows that it is bounded from below. 
Show by induction that $f(n)\ge n-1.$ Thus, $f(n)$ is not bounded from above. (This also shows that $f(n)$ is bounded from below, since $f(n)\ge n-1\ge 0.$)
A: Proof by induction for lower bound:


*

*Assume, that $f(k)>0$ for $k\leq n$

*$f(1)>0$ and $f(2)>0$

*Then $f(n+1)=f(n)+f(n-1)>0$.


Proof for divergence by induction:


*

*Assume, that $f(k)\geq k$ for $5\leq k\leq n$

*$f(5)\geq 5$ and $f(6)\geq 6$. 

*$f(n+1)=f(n)+f(n-1)\geq n+(n-1)=2n-1\rightarrow \infty $ for $n\rightarrow \infty$.


Of course, you would need to write down the steps in a more formal way.
A: Obviously $f(n)\geq 1$. Assume to the contrary that it converges to some  $l$. By that trivial observation $l\geq 1.$ Then $\lim_{n\to\infty}f(n) = \lim_{n\to\infty}f(n-1) +\lim_{n\to\infty} f(n-2)\Rightarrow2l=l\Rightarrow l=0$ Contradiction!! 
