Proof by Induction (Inequalities)

Hi,



Subtracting the original statement from the I.S.
$(k+2) - (k+1) \leq 2(2^{k}) - 2^{k} \leq (k+2)! - (k+1)!$
$1 \leq 2^{k} \leq (k+1)![k+2-1]$
$1 \leq 2^{k} \leq (k+1)!(k+1)$

With these kind of inequalities can you split them up? e.g first look at n+1 <= 2^n and then look at 2^n<=(n+1)! ?

Hi,

I haven't come across proof by induction with inequalities before, so I'm not sure if my attempted method for this question is correct.

The question is:

$(\forall n \in \mathbb{N}): n+1 \leq 2^{n} \leq (n+1)!$

Here's how I proved it:

Basis Step:

$n = 1; (n+1 = 2) \leq (2^{n} = 2) \leq ((n+1)! = 2)$
$\therefore\ \mathrm{true\ for}\ n = 1$.

Assumption Step:

Assume true for $n = k$
i.e. $k+1 \leq 2^{k} \leq (k+1)!$

Inductive Step:

With $n = k+1$, the inequality becomes:
$(k+1)+1 \leq 2^{k+1} \leq ((k+1) + 1)! \equiv k+2 \leq 2(2^{k}) \leq (k+2)!$

Subtracting the original statement from the I.S.
$(k+2) - (k+1) \leq 2(2^{k}) - 2^{k} \leq (k+2)! - (k+1)!$
$1 \leq 2^{k} \leq (k+1)![k+2-1]$
$1 \leq 2^{k} \leq (k+1)!(k+1)$

We know $\forall k \in \mathbb{N}$ that $1 < 2^{k}$. We also know from the Assumption Step that $2^{k} \leq (k+1)!$. As $k \geq 1$, $(k+1)! \leq (k+1)!(k+1)$ thus $2^{k} \leq (k+1)!(k+1)$.

Conclusion Step:

Therefore, the inequality is true when $n = k+1$. If the inequality is true for $n = k$, then it is shown to be true for $n = k+1$. As the result is true for $n = 1$, it is now true $\forall n \in \mathbb{N}$ by mathematical induction.