3.2 Induction and recursive arithmetic

The recursive rules tell us how to calculate addition and multiplication. The question in this note is why those rules imply the familiar algebraic laws. The order of proof matters: first establish identities for addition, then use them in multiplication proofs, and only then use cancellation to construct larger number systems.

Recursive addition

Definition

Recursive definition of addition

For natural numbers $a$ and $b$, addition is defined by:

• $a + 0 = a$
• $a + S(b) = S(a + b)$

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 $2 + 3$ from the definition

Write $2 = S(S(0))$ and $3 = S(S(S(0)))$.

Then:

$2 + 3 = 2 + S(S(S(0)))$

$= S(2 + S(S(0)))$

$= S(S(2 + S(0)))$

$= S(S(S(2 + 0)))$

$= S(S(S(2)))$.

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:

• $a \cdot 0 = 0$
• $a \cdot S(b) = (a \cdot b) + a$

The base case says that adding $a$ zero times gives $0$. The step says that if you already know $a \cdot b$, then multiplying by the successor $S(b)$ adds one more copy of $a$.

Worked example

Compute $3 \cdot 2$ from the definition

Write $2 = S(S(0))$. Then

$$3\cdot 2 =3\cdot S(S(0)) =(3\cdot S(0))+3$$

and

$$3\cdot S(0)=(3\cdot 0)+3=0+3=3.$$

Therefore

$$3\cdot 2=3+3=6.$$

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:

1. $P(0)$ is true, and
2. whenever $P(n)$ is true, $P(S(n))$ is also true,

then $P(n)$ is true for every $n\in N$.

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.

Follow an induction argument

The stepper below separates one induction proof into the base case, the induction hypothesis, the induction step, and the conclusion.

Establish the successor identity

Proof: $S(a) + b = S(a + b)$ by induction on $b$

We prove the statement for all $b\in N$.

Base case: when $b = 0$,

$S(a) + 0 = S(a) = S(a + 0)$.

Induction step: assume $S(a) + b = S(a + b)$. Then

$S(a) + S(b) = S(S(a) + b)$ by the recursive rule,

$= S(S(a + b))$ by the induction hypothesis,

$= S(a + S(b))$ by the recursive rule again.

So the statement holds for $S(b)$ whenever it holds for $b$.

Why $a \cdot S(b) = a \cdot b + a$ is a definition

For multiplication, the formula

$$a\cdot S(b)=(a\cdot b)+a$$

is not something proved after multiplication is already known. It is the recursive step that defines multiplication. Later algebraic laws, such as distributivity, are the statements that require induction.

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:

$$a+b=b+a,$$$$a\cdot(b+c)=a\cdot b+a\cdot c,$$

and

$$a\cdot b=b\cdot a.$$

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: associativity of addition

Fix $a$ and $b$, and induct on $c$ for

$$(a+b)+c=a+(b+c).$$

When $c=0$, both sides equal $a+b$ by $b+0=b$ and the defining rule. If the identity holds for $c$, then

$$\begin{aligned} (a+b)+S(c)&=S((a+b)+c)\\ &=S(a+(b+c))\\ &=a+S(b+c)\\ &=a+(b+S(c)). \end{aligned}$$

The second line is the induction hypothesis and the first and last rewrites use the recursive addition rule. Thus addition is associative before it is used to rearrange terms in later proofs.

Proof: $0 \cdot a = 0$

Induct on $a$. The base case is the defining equation $0\cdot 0=0$. If $0\cdot a=0$, then

$$0\cdot S(a)=0\cdot a+0=0+0=0.$$

Hence $0\cdot a=0$ for every natural number $a$.

From a recursive rule to a proof

There are two related but different uses of the successor pattern. A recursive definition tells us how to calculate a new value from an earlier value. An induction proof tells us how to establish a statement for every natural input. The calculation can suggest a theorem, but it does not replace the proof.

Worked example

Compute $2 \cdot 3$ one successor at a time

Using $3=S(S(S(0)))$ and the multiplication rule,

$$\begin{aligned} 2\cdot3 &=2\cdot S(S(S(0)))\\ &=(2\cdot S(S(0)))+2\\ &=((2\cdot S(0))+2)+2\\ &=(((2\cdot0)+2)+2)+2\\ &=((0+2)+2)+2\\ &=2+2+2=6. \end{aligned}$$

Each line reduces the second input until the base case $2\cdot0=0$ is reached. Only then do we simplify the resulting additions.

A complete proof that $0+n=n$

Define $P(n)$ to be the statement $0+n=n$.

For the base case, the recursive addition rule gives $0+0=0$.

For the step, assume $P(n)$, so $0+n=n$. Then

$$0+S(n)=S(0+n)=S(n).$$

The first equality is the recursive definition, and the second uses the induction hypothesis. Therefore $P(S(n))$ follows from $P(n)$. Induction concludes that $0+n=n$ for every $n\in N$.

This proof is small, but it supplies a fact needed by later algebra. It also shows why the induction hypothesis should be written explicitly instead of replaced by an informal phrase such as “the pattern continues.”

Theorem

Addition is commutative after the induction lemmas

For all $a,b\in N$, $a+b=b+a$.

Proof of commutativity of addition

Fix $a$ and induct on $b$.

When $b=0$,

$$a+0=a=0+a,$$

where the first equality is the definition and the second is the lemma $0+a=a$.

Now assume $a+b=b+a$. Then

$$\begin{aligned} a+S(b)&=S(a+b)\\ &=S(b+a)\\ &=S(b)+a. \end{aligned}$$

The middle equality is the induction hypothesis, and the last equality is the successor-on-the-left identity. Thus the claim holds for $S(b)$, completing the induction. The proof is a model for later algebra: first prove the identities forced by the recursive orientation, then use them to establish familiar symmetric laws.

