Proofs Involving The Addition of Natural Numbers - Proof of Associativity

Proof of Associativity

We prove associativity by first fixing natural numbers a and b and applying induction on the natural number c.

For the base case c = 0,

Each equation follows by definition ; the first with a + b, the second with b.

Now, for the induction. We assume the induction hypothesis, namely we assume that for some natural number c,

Then it follows,

(a + b) + S(c)

= S((a + b) + c)

= S(a + (b + c))

= a + S(b + c)

= a + (b + S(c))

In other words, the induction hypothesis holds for S(c). Therefore, the induction on c is complete.