proof by complete induction

fibonacci sequence {fn}= 1,1,2,3,5,8,13,... you know this. defined recursively by f1=1 f2=1 fn+2 = fn+1 + fn for n=1,2,3,... use complete induction to prove that fn < 2^n for all positive integers n. I'm just a little confused with the complete induction part the book and teacher didn't explain it too well.

Quote:

Originally Posted by Puubes

fibonacci sequence {fn}= 1,1,2,3,5,8,13,... you know this. defined recursively by f1=1 f2=1 fn+2 = fn+1 + fn for n=1,2,3,... use complete induction to prove that fn < 2^n for all positive integers n. I'm just a little confused with the complete induction part the book and teacher didn't explain it too well.

We have that
$f_1 < 2^1$
and
$f_2 < 2^2$

Now assume that there is a number k such that $f_m < 2^m$ for all $m \leq k$ .

We wish to show that
$f_{k + 1} < 2^{k + 1}$

Well,
$f_{k + 1} = f_k + f_{k - 1}$

and we know, by assumption, that
$f_{k - 1} < 2^{k - 1}$
and
$f_k < 2^k$

Thus
$f_{k + 1} = f_k + f_{k - 1} < 2^k + 2^{k - 1}$

But
$2^k + 2^{k -1} < 2^{k + 1}$ <-- I leave this for you to prove.

Thus
$f_{k + 1} = f_k + f_{k - 1} < 2^k + 2^{k - 1} < 2^{k + 1}$

implies
$f_{k + 1} < 2^{k + 1}$
as desired.

Thus the theorem is true for n = 1, 2, ...

-Dan

thanks dan that seems simple enough.