Proove that $2n-3\leq 2^{n-2}$ for all $n\geq 5$

The following is the proof asked in https://goo.gl/h5uyhK


Prove that $$2n-3\leq 2^{n-2}\text{ for all } n\geq 5$$

Solution (by Mathematical Induction)


1. Base case: If $n=5$, the left side is 7 and the right side is $2^{5-2}=2^3=8$. So, the inequality holds when $n=5$.

2. Inductive hypothesis: Suppose the inequality holds for all values of $n$ up to some $k\geq5$, $P(k):2k-3\leq 2^{k-2}$.
3. Inductive step: Let $n=k+1$. Now we have to prove that the relation also holds for $k+1$ by using the induction hypothesis. This means that we have to prove
$$P(k+1):2(k+1)-3\leq 2^{(k+1)-2}$$
Then our left side is
$$\begin{align} P(k+1):2(k+1)-3 &= 2k-3+2 \\ &\leq 2^{k-2} +2 \text{, by our inductive hypothesis}\\ &\leq 2^{k-2} + 2^{k-2} \text{ since } 2\leq 2^{k-2}, \forall k\geq 5 \\ &\leq 2\cdot 2^{k-2} \\ &\leq 2^{k-2+1} \\ &=2^{k-1} \end{align}$$
Thus
$$2(k+1)-3\leq 2^{k-1} \Longrightarrow 2k-3 \leq 2^{k-2}$$
which is our right side. So, the theorem holds for $n=k+1$.
By the principle of mathematical induction, the theorem holds for all $n\geq 5$.

Comentarios

  1. Nice proof. Your proof is helpfull for me. I can understand this explanation too. Thank you very much for your help.

    ResponderEliminar
    Respuestas
    1. You are welcome Dian! I'm glad it helped you.
      Ask me anytime.

      Eliminar
  2. Okay Luis. I'll ask you if I need a help. Thank you so much Luis. I'm not good at mathematical induction :'(

    ResponderEliminar
    Respuestas
    1. Be my guest!

      And do not worry, it could be difficult at the beggining, but you can get use to it whenever you practice what you need. Keep going!

      Eliminar

Publicar un comentario

Su opinión es muy importante.

Entradas populares