# Mathematical Induction II

This next post will focus on using mathematical induction to prove an inequality. Our statement to be proven is as follows:

$2n + 1 \textless 2^n$ for all integers n $\geq 3$

Solution:

The first step as always in theses types of proofs is to prove the basis step. This is accomplished by just inputting  values.

Show that P(3) is true:

$2n + 1 \textless 2^n$

$2(3) + 1 \textless 2^3$

$7 \textless 8$

As was shown above, the basis step checks out in our proof and we are now ready to move onto our inductive step.

Show that the inductive hypothesis is true:

Suppose that k is some arbitrarily chosen but particular value such that:

$2k + 1 \textless 2^k$ for all integers k $\geq 3$

We must show that

$2(k+1) + 1 \textless 2^{k+1}$ for all integers n $\geq 3$

We are allowed to use part of our inductive hypothesis because that’s what we are assuming to be true. In order to take advantage of our inductive hypothesis we must re-arrange out current statement P(k+1). The left side of this inequality can be written as follows:

$2(k+1) + 1 = 2k + 2 + 1 = (2k + 1) + 2$

With the left side of the inequality in this form we can make the following claim:

$(2k + 1) + 2 \textless 2^k + 2$

This result was achieved by simply substituting the 2k+1 term from our inductive hypothesis. Now if we can prove that $2^k + 2$ is strictly less than $2^{k+1}$ we will have finished the proof.

This next step takes a little finesse because we must remember how inequalities work. We must remember that by adding/subtracting/multiplying/dividing the same POSITIVE term for both sides we are maintaining the inequalities validity (try a few cases if  your not satisfied). This means that we can go through the following set of manipulations:

$2^k + 2 \textless 2^{k+1}$

$2 \textless 2^{k+1} - 2^k$

$2 \textless 2^k(2-1)$

$2 \textless 2^k(1)$

$2 \textless 2^k$

$\frac{2}{2} \textless \frac{2^k}{2}$

$1 \textless 2^{k-1}$

Our final inequality is clearly valid for all terms $k \geq 2$ thus by default it will be valid for all $k \geq 3$

$\therefore 2n + 1 \textless 2^n$ for all integers $n \geq 3$