## Limit on the Terms of a Fibonacci Sequence

The Fibonacci sequence is defined as:
$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.