Please explain this basic proof

88 Views Asked by At

In my freshman math course book there's a proof of associativity of addition on the natural numbers using mathematical induction. The author proves the base case and assumes the hypothesis, $a+(b+c) = (a+b)+c$, holds. The inductive step for $c:=c+1$ goes like this: $$a+(b+(c+1)) = a+((b+c)+1) = (a+(b+c))+1 = ((a+b)+c)+1 = (a+b)+(c+1)$$ , which proves the hypothesis.

Here's the question: why is it wrong to directly state $a+(b+(c+1)) = (a+b)+(c+1)$ in the inductive step? It was assumed that $a+(b+c) = (a+b)+c$ is true, here we take the $(c+1)$ from $a+(b+(c+1))$ to be the $c$ from $a+(b+c)$ and just apply $a+(b+c) = (a+b)+c$. What's the fault in my reasoning?

2

There are 2 best solutions below

0
On BEST ANSWER

Make sure you get the assumption of the induction right which is that associativity of addition holds for all natural numbers smaller or equal to c. With only this assumption your task is to show that it holds for c+1. That means you can not take c+1 to be your old c.

2
On

Every step in the version in the book is an instance of the axiom (or whatever) $$x+(y+1)=(x+y)+1.$$Your "direct" $$a+(b+(c+1))=(a+b)+(c+1)$$is simply not an instance of that axiom.