Mathematical Induction Proofs

The Principle of Induction: From Dominoes to Axioms

Many mathematical statements are claims about all natural numbers $n\in \mathbb{N}$. For example, "The sum of the first $n$ odd positive integers is $n^2$." How can we prove such a statement for an infinite number of cases without testing every single one?

The intuitive idea behind induction is that of a "domino effect." If you can prove:

1. The first domino falls.
2. Any domino falling causes the next one to fall.

Then you can conclude that all dominoes will fall. In mathematical terms, if we want to prove a statement $P(n)$ for all $n\ge 1$:

1. Base Case: Prove that $P(1)$ is true.
2. Inductive Step: Prove that for any $k\ge 1$, if $P(k)$ is true, then $P(k+1)$ must also be true.

The assumption "if $P(k)$ is true" is called the inductive hypothesis.

This isn't just a handy trick; it is a rigorous theorem rooted in the fundamental properties of the natural numbers. For a learner who values a proof-heavy approach, it is essential to see why induction is a valid proof technique. The following video does an excellent job of proving the principle of induction itself. It uses the well-ordering property of the natural numbers (which states that every non-empty set of natural numbers has a least element) and proof by contradiction, connecting this lesson directly to our previous one.

The proof in the video establishes that the two-step process of induction is logically sound. You don't need to reproduce this proof every time you use induction, but understanding it solidifies why the method works.

Structuring an Inductive Proof: A First Example

Let's apply this principle to a classic problem: finding a closed-form expression for the sum of the first $n$ non-negative integers.

Proposition: For any natural number $n\in \mathbb{N}=\{0,1,2,\dots \}$, the statement $P(n):0+1+2+\cdots +n=\frac{n(n+1)}{2}$ is true.

The following resource walks through this exact proof. It clearly demonstrates the two-step structure.

Let's formalize the structure of that proof, as you will use this template repeatedly.

Proof. We proceed by mathematical induction.
Let $P(n)$ be the statement $0+1+2+\cdots +n=\frac{n(n+1)}{2}$.

1. Base Case: We must show that $P(0)$ is true.
For $n=0$, the left-hand side (LHS) is simply 0.
The right-hand side (RHS) is $\frac{0(0+1)}{2}=0$.
Since LHS = RHS, $P(0)$ is true.

2. Inductive Step: We must show that for any integer $k\ge 0$, if $P(k)$ is true, then $P(k+1)$ is true.
Inductive Hypothesis: Assume $P(k)$ is true for some arbitrary integer $k\ge 0$. That is, assume:
$0+1+2+\cdots +k=\frac{k(k+1)}{2}$
Goal: We want to prove that $P(k+1)$ is true. That is, we want to show:
$0+1+2+\cdots +k+(k+1)=\frac{(k+1)((k+1)+1)}{2}=\frac{(k+1)(k+2)}{2}$
Now we start with the LHS of $P(k+1)$ and use our inductive hypothesis.

We have successfully shown that if $P(k)$ is true, then $P(k+1)$ is true.

By the principle of mathematical induction, the statement $P(n)$ is true for all natural numbers $n\ge 0$. □

Broadening the Application: Inequalities and Other Base Cases

Induction is not limited to summation formulas. It is widely used to prove inequalities, properties of divisibility, and results in combinatorics and geometry. Let's look at another classic example: Bernoulli's Inequality.

Sometimes, a statement is not true for small values of $n$, but holds for all integers from a certain point onward. The principle of induction is easily adapted for this. Instead of using $n=0$ or $n=1$ for the base case, you simply use the first integer for which the statement is claimed to be true.

Proposition: For all integers $n\ge 5$, $2^n>n^2$.

Let's check for small $n$:

• $n=1:2^1=2,1^2=1⟹2>1$ (True)
• $n=2:2^2=4,2^2=4⟹4>4$ (False)
• $n=3:2^3=8,3^2=9⟹8>9$ (False)
• $n=4:2^4=16,4^2=16⟹16>16$ (False)
• $n=5:2^5=32,5^2=25⟹32>25$ (True)

It seems the statement holds for $n=1$ and then for $n\ge 5$. Let's prove the latter part.

A Common Fallacy: The Flaw in the Logic

Rigorous application of induction requires that the inductive step, $P(k)\to P(k+1)$, holds for every integer $k$ from the base case onward. A common mistake is to have a seemingly plausible inductive step that fails for a specific value of $k$. This can lead to absurd conclusions.

The following "proof" claims that all things in any group are the same color. Your task is to find the flaw.

Did you spot the error?

The argument breaks down when we try to prove $P(2)$ from $P(1)$. Let $k=1$. We are trying to prove the statement for a group of $k+1=2$ things.
The proof says:

1. "the first $k=1$ things are of the same colour" (True, this is just one thing).
2. "the last $k=1$ things are also of the same colour" (True, this is the other thing).
3. "Therefore, the $k+1=2$ things are of the same colour."

This conclusion does not follow. The "first 1" and the "last 1" are disjoint sets with no overlap. We can't conclude they are the same color. The argument about overlapping groups only works if $k>1$. The inductive step fails for the very first step, $k=1\to k=2$, invalidating the entire proof.

Conclusion

In this lesson, we have formally introduced the principle of mathematical induction as a rigorous method for proving statements about natural numbers.

Here are the essential takeaways:

• An inductive proof consists of two parts: the base case (proving the statement for the first value, e.g., $P(1)$) and the inductive step (proving that if the statement holds for an arbitrary $k$, it must also hold for $k+1$).
• The validity of induction is guaranteed by the well-ordering property of the natural numbers.
• The base case can start at any integer $N$, in which case the proof establishes the statement for all $n\ge N$.
• It is critical to ensure the inductive step is valid for all values of $k$ from the base case upwards.

You have now mastered the basic form of induction. This technique is sometimes called "weak" or "standard" induction because the inductive hypothesis only assumes $P(k)$ is true. In our next lesson, we will explore a related but even more powerful variant called strong induction, where we assume the statement holds for all values up to $k$.