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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s