Proof: cancellation in $N$

We prove the left-cancellation law

$$a+b=a+c\quad\Longrightarrow\quad b=c$$

by induction on $a$. When $a=0$, the identity $0+b=0+c$ reduces to $b=c$ by $0+n=n$. For the step, suppose the result is known for $a$, and assume $S(a)+b=S(a)+c$. The successor-on-the-left lemma and injectivity of $S$ give $a+b=a+c$; the induction hypothesis then gives $b=c$. This cancellation theorem is the natural-number fact used when proving transitivity of the integer equivalence relation.

Common mistake

A calculation of several cases is not induction

Computing $2+0$, $2+1$, and $2+2$ checks only three inputs. An induction proof must name an arbitrary $n$, prove the base case, and show how the statement passes from $n$ to $S(n)$.

Checkpoint

What is the difference between a recursive definition and an induction hypothesis?

Mention what each one is allowed to do.

Solution · Answer

A recursive definition gives the value of an operation by reducing an input to a base case. An induction hypothesis is a temporary assumption that a particular statement holds at an arbitrary $n$, used to prove the statement at $S(n)$.

A full induction proof of distributivity

Fix $a$ and $b$, and let

$$P(c):\quad a\cdot(b+c)=a\cdot b+a\cdot c.$$

For $c=0$,

$$a\cdot(b+0)=a\cdot b=a\cdot b+0=a\cdot b+a\cdot0.$$

Assume $P(c)$. Since $b+S(c)=S(b+c)$, the recursive multiplication rule and the induction hypothesis give

$$\begin{aligned} a\cdot(b+S(c)) &=a\cdot S(b+c)\\ &=a\cdot(b+c)+a\\ &=(a\cdot b+a\cdot c)+a\\ &=a\cdot b+(a\cdot c+a)\\ &=a\cdot b+a\cdot S(c). \end{aligned}$$

The penultimate equality uses associativity of addition, itself proved by an earlier induction. Thus $P(S(c))$ follows, and distributivity holds for every natural $c$.

Proof: associativity of multiplication

We prove $(a\cdot b)\cdot c=a\cdot(b\cdot c)$ by induction on $c$, using the already established distributivity and addition laws. The base case is

$$(a\cdot b)\cdot0=0=a\cdot0=a\cdot(b\cdot0)$$

For the step, the induction hypothesis and distributivity give

$$\begin{aligned} (a\cdot b)\cdot S(c) &=(a\cdot b)\cdot c+a\cdot b\\ &=a\cdot(b\cdot c)+a\cdot b\\ &=a\cdot(b\cdot c+b)\\ &=a\cdot(b\cdot S(c)) \end{aligned}$$

The last equality uses the recursive multiplication rule, completing the induction. Positive factors also have positive product: write $r=S(r')$ and $s=S(s')$. Then

$$r\cdot s=r\cdot S(s')=r\cdot s'+S(r')=S(r\cdot s'+r')\ne0.$$

The last step uses recursive addition and the axiom that zero is not a successor. This will justify the signed-representative argument in $Z$.

How commutativity of multiplication is organized

The recursive definition expands the second input, so the identity $a\cdot b=b\cdot a$ cannot be justified by simply swapping symbols in the definition. A useful auxiliary lemma is proved first by induction on $a$:

$$S(b)\cdot a=b\cdot a+a.$$

For $a=0$, both sides are $0$. If the identity holds for $a$, the successor rule for the second input and the induction hypothesis give

$$S(b)\cdot S(a)=S(b)\cdot a+S(b) =(b\cdot a+a)+S(b).$$

Associativity and commutativity of addition, already established from the recursive addition rules, rearrange this to the expression required in the next induction step: using $S(x)=x+1$ and the recursive expansion $b\cdot S(a)=b\cdot a+b$, the target is $b\cdot S(a)+S(a)=b\cdot a+b+a+1=b\cdot a+a+S(b)$. The lemma therefore supplies the missing orientation. Now induction on $b$ proves commutativity: the base case is $a\cdot 0=0=0\cdot a$; for the successor case,

$$a\cdot S(b)=a\cdot b+a=b\cdot a+a=S(b)\cdot a.$$

This proof architecture matters: each rearrangement cites a previously proved addition fact, while each recursive expansion follows the stated definition. It prevents the circular argument that treats multiplication as commutative merely because its notation looks symmetric.

Worked example

Proving $n+1=1+n$ without assuming commutativity

Write $1=S(0)$. First, the recursive rule gives

$$n+1=n+S(0)=S(n+0)=S(n).$$

Now prove $S(n)=1+n$ by induction. At $n=0$, both sides are $S(0)$. If $S(n)=1+n$, then

$$S(S(n))=S(1+n)=1+S(n),$$

where the last equality is the recursive rule. Hence $S(n)=1+n$ for every $n$, and combining the two identities yields $n+1=1+n$.

Quick checks

Checkpoint

What is the base case in the recursive definition of addition?

Think about which input is fixed first.

Solution · Answer

The base case is $a + 0 = a$.

Checkpoint

What is the base case in the recursive definition of multiplication?

Look at the second input.

Solution · Answer

The base case is $a \cdot 0 = 0$.

Checkpoint

Using the recursive rule, what is $a \cdot S(b)$?

State the next multiplication value in terms of the previous one.

Solution · Answer

It is $(a \cdot b) + a$.

Checkpoint

In an induction proof, what is the induction hypothesis?

Use one short sentence.

Solution · Answer

It is the assumption that the claim holds for a fixed natural number $n$, before proving it for $S(n)$.

Read this first

If you want the formal setup for the natural numbers, review 3.1 Natural numbers and Peano's axioms.