Table of Contents
Understanding Mathematical Induction
Mathematical induction is a proof technique used to show that a statement is true for all natural numbers from some starting point onward (usually all integers $n \ge 1$ or $n \ge 0$).
It is especially suited to statements that talk about an integer parameter $n$ in phrases like “for every natural number $n$”, or that involve sums, products, patterns, or recursively defined objects.
This chapter assumes you already know what a proof is and have seen other proof techniques such as direct proof and proof by contradiction. Here we focus on how induction works and how to use it.
The Idea Behind Induction
The key idea is a “domino effect”:
- If the first domino falls, and
- whenever one domino falls, the next one also falls,
then eventually all the dominos fall.
In induction, each domino represents a natural number $n$ and a statement $P(n)$ about that number. To prove that $P(n)$ is true for all $n$ in some range, you show:
- $P$ is true for the first value (the “first domino”).
- If $P(k)$ is true for some arbitrary integer $k$ in the range, then $P(k+1)$ is also true (the “domino effect”).
If both are proved logically, it follows that $P(n)$ is true for every $n$ from the starting point onward.
The Structure of a Basic Induction Proof
Most simple induction proofs follow this pattern.
Let $P(n)$ be a statement about a natural number $n$.
To prove: $P(n)$ is true for all integers $n \ge n_0$ (for some starting integer $n_0$).
1. Base Case
You verify that the statement holds for the first value $n_0$:
- Write clearly what $P(n_0)$ says.
- Show it is true by direct checking.
This is the “first domino.”
Example skeleton:
- Base case: Let $n = 1$. Then $P(1)$ states that $2 \cdot 1 \ge 1$, which is $2 \ge 1$, true.
The base case may sometimes involve $n_0 = 0$, $n_0 = 2$, or another starting value, depending on the problem.
2. Induction Hypothesis
You assume that $P(k)$ is true for some arbitrary integer $k \ge n_0$.
- This is not something you have “proved” yet; instead, you temporarily assume it in order to deduce $P(k+1)$.
- You must state this assumption clearly.
Example skeleton:
- Induction hypothesis: Assume that for some integer $k \ge 1$, the statement $P(k)$ is true. That is, assume
$$\text{(some equation or inequality involving }k\text{)}.$$
This is called the induction hypothesis.
3. Induction Step
Using the induction hypothesis, you must prove that $P(k+1)$ is true:
- Start with the expression or condition that appears in $P(k+1)$.
- Manipulate it algebraically or logically.
- At some point, use the assumption $P(k)$.
- End by obtaining exactly the statement $P(k+1)$.
Example skeleton:
- Induction step: We must show that $P(k) \Rightarrow P(k+1)$.
Starting from the left-hand side of $P(k+1)$:
$$\text{(expression involving }k+1\text{)}$$
$$= \dots \quad \text{(algebraic steps)}$$
$$\le \dots \quad \text{(using the induction hypothesis)}$$
$$= \text{(right-hand side of }P(k+1)\text{)}.$$
Conclude with:
- Therefore, if $P(k)$ holds, then $P(k+1)$ holds.
4. Conclusion
Once both parts are established:
- State clearly that by mathematical induction, $P(n)$ holds for all integers $n \ge n_0$.
A typical final line:
- Therefore, by mathematical induction, the statement $P(n)$ holds for all integers $n \ge 1$.
A Standard Example: A Formula for a Sum
Consider the statement:
$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} \quad \text{for all integers } n \ge 1.$$
Define $P(n)$ to be:
$P(n)$: $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.
We prove $P(n)$ for all $n \ge 1$ by induction.
Base Case
Take $n = 1$.
Left-hand side: $1$.
Right-hand side:
$$\frac{1(1+1)}{2} = \frac{2}{2} = 1.$$
So $P(1)$ is true.
Induction Hypothesis
Assume $P(k)$ is true for some integer $k \ge 1$:
$$1 + 2 + \dots + k = \frac{k(k+1)}{2}.$$
Induction Step
We must show that $P(k+1)$ is true:
$$1 + 2 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}.$$
Start from the left-hand side:
\[
\begin{aligned}
1 + 2 + \dots + k + (k+1)
&= \left(1 + 2 + \dots + k\right) + (k+1) \\
&= \frac{k(k+1)}{2} + (k+1) &&\text{(by the induction hypothesis)} \\
&= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\
&= \frac{(k+1)(k+2)}{2}.
\end{aligned}
\]
This is exactly the right-hand side of $P(k+1)$, so $P(k+1)$ is true.
Conclusion
Since $P(1)$ is true, and $P(k) \Rightarrow P(k+1)$ for all $k \ge 1$, it follows by mathematical induction that
$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$
for all integers $n \ge 1$.
What Makes Induction Different from Direct Proof
In a direct proof, you usually start from the hypothesis for a specific $n$ and argue directly to the conclusion for that same $n$.
In an induction proof:
- You prove two things: the base case and the “step” from $k$ to $k+1$.
- The induction hypothesis is a general assumption about an arbitrary $k$, not about a fixed, specific number.
- You never check each $n$ individually; instead, you show that truth “propagates” from one integer to the next.
This propagation is what lets you conclude the statement holds for all integers in the range, even though you only checked one base case directly.
Common Uses of Induction
Induction appears in many contexts, including:
- Formulas for sums or products
For example:
- Sum of first $n$ odd numbers.
- Sum of a geometric series.
- Inequalities involving $n$
For example: showing that some function of $n$ is always less than or greater than another function once $n$ is large enough.
- Properties of recursively defined sequences
If a sequence is defined in terms of previous terms (like $a_{n+1}$ expressed using $a_n$), induction matches this “step-by-step” nature.
- Number theory statements indexed by $n$
For example, divisibility properties such as:
- $2^n - 1$ is divisible by some integer (under certain conditions).
- A certain number divides a sum or product for every $n$.
You do not need to explore these topics deeply here; the important point is recognizing when a statement is naturally about “all integers from some point onward,” making induction a natural tool.
Weak (Simple) vs Strong Induction
The form used so far is sometimes called weak induction or simple induction:
- Assume $P(k)$ is true.
- Prove $P(k+1)$.
There is another closely related form called strong induction.
Strong Induction
In strong induction, the induction hypothesis is stronger:
- You assume $P(n_0), P(n_0+1), \dots, P(k)$ are all true.
- You then show $P(k+1)$ must also be true.
The structure:
- Base case: Prove $P(n_0)$.
- Induction hypothesis: Assume $P(n_0), P(n_0+1), \dots, P(k)$ are true.
- Induction step: Using that whole collection of assumptions, prove $P(k+1)$.
Logically, simple and strong induction are equivalent: everything you can prove with one you can also prove with the other. In practice, strong induction is often more convenient when $P(k+1)$ depends on several of the previous cases, not just $P(k)$ alone.
Typical Pitfalls and How to Avoid Them
When writing induction proofs, beginners commonly make a few errors. Recognizing them helps you avoid them.
1. Skipping or Mishandling the Base Case
If you do not prove the base case, the whole induction fails, no matter how good the induction step is. You must:
- State the base case clearly.
- Show the statement actually holds there.
Do not say “obvious” without justification, especially in a formal context.
2. Using What You Want to Prove
In the induction step, you must only assume $P(k)$, not $P(k+1)$ or “the statement holds for all $n$.” Be careful not to sneak $P(k+1)$ into your algebra by rearranging it as if it were already true.
A safe pattern is:
- Start from the left-hand side of $P(k+1)$.
- Use algebra and the induction hypothesis (which is $P(k)$).
- Reach the right-hand side of $P(k+1)$.
Avoid starting with something like “Assume $P(k+1)$ and transform it into the induction hypothesis,” unless you later justify that this step is reversible; for beginners, it is better to stick to the direct direction.
3. Not Stating the Induction Hypothesis
Always write a sentence like:
- “Assume for some integer $k \ge n_0$ that $P(k)$ is true, that is, assume …”
This makes it clear what you are allowed to use.
4. Confusing Induction with Checking a Few Cases
Checking $P(1), P(2), P(3)$ and stopping is not induction. The key is to show that if $P(k)$ holds for an arbitrary $k$, then $P(k+1)$ holds. That is what lets the truth spread to all integers beyond the base case.
Variations: Different Starting Points and Multiple Base Cases
Not all induction proofs start at $n = 1$.
- If the statement is only meaningful or true starting from some $n_0 > 1$, you start the induction at $n_0$.
- Occasionally, the induction step goes from $k$ to $k+2$ or some other jump. Then you need enough base cases to “cover” all integers in the range.
For example, if you prove $P(k) \Rightarrow P(k+2)$, you will often need:
- Base case 1: Prove $P(1)$.
- Base case 2: Prove $P(2)$.
Then, $P(1)$ gives $P(3)$, which gives $P(5)$, and so on; $P(2)$ gives $P(4)$, $P(6)$, etc., so all integers $\ge 1$ are covered.
The general principle:
- The induction step tells you how truth moves from one index to others.
- You must choose enough base cases so that repeated application of the step eventually reaches every integer in the claimed range.
Recognizing When to Use Induction
You should consider induction when:
- The statement is indexed by an integer $n$ (“for every natural number $n$ …”).
- There is a recursive or stepwise aspect:
- Definitions that use $n-1$ or earlier terms.
- Formulas built from sums or products up to $n$.
- Statements about “breaking something into $n$ parts,” “building something with $n$ steps,” etc.
Often, if you can see how the case $n+1$ relates to the case $n$, induction is a natural fit.
Writing Style for Induction Proofs
A clear induction proof usually:
- Names the statement: “Let $P(n)$ be …”
- Labels the two main parts explicitly:
- “Base case” or “Initial step”
- “Induction hypothesis” and “Induction step”
- Ends with a sentence such as:
- “Therefore, by mathematical induction, $P(n)$ holds for all integers $n \ge n_0$.”
This structure signals to the reader that you are using induction and that you understand each component of the argument.
In later work, especially in more advanced mathematics, writers may abbreviate some of this. When learning, however, it is helpful to practice the full, explicit structure until it feels natural.