0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Oct 18 '18 at 2:09
  • $\begingroup$ Just do the induction, since the statement is given to you. $\endgroup$
    – xbh
    Oct 18 '18 at 2:10
0
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.