2
$\begingroup$

I'm learning about how use mathematical induction. I'm tasked with proving the inequality shown in (1). It is a requirement that I use mathematical induction for the proof.

$(1) \quad P(n):\quad 2n+1 < 2^{n}, \quad n \ge 3$

I would like some feedback regarding whether my proof is valid and if my use of the induction hypothesis is correct. My proof:

Prove base case:

$(2) \quad P(b):\quad 2\cdot3+1 < 2^{3}, \quad b=1$

$(3) \quad P(b):\quad 7<8$

Assume that $P(n)$ is true for an arbitrary $k$, with $n \ge k \ge 3$. (This is the induction hypothesis, IH)

$(4) \quad P(k):\quad 2k+1 < 2^{k}$

The inductive step:

$(5) \quad P(k+1):\quad 2(k+1)+1 < 2^{k+1}$

$(6) \quad 2k+3 < 2^{k}\cdot 2$

Using the IH we get (7). I just added 2 to both sides of the inequality so that the LHS in (6) and the IH is equal.

$(7) \quad 2k+3 \overset {IH}{<} 2^{k}+2$

Subtracting 2 from both sides yields us $P(k)$:

$(8) \quad 2k+1 < 2^{k}$

Which concludes the proof that $P(n)$ is true for every $n \ge 3$

Is my proof valid? Is my use of the IH correct?

I am aware that a similar problem is asked here.

$\endgroup$
  • 1
    $\begingroup$ How did you get from $2k+3<2^k\times 2$ to $2k+3<2^k+2$? You seem to add $2$ to the IH, then substract $2$ from this, and conclude that the result is the IH hence the proof is finished. If you are not using anywhere the fact that $2^k+2<2^k\times2$ (for $k>1$), then the proof is incorrect. $\endgroup$ – Jean-Claude Arbaut Dec 29 '17 at 11:01
  • $\begingroup$ If you are ok, you can accept the answer and set as solved. Thanks! $\endgroup$ – gimusi Dec 31 '17 at 10:25
1
$\begingroup$

It's not clear to me how you proved that $P(k) \implies P(k + 1)$. You have a collection of inequalities $(5), (6), (7), (8)$, but I don't see which of them are implied by the others. Here's an alternative approach.

Assume that $P(k)$ is true for some $k$, where $k \geq 3$. It remains to show that $P(k + 1)$ is true. Indeed, observe that: \begin{align*} 2(k + 1) + 1 &= 2k + 3 \\ &= (2k + 1) + 2 \\ &< 2^k + 2 &\text{by the induction hypothesis} \\ &< 2^k + 8 \\ &= 2^k + 2^3 \\ &\leq 2^k + 2^k &\text{since $3 \leq k$, and $2^x$ is an increasing function} \\ &= 2 \cdot 2^k \\ &= 2^{k + 1} \end{align*} as desired.

$\endgroup$
  • $\begingroup$ Whoops, my bad, you're right. Edited. $\endgroup$ – Adriano Dec 29 '17 at 12:40
1
$\begingroup$

You know it for $n=3$. Suppose this is true for $n$, i.e., $2n+1<2^n$. Let us prove it for $n+1$, i.e., $2(n+1)+1<2^{n+1}$. You have $$ 2n+3=(2n+1)+2<2^n+2 \le 2^{n+1}. $$ The last inequality is true because $n\ge 3$.

$\endgroup$
  • $\begingroup$ Nice +1. The last inequality is true even for $n>0$ $\endgroup$ – Isham Dec 29 '17 at 11:44
1
$\begingroup$

Base case:

$n=3 \implies 7<8$ ok

Inductive step:

let's assume: $2n+1 < 2^{n}$

we want to prove that: $2n+3 < 2^{n+1}$

$$2n+3=2n+1+2\overset {IH}{<} 2^n+2=2(2^{n-1}+1)\overset {?}{<} 2\cdot2^n=2^{n+1}$$

we can easily check that $$2^{n-1}+1< 2^n\iff2^n-2^{n-1}>1\iff2^{n-1}(2-1)>1 \quad \forall n>1$$

thus

$$2n+3<2^{n+1} \quad \square$$

$\endgroup$
0
$\begingroup$

I want to suggest an alternative way just to be more systematic:

Let $a(n) = 2n+1$ and $b(n)= 2^n$ where $n \ge 3$. Then for $n=3$, we have $7 = a(3) < b(3) = 8$. Then assume inductively that $a(n) < b(n)$ and $n > 4$. Then, for $n+1$, we have $$a(n+1) = 2n+3 = 2n+1+2 = a(n)+2 < b(n)+2$$ by inductive hyphotesis. But notice that $$b(n)+2 = 2^n+2 < 2 \cdot 2^n = 2^{n+1} = b(n+1)$$

Therefore, we have $$a(n+1) < b(n)+2 < b(n+1) \implies a(n+1) < b(n+1)$$

$\endgroup$
0
$\begingroup$

Hypothesis:

1) You assume that $2n+1 < 2^n$ for an $n.$

Step:

Assuming the hypothesis :

Show that $2(n+1) +1 < 2^{n+1}$, I.e.

the formula holds for $n+1.$

$2n+1 + 2 =$

$2(n+1) +1 < 2^n +2 ;$

$2$ has been added to both sides of $2n+1 <2^n$ (hypothesis) .

LHS : $2(n+1) +1$.

RHS: $2^n +2 \lt 2^n +2^n= $

$2(2^n) =2^{n+1}$.

since $2 \lt 2^n$ for $n \ge 3.$

Hence:

$2(n+1)+1 < 2^{n+1}.$

$\endgroup$
0
$\begingroup$

Alternatively, without induction: for $n\ge 3$: $$2^n=(1+1)^n=1+n+\cdots +n+1>2n+1.$$

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