Proof by Induction

Proof by Induction

Proof by induction is a powerful mathematical technique used to prove statements about natural numbers. It is particularly useful for proving propositions that hold for all integers greater than or equal to a certain number. The method consists of two main steps: the base case and the inductive step.

Base Case

The base case is the initial step where you prove that the statement is true for the smallest natural number, usually 1. This step is crucial because it establishes the foundation upon which the rest of the proof is built.

Inductive Step

The inductive step involves assuming that the statement is true for some arbitrary natural number, say k. This assumption is called the inductive hypothesis. You then need to show that if the statement is true for k, it must also be true for k + 1. This step demonstrates that the truth of the statement for one number implies its truth for the next number.

Example of Proof by Induction

Let us prove the following statement by induction:

Statement: For all natural numbers n, the sum of the first n natural numbers is given by the formula:

S(n) = 1 + 2 + 3 + ... + n = n(n + 1)/2

Step 1: Base Case

We start with the base case where n = 1.

S(1) = 1

According to the formula:

S(1) = 1(1 + 1)/2 = 1 × 2/2 = 1

Since both sides are equal, the base case holds.

Step 2: Inductive Step

Assume the statement is true for some arbitrary natural number k. That is, we assume:

S(k) = 1 + 2 + 3 + ... + k = k(k + 1)/2

Now we must show that the statement holds for k + 1. Thus, we need to prove:

S(k + 1) = 1 + 2 + 3 + ... + k + (k + 1)

Using the inductive hypothesis:

S(k + 1) = S(k) + (k + 1)

Substituting the inductive hypothesis:

S(k + 1) = k(k + 1)/2 + (k + 1)

To combine the terms, we need a common denominator:

S(k + 1) = k(k + 1)/2 + 2(k + 1)/2

S(k + 1) = (k(k + 1) + 2(k + 1))/2

S(k + 1) = (k + 1)(k + 2)/2

This matches the formula for n = k + 1. Thus, the inductive step holds.

Since both the base case and the inductive step have been proven, by the principle of mathematical induction, the statement is true for all natural numbers n.

Types of Proof by Induction

There are several variations of proof by induction, including:

• Simple Induction: The method described above, which covers the base case and the inductive step.
• Strong Induction: In strong induction, the inductive hypothesis assumes the statement is true for all integers less than or equal to k, and then shows it is true for k + 1. This is useful when the proof for k + 1 depends on multiple previous cases.

Example of Strong Induction

Let us prove that every natural number greater than 1 can be written as a product of prime numbers.

Step 1: Base Case

For n = 2, the statement holds since 2 is a prime number.

Step 2: Inductive Step

Assume the statement is true for all natural numbers up to k. We need to show it is true for k + 1.

If k + 1 is prime, then it is a product of itself. If it is not prime, it can be expressed as a × b, where a and b are natural numbers such that 1 < a, b < k + 1. By the inductive hypothesis, both a and b can be written as products of prime numbers. Therefore, k + 1 can also be written as a product of prime numbers.

This completes the proof by strong induction.

Common Mistakes in Proof by Induction

• Not proving the base case. The base case is essential for the validity of the proof.
• Failing to clearly state the inductive hypothesis. This can lead to confusion and incorrect proofs.
• Assuming the statement is true without proper justification. Each step must be logically derived from the previous steps.

Summary

• Proof by induction consists of a base case and an inductive step.
• The base case proves the statement for the smallest natural number.
• The inductive step shows that if the statement holds for k, it also holds for k + 1.
• Strong induction assumes the statement holds for all integers up to k to prove it for k + 1.

Check your understanding

1. What are the two main steps in a proof by induction?
2. How do you prove the base case in a proof by induction?
3. Explain the difference between simple induction and strong induction.
4. What common mistakes should you avoid when performing a proof by induction?