Proof of the associativity of addition by induction

Proof

We argue by induction on $c$. Let $S$ be the successor function. The addition satisfies $x + 0 = x$ and $x + S(y) = S(x + y)$ for all natural numbers $x$ and $y$. Fix natural numbers $a$ and $b$.

1. For $c = 0$: the definition gives $(a + b) + 0 = a + b$.
2. Also $b + 0 = b$, so $a + (b + 0) = a + b$. Thus $(a + b) + 0 = a + (b + 0)$.
3. Suppose that $(a + b) + c = a + (b + c)$ for some natural number $c$.
4. By the definition, $(a + b) + S(c) = S((a + b) + c)$.
5. By the hypothesis of step 3, $S((a + b) + c) = S(a + (b + c))$.
6. By the definition, $S(a + (b + c)) = a + S(b + c)$.
7. By the definition again, $S(b + c) = b + S(c)$, so $a + S(b + c) = a + (b + S(c))$.
8. Steps 4 to 7 give $(a + b) + S(c) = a + (b + S(c))$.
9. Since $S(c) = c + 1$, induction gives $(a + b) + c = a + (b + c)$ for every natural number $c$. As $a$ and $b$ were arbitrary, the law holds for all $a$, $b$ and $c$.