# Exercise 2.2.1 in Analysis by Terence Tao Induction Proof of Addition Associative Law Natural Numbers

The proposition 2.2.5 and also exercise 2.2.1 of Analysis by Terence Tao is as below:

Show for any natural numbers $$a, b, c$$, we have $$(a+b)+c = a+(b+c)$$ the associative rule

The proof should use induction.

Definition: $$0 + n = n$$ for $$n$$ is a natural number ($$0$$ is also natural number)

Addition definition: $$(n++)+m = (n+m)++$$ where $$n++$$ is increment in n

Lemma 2.2.2: $$n + 0 = n$$

Lemma 2.2.3: $$n+(m++)=(n+m)++$$

Proposition 2.2.4: $$n+m = m+n$$

So my humble attempt is (as I am not really good at math..)

Proof:

To show $$(a+b)+c = a+(b+c)$$

For case = $$0$$ and if we fix $$a$$ and $$b$$ and increment $$c$$

(1) We want to show: $$(a+b)+0 = a+(b+0)$$.

The left hand side is $$(a+b)+0 = a+b$$ using Lemma 2.2.2 and view $$(a+b)$$ as an entity | Right hand side is $$a+(b+0) = a + b$$ also using Lemma 2.2.2 in the fact that $$(b+0) = b$$

So case $$0$$ is proved.

(2) Use induction to show for case $$n$$ this is true

For case = $$1$$: Show $$(a+b)+1 = a+(b+1)$$

Left hand side is $$(a+b)+1 = (a+b)++$$ by definition of Natural Numbers increment if we view $$(a+b)$$ as an entity and $$(a+b)+1$$ is $$1$$ increment of it

Right hand side is $$a + (b+1) = a + (b++) \dfrac{=}{Lemma 2.2.3} (a+b)++$$

So $$(a+b)+1 = (a+b)++ = a+(b+1)$$

For case = $$2$$: Show $$(a+b)+2 = a+(b+2)$$

Left hand side is $$(a+b)+2 = ((a+b)++)++$$ by definition of Natural Numbers increment if we view $$(a+b)$$ as an entity and $$(a+b)+2$$ is $$2$$ increments of it

Right hand side is $$a + (b+2) = a + (b+1)++ = (a+b+1)++ = (a+b++)++ = ((a+b)++)++$$ if keep applying Lemma 2.2.3

So $$(a+b)+2 = ((a+b)++)++ = a+(b+2)$$

$$\vdots$$

For case = $$n$$: Show $$(a+b)+n = a+(b+n)$$

Left hand side is $$(a+b)+n = (((a+b)++)++)\cdots)++$$ by definition of Natural Numbers increment if we view $$(a+b)$$ as an entity and $$(a+b)+n$$ is $$n$$ increments of it where there are $$n$$ signs of $$++$$

Right hand side is $$a + (b+n) = a + (b+(n-1)++) = a + (b+n-1)++ = a + (b+ (n-2)++)++ = a + ((b + (n-2))++)++ = \cdots = ((((a + b)++)++)\cdots)++$$ if keep applying Lemma 2.2.3, and there are $$n$$ signs of $$++$$

So $$(a+b)+n = ((((a + b)++)++)\cdots)++ = a+(b+n)$$

So we know for case = $$n$$ this is also True

(3) Now we only need to show for case = $$n+1$$ is True to complete the induction.

We show: $$(a + b) + n + 1 = a + (b + n + 1)$$ By:

Left hand side $$(a + b) + n + 1 = (a + b) + (n++) = (a + b + n) ++$$ Using Lemma 2.2.3

Right hand side $$a + (b + n + 1) = a + (b + (n++)) = a + ((b+n)++) = (a + b + n)++$$ Keep applying *Lemma 2.2.3**

Thus $$(a + b) + n + 1 = (a + b + n)++ = a + (b + n + 1)$$

Thus the proof is complete.

** Could somebody help me check if the above is a rigorous proof of the associative rule for natural numbers? **

• Apologies but...I haven't reached to multiplication part and I just want to make sure if there's any logical issues with my attempt on the addition's associative rule...Not really using answers from others... – commentallez-vous May 11 at 16:44
• Base case is correct, but for the Induction step you cannot prove $1,2,\ldots$ exactly because what we have to show is how to formalize the "$\ldots$". Thus, assume $(a+b)+n=a+ (b+n)$ and prove $(a+b)+(n++)=a+(b+(n++))$ – Mauro ALLEGRANZA May 11 at 17:01
• Hi Mauro, so for induction, we show case 0 is true. But when we say case n, we are assuming if case n is true, and see if for n+1 is true, and if yes, induction is proved? So we are not really showing for case = 1 ... n is true? – commentallez-vous May 11 at 17:02
• Exactly; having case $n=0$ and having the proof for "if case $n$, then case $(n+1)$", we can use it with $n=0$ to prove $n=1$, and so on. – Mauro ALLEGRANZA May 11 at 17:04
• Ah I see...sorry I was a bad math student...and definitely didn't catch the logic here. I was wondering why Tao was basically using "Suppose" and "Assume" in case = n in his text and thought maybe he was "lazy" haha. But is my case = n+1 okay after assuming case = n is true? – commentallez-vous May 11 at 17:05