Complete Induction Explained - Free Source Library

Complete Induction: Definition and Examples

Induction, in logic and mathematics, refers to the process of drawing general conclusions based on specific observations or examples. However, complete induction, also known as mathematical induction, is a more structured and rigorous form of induction used primarily to prove mathematical statements. It is one of the most important and widely used proof techniques in mathematics, especially when proving statements that apply to an infinite set of natural numbers or other countably infinite sets.

In this article, we will delve into the definition of complete induction, how it works, its importance in mathematical proofs, and explore several examples that illustrate its application.

Definition of Complete Induction

Complete induction is a method of proving a statement for all natural numbers (or other similar sets) by following a structured two-step process. The idea is to prove that if the statement holds for a particular case, then it also holds for the next case, and thus it holds for all cases.

The method can be formally described as follows:

Base Case: First, prove the statement for the initial value in the set (usually when $n = 1$ , though it can sometimes be a different starting point). This is often referred to as the “base case” and serves as the foundation for the induction.
Inductive Step: Assume that the statement holds for some arbitrary natural number $n = k$ . This assumption is called the inductive hypothesis. Then, prove that under this assumption, the statement also holds for the next number, $n = k + 1$ . This is the inductive step.

By completing these two steps, we can conclude that the statement holds for all natural numbers starting from the base case.

Why is Complete Induction Important?

Complete induction is particularly useful for proving propositions that apply to an infinite set of numbers or objects. Many mathematical theorems, especially those related to sequences, series, inequalities, divisibility, and structures, require the ability to prove a statement for an infinite number of cases.

One of the advantages of mathematical induction over other proof methods is its ability to prove statements about infinite sets without directly evaluating each individual case. Instead, it establishes the general truth of the statement by showing that it is true for the starting case and that it propagates through the entire set via the inductive step.

Steps of a Complete Induction Proof

The process of complete induction can be broken down into the following steps:

Base Case: Prove the proposition for the initial value, typically $n = 1$ . This is straightforward as it involves verifying the proposition for a specific number.
Inductive Hypothesis: Assume that the statement is true for an arbitrary number $n = k$ . This assumption is not the conclusion but a working hypothesis that helps us prove the next step.
Inductive Step: Using the assumption that the statement is true for $n = k$ , prove that it must then be true for $n = k + 1$ . The critical idea is that if the statement is true for $k$ , then we can show that it is true for $k + 1$ , which ensures that the statement holds for all natural numbers.

Examples of Complete Induction

Example 1: The Sum of the First $n$ Natural Numbers

A classic example of complete induction involves proving the formula for the sum of the first $n$ natural numbers:

$S(n) = 1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}$

To prove this using complete induction:

Base Case: For $n = 1$ , we check if the formula holds:

$S(1) = 1 = \frac{1(1 + 1)}{2} = 1$

Since the formula holds for $n = 1$ , the base case is true.
Inductive Hypothesis: Assume that the formula holds for $n = k$ . That is, assume:

$S(k) = 1 + 2 + 3 + \dots + k = \frac{k(k + 1)}{2}$

is true.
Inductive Step: We now need to prove that the formula holds for $n = k + 1$ . Using the inductive hypothesis, we calculate $S(k + 1)$ :

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

Substituting the inductive hypothesis for $S(k)$ :

$S(k + 1) = \frac{k(k + 1)}{2} + (k + 1)$

Factor out $k + 1$ :

$S(k + 1) = \frac{k(k + 1)}{2} + \frac{2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2}$

This matches the formula for $S(n)$ , so the formula holds for $n = k + 1$ .

Since both the base case and inductive step hold, by complete induction, the formula is valid for all natural numbers $n$ .

Example 2: Divisibility of Powers of 2

Another classic example involves proving that $2^n – 1$ is divisible by 1 for all $n \geq 1$ .

Base Case: For $n = 1$ , $2^1 – 1 = 1$ , which is clearly divisible by 1.
Inductive Hypothesis: Assume that for some $n = k$ , $2^k – 1$ is divisible by 1.
Inductive Step: We need to prove that $2^{k+1} – 1$ is divisible by 1. Using the inductive hypothesis:

$2^{k+1} – 1 = 2 \cdot 2^k – 1 = 2 \cdot (2^k – 1) + 1$

Since $2^k – 1$ is divisible by 1, the expression is divisible by 1 as well.

Thus, by complete induction, $2^n – 1$ is divisible by 1 for all $n \geq 1$ .

Example 3: Proving an Inequality

Suppose we want to prove that for all $n \geq 1$ , the inequality $n^2 + n \geq 2n$ holds. We proceed as follows:

Base Case: For $n = 1$ , check if the inequality holds:

$1^2 + 1 = 2 \geq 2 \cdot 1 = 2$

The base case is true.
Inductive Hypothesis: Assume that the inequality holds for $n = k$ , i.e., $k^2 + k \geq 2k$ .
Inductive Step: We need to prove that $(k + 1)^2 + (k + 1) \geq 2(k + 1)$ . Expanding both sides:

$(k + 1)^2 + (k + 1) = k^2 + 2k + 1 + k + 1 = k^2 + 3k + 2$

and

$2(k + 1) = 2k + 2$

Now, since by the inductive hypothesis $k^2 + k \geq 2k$ , we can add $2k + 2$ to both sides:

$k^2 + 3k + 2 \geq 2k + 2k + 2 = 2(k + 1)$

Therefore, the inequality holds for $n = k + 1$ .

Thus, by complete induction, the inequality $n^2 + n \geq 2n$ holds for all $n \geq 1$ .

Conclusion

Complete induction is an essential proof technique in mathematics, allowing us to prove propositions about natural numbers and other infinite sets. By using the two-step process of proving a base case and an inductive step, complete induction offers a powerful and efficient way to establish the truth of statements that might otherwise be difficult to prove through direct verification or other methods. Through examples like the sum of the first $n$ natural numbers and divisibility statements, we see that complete induction is versatile and widely applicable across mathematical disciplines.