Chapter 6: Induction and Deduction
Introduction (High School to First-Year University Level)
6.1 Two kinds of reasoning
The path from premises to a conclusion is called reasoning. Reasoning comes in two broad types.
- Deduction: from general rules to a particular conclusion
- Induction: from particular cases to a general law
The directions are exactly opposite. And the decisive difference is the certainty of the conclusion. In deduction, "if the premises are correct, the conclusion is necessarily correct," whereas induction only reaches "probably correct." This chapter distinguishes the two, shows that every mathematical proof is deductive, and that the confusingly named "mathematical induction" is in fact deduction. Figure 6.1 summarizes the difference in direction and certainty between the two.
6.2 Deduction — from general to particular
Definition: Deduction
Deduction derives a necessary conclusion from generally true premises (rules, axioms, already-proved theorems) using only the rules of logic. If all the premises are correct, the conclusion is necessarily correct (this property is called "valid").
A classic example is the syllogism.
- Major premise: All humans are mortal.
- Minor premise: Socrates is a human.
- Conclusion: Therefore, Socrates is mortal.
If the major and minor premises are correct, the conclusion follows without exception. No new fact has been observed; we are merely extracting content already contained in the premises.
Every mathematical proof is deductive
Taking definitions, axioms, and already-proved theorems as premises and deriving the conclusion by the rules of logic — this is exactly what a mathematical proof is. The direct proof, proof by contrapositive, and proof by contradiction from the earlier chapters are all particular forms of deduction. This is precisely why a mathematical theorem can be asserted with certainty to "hold in all cases."
The strength of deduction is certainty; its limitation is that it cannot produce a new general law that was not already in the premises. The job of finding new laws falls to induction, which we turn to next.
6.3 Induction — from particular to general
Definition: Induction
Induction collects particular observations and examples and conjectures a general law from them. The conclusion is not certain but probable (likely correct), and it can be overturned by a new case.
The basic method of the natural sciences is this induction. "Every crow observed so far has been black, so crows are probably all black." This is not certain, but it has the power to generate new hypotheses.
Conjectures in mathematics also arise from induction
Add up the odd numbers starting from the smallest.
$1 = 1 = 1^2$, $\;1+3 = 4 = 2^2$, $\;1+3+5 = 9 = 3^2$, $\;1+3+5+7 = 16 = 4^2$
From this alone, one can conjecture that "the sum of the first $n$ odd numbers is $n^2$." This is a conjecture by induction; it is not yet a proof.
Induction is thus a powerful tool for discovery. In mathematics, however, a conjecture never becomes a theorem on its own. The next section makes the reason explicit.
6.4 Induction is not a proof
Even if a statement holds for finitely many examples, there is no guarantee that it holds in all cases. A single counterexample brings the general law down. In mathematics, "having checked many examples" is not enough.
Counterexample: Euler's polynomial $n^2 + n + 41$
Compute $f(n) = n^2 + n + 41$:
$f(0)=41$, $f(1)=43$, $f(2)=47$, $\ldots$ — for $n = 0, 1, 2, \ldots, 39$ the value is prime in every case.
With 40 consecutive primes, one is tempted to say "$f(n)$ is always prime." However,
$$f(40) = 40^2 + 40 + 41 = 40(40+1) + 41 = 41 \times 41 = 41^2$$so it is divisible by $41$ and is not prime. The 39 successful cases were overturned at the 40th.
Another famous example
The Fermat numbers $F_n = 2^{2^n} + 1$ are prime for $F_0, F_1, F_2, F_3, F_4$. Fermat conjectured that they are all prime, but Euler showed that $F_5 = 2^{32}+1 = 641 \times 6700417$ is composite. Five examples were not enough.
Induction and deduction divide the labor
None of this makes induction worthless. The division of labor is discovery by induction, justification by deduction. The "sum of odd numbers is $n^2$" from the previous section, too, first arises as a conjecture by induction, and becomes a theorem only once it is proved by deduction (for instance, by mathematical induction). Induction works at the stage of forming a conjecture; deduction works at the stage of settling it.
6.5 "Mathematical induction" is actually deduction
This is the most confusing point. Although "mathematical induction" has the word "induction" in its name, it is not empirical induction but a genuinely deductive method of proof.
The principle of mathematical induction (review)
For a proposition $P(n)$ about the natural numbers, show the following two things.
- Base case: $P(1)$ holds.
- Inductive step: for every $k$, "if $P(k)$ then $P(k+1)$" holds.
Once these two are shown, $P(n)$ holds for every natural number $n$.
Note that here we have not checked finitely many examples. What we checked is only "the first one" and "the universal single step from $k$ to $k+1$" — just two things. From these two alone, by the fifth Peano axiom, the conclusion about all natural numbers follows as a logical necessity. There is no leap anywhere. This is deduction itself. Note that this axiom does not endorse empirical induction ("check a few examples, conclude all"); what it guarantees is only the statement "if the base case and the step for every $k$ both hold, then the whole follows."
| Aspect | Empirical induction | Mathematical induction |
|---|---|---|
| What is checked | finitely many: $n=1,2,\ldots,100$, etc. | $P(1)$ and "$P(k)\Rightarrow P(k+1)$" (two things) |
| Leap to the conclusion | yes (probably all) | none (necessarily all) |
| Certainty of the conclusion | probable | necessary (a proof) |
| Type of reasoning | induction | deduction |
So why is it called "induction"?
Because the domino image — "$P(1)$ makes the next $P(2)$ hold, $P(2)$ makes $P(3)$ hold, …," with validity propagating one after another — evokes induction's building up of particulars. It is a historical remnant; in English, too, it is called mathematical induction. The name is misleading, but the substance is deduction. Its detailed use is covered in the basic-level chapter "Mathematical induction".
6.6 Chapter summary
| Aspect | Deduction | Induction |
|---|---|---|
| Direction | general → particular | particular → general |
| Certainty | always correct (necessary) | probably correct (probable) |
| Role | justification / proof | discovery / conjecture |
| In mathematics | every proof is this | conjecture only (not a proof) |
- A mathematical proof is entirely deductive. That is why it can assert with certainty that something "holds in all cases."
- "Checked many examples" is induction; it grounds a conjecture but is not a proof (the $n^2+n+41$ counterexample).
- Mathematical induction is deduction. Despite its name, it is a certain method of proof with no leap.
Closing the introduction
The introductory concepts are now in place. Confirm your understanding with the next Chapter 7: Exercises, then move on to the concrete proof techniques of the basic level (direct proof, contrapositive, contradiction, and mathematical induction).
Frequently asked questions
Q1: What is the difference between deduction and induction?
A: Deduction derives a necessary conclusion from general rules or axioms; if the premises are correct, the conclusion is necessarily correct. Induction conjectures a general law from particular cases; the conclusion is only probable and can be overturned by a counterexample. Every mathematical proof is deductive.
Q2: Does holding for many examples constitute a mathematical proof?
A: No. Even if a statement holds for finitely many examples, there is no guarantee it holds in all cases. For example, $n^2+n+41$ is prime for $n=0$ through $39$, but at $n=40$ it is a multiple of $41$ and is not prime. Many examples ground a conjecture (induction), but a general deduction is required for a proof.
Q3: Is mathematical induction induction or deduction?
A: Despite the name "induction," mathematical induction is a deductive method of proof. From only the base case $P(1)$ and the inductive step "if $P(k)$ then $P(k+1)$," the fifth Peano axiom (also called the axiom of induction) yields $P(n)$ for all natural numbers as a logical necessity. It is fundamentally different from empirical induction, which settles for finitely many examples.