\[a_1=1, \: a_2=1, a_{n+2}=a_{n+1}+a_n\]
The first few terms of the sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34
Though the sequence increases without limit, each term
\[a_=n\]
is less than \[2^n\]
. We can prove this with induction.Let
\[P(k)\]
be the statement "\[a_k \lt 2^k\]
".\[a_1 =1 \lt 2^1=2\]
so \[P(1)\]
is true. Suppose now that
\[P(k)\]
is true for \[n=1,2,...,k\]
.Then
\[a_{k+2}=a_{k+1}+a_k \lt 2^{k+1}+2^k=2n (2+1) \lt 2^k (2+2)=2^k \times 2^2=2^{k+2}\]
.Hence
\[P(k+1}\]
is true.