Example of a Proof by Induction
If n ∈ N, then 21+22 +23 +··· +2n = 2n+1 −2.
Proof. The proof is by mathematical induction.
(1) When n = 1, this statement is 21 = 21+1 −2, or 2 = 4−2, which is true.
(2) Now assume the statement is true for some integer n = k ≥ 1, that is assume
22 + 22 + 23 + ··· + 2k= 2k+1 − 2. Observe this implies that the statement is true for n = k +1, as
follows:
21 +22 +23 +··· +2k+2k+1 =
(21 +22+23 +··· +2k )+2k+1 =
2k+1 −2+2k+1 = 2·2k+1 −2
= 2k+2−2
= 2(k+1)+1−2.
Thus, we have 21+22+23+···+2k+2k+1 = 2(k+1)+1 −2, so the statement is true for n = k+1.
Thus, the result follows by mathematical induction
Explanation of the Proof:
The proof uses mathematical induction to show that the
formula 21 + 22 + 23 + ... + 2n = 2n+1− 2 holds for every positive integer n.
Step 1: Base Case (n = 1)
The proof begins by verifying the formula for the base case,
where n = 1. In this case, the left-hand side of the equation is 21= 2, and the right-hand side is
21+1 − 2 = 2. Since both sides are equal, the formula is true for n = 1.
Step 2: Inductive Hypothesis
The proof then assumes that the formula is true for some
integer n = k ≥ 1. That is, it assumes that 22 + 22 + 23 + ... + 2k = 2k+1− 2 is true.
Step 3: Inductive Step (n = k + 1)
The proof aims to show that if the formula is true for n =
k, then it must also be true for n = k + 1. To do this, the proof considers the
sum 21 + 22 + ... + 2k + 2k+1.
Using the inductive hypothesis, the sum 21 + 22+ ... + 2k can be replaced with 2k+1 − 2. Thus, the entire sum becomes 2k+1 − 2 + 2k+1.
Next, the proof simplifies the expression by combining like terms. The sum becomes 2(2k+1) − 2, which is equal to 2k+2− 2.
Finally, using the exponent rule that 2(2k+1)is equal to 2k+2, the expression becomes 2k+1+1 − 2, which is the right-hand side of the formula for n = k + 1.
Since the inductive step shows that if the formula is true for n = k, then it must also be true for n = k + 1, the proof establishes that the formula 21 + 22 + 23 + ... + 2n = 2n+1− 2 holds for every positive integer n.