Question

How can we prove using mathematical induction that `2^(n+1)>2n+1` if n is a natural number?

Answer 1

See explanation.

Explanation:

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 in ZZ^+}`.

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≥2(k+1)+1=2k+3`. We solve this to get `k≥1/2`. Since `kinZZ^+`, our proof is finished.