Proving $2n+1 < 2^{n}$ using mathematical induction.

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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