Induction is not a magic trick. It is a proof pattern for statements that are meant to hold for every natural number.
The same chapter also uses recursive definitions for addition and multiplication, so it helps to keep the base case and the step visible all the time.
Recursive addition
Definition
Recursive definition of addition
For natural numbers a and b, addition is defined by:
This is a recursive definition. You know the result when the second input is
0, and every later value is built from an earlier one.
Worked example
Compute from the definition
Write and .
Then:
.
That is the number usually called 5.
Common mistake
A recursive formula is not yet a proof
The formulas tell you how the operation is defined. They do not automatically prove a claim about all natural numbers. For that, you still need induction.
Recursive multiplication
Multiplication is introduced in the same recursive style. Once addition is available, multiplication can be read as repeated addition controlled by the second input.
Definition
Recursive definition of multiplication
For natural numbers a and b, multiplication is defined by:
The base case says that adding a zero times gives 0. The step says that if
you already know a · b, then multiplying by the successor S(b) adds one
more copy of a.
Worked example
Compute 3 · 2 from the definition
Write . Then
and
Therefore
The familiar interpretation “three, taken two times” is recovered from the recursive rule.
What induction proves
The induction principle is the reason recursive definitions can support ordinary algebraic laws. A typical proof has the following shape.
Theorem
Induction principle
Let P(n) be a statement about a natural number n. If:
P(0)is true, and- whenever
P(n)is true,P(S(n))is also true,
then P(n) is true for every .
The base case attaches the statement to the starting point 0. The induction
step proves that truth is preserved when we move one successor forward. The two
parts together rule out the possibility that the statement holds at first but
then fails later.
Watch the proof pattern
The stepper below separates one induction proof into the base case, the induction hypothesis, the induction step, and the conclusion.
Read and try
Trace one induction proof
The live stepper separates a proof by induction into its three moving parts.
Claim
Claim: for every natural number n, 0 + n = n.
A proof sketch
Proof
Why follows by induction on b
Proof
Why is not a theorem but a definition
Algebraic laws come after the definitions
Once addition and multiplication have been defined recursively, the familiar laws of arithmetic become theorems.
Theorem
Examples of arithmetic laws proved by induction
For natural numbers a, b, and c, one proves:
and
The important point is the order of logic: we first define the operations, then prove that they behave like the operations we already know.
Proof
Proof structure for distributivity
Quick checks
Quick check
What is the base case in the recursive definition of addition?
Think about which input is fixed first.
Solution
Answer
Quick check
What is the base case in the recursive definition of multiplication?
Look at the second input.
Solution
Answer
Quick check
Using the recursive rule, what is a · S(b)?
State the next multiplication value in terms of the previous one.
Solution
Answer
Quick check
In an induction proof, what is the induction hypothesis?
Use one short sentence.
Solution
Answer
Read this first
If you want the formal setup for the natural numbers, review 3.1 Natural numbers and Peano's axioms.