Fibonacci sequence is defined as follows $\{F_{n}\}_{n=0}^{\infty}$, where $F_{n+2}=F_{n+1}+F_{n}$. How to prove that this sequence is divergent?
I started with definition of limit goes to infinity, i.e. $\forall M \in \mathbb{R}, \exists n_{0} \in \mathbb{N} s.t. \forall n \in \mathbb{N}, n < n_{0} \implies F_{n} > M$ , prove that it is divergent.
I have no idea how to prove it, any suggestions would be appreciated.
We prove that $F_n \geq n-2$ by induction.
(1) The inequality hold for $n=1,2,3,4$.
(2) Suppose it is true for $F_n$ with $n=1,2,...,k+1$ for $k\geq3$, then we have $F_{k+2}=F_{k+1}+F_k \geq (k-1)+(k-2) = 2k-3 \geq k$. (The last inequality holds by $k \geq 3$).
This proves $F_n>n-2$ and hence $F_n$ diverge. Actually, Fibonacci sequence diverge exponentially, but here we only prove it diverge faster than $O(n)$.