Help proving inequality by induction with recurrent sequence?

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$$

Can someone help me out? Thanks!

• You don't need to do anything clever here, you can just directly apply induction. You already know the statement is true for $n=1,2$. Now assume the statement is true for $n$ and $n+1$. Show that it follows that the statement is true for $n+2$. Oct 18 '18 at 2:09
• Just do the induction, since the statement is given to you.
– xbh
Oct 18 '18 at 2:10

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}.$$

• Technically, would you say this argument is strong induction? Oct 18 '18 at 2:14
• @Moed Pol Bollo We can say so. Oct 18 '18 at 2:19
• How did you obtain the LHS of the second inequality? @MichaelRozenberg Oct 18 '18 at 14:34
• @natojato $2^n+2^{n-1}=2\cdot2^{n-1}+2^{n-1}=(2+1)2^{n-1}=3\cdot2^{n-1}.$ Oct 18 '18 at 16:01

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.

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.