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.
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
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
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.