Help proving inequality by induction with recurrent sequence?

Question

Problem

For a sequence, $u_n$ , $u_1=u_2=1$ and $u_{n+2}=u_{n+1}+u_n$

Using induction, prove $u_n<2^n$

So, I'm having trouble working through this. I've tried coming up with a conjecture for $u_n$ but it doesn't seem to work: $u_1=1$, $u_2=1$, $u_3=2$, $u_4=3$, $u_5=5$

I don't see a pattern. I'm assuming this isn't the way to go about this problem.

Can someone help me out? Thanks!

Answer 1

Because the base is obvious and by the assumption of the induction we obtain:$$u_{n+2}<2^n+2^{n-1}=3\cdot2^{n-1}<4\cdot2^{n-1}=2^{n+1}.$$

Answer 2

For this (strong) induction, you first need to prove the base cases when $n=1$ and 2. Thus you need to show that $u_1< 2^1$. Since $u_1$ is 1 and $2^1$ is 2 the $n=1$ case is true. Similarly, $u_2=1<2^2=4$.

Now for the induction step, suppose that $$ (*)\quad u_n < 2^n $$ for all values of $n$ less than say $k$ which is greater than 2. Can you then prove that $u_k < 2^k$? We know that $$ u_k = u_{k-2}+u_{k-1} . $$ The idea is to apply (*) twice to the right hand side.

Answer 3

The Base of induction \begin{align} a_1 &= 1<2^1 \\ a_2 &= 1<2^2 \end{align}

Induction from $n$ to $n+1$

\begin{align} a_n &< 2^n \\ a_{n+1} &< 2^{n+1} \\ \implies a_{n+2} &= a_n+a_{n+1} \\ &< 2^{n}+2^{n+1} \\ &< 2^{n+1}+2^{n+1} \\ &= 2^{n+2} \end{align} and the proof is complete.