Answer to Question #343501 in Discrete Mathematics for Greatfortune

Question

Prove by PMI for 2^n+1>2n+1

Answer 1

For mathematical induction, we need to prove the following:

1. It is true for some base case
2. If it is true for k, it must be true for k+1

The definition for natural numbers vary, but I will be using the definition of all positive integers (excluding zero), or {$m|m\isin\Z^+$ }.

First, we need to prove that the expression is true for some base case. Here, we start from 1:

$2^{1+1}>2*1+1$ , which is indeed true.

Now, we suppose that it is true for some natural number k. Then, $2^{k+1}>2k+1.$

We can multiply both sides by 2: $2*2^{k+1}>2*(2k+1).$ So, if it is true for k, then

$2^{k+2}>4k+2$ .

To complete the proof, we just need to show that the expression in the question is true for

$k+1$ if it is true for k. We need to prove that $2^{k+1+1}>2(k+1)+1$ , or $2^{k+2}>2k+3$ .

Comparing this with the inequality in the equation from the last paragraph, we realize that we would be done if we could prove that

$4k+2\ge2(k+1)+1=2k+3.$  We solve this to get $k\ge1/2.$ Since $k\isin\Z^+$ , our proof is finished.