# Problem understanding a proof by induction for 2 variables

I will start by giving a background to the problem. In the book I am reading, the existence of the unit element $$e$$ for the multiplication operation on real numbers is given by axioms assumed for reals. Then, we have the positive integers which till now have not been defined as a subset of reals but rather as natural numbers used for counting purposes. Now, the aim is to identify these natural numbers as real numbers.

We define a mapping $$f:Z^+ \to R$$ inductively as, $$f(1)=e$$ and assuming that $$f(n)=ne$$ has been defined, $$f(n+1)=ne+e$$.

We want to prove that $$(m+n)e=me+ne$$ for positive integers $$m,n$$. The proof given uses induction on $$n$$. The base case where $$n=1$$ follows from the definition of $$f$$. Then assuming proved for all positive integers $$\le n$$ and all m, we have $$(m+n+1)e=(m+1+n)e=(m+1)e+ne=me+e+ne=me+(n+1)e$$

What I don't know is how do you justify that it has been proved for all positive integers $$m,n$$? Intuitively, I can see that we know $$f(n+1)=ne+e$$ for any positive integer $$n$$ and so all we have to prove is we can have any positive integer other than $$1$$ in the expression. In this sense, it's a proof in only one variable but is there a better way to justify us doing induction only on $$n$$?

Also, in the proof, why has the assumption been made for all positive integers $$\le n$$? Isn't it enough to assume it just for any positive integer $$n$$ and show it holds for the next integer as we normally do?

• You're assuming nothing special about $m$, so the proof works for every $m$. Commented Jun 4, 2019 at 12:06

## 1 Answer

You're applying induction on the formula with the free variable $$n$$

for every natural number $$m$$, $$(m+n)e=me+ne$$

which you want to be able to prepend “for every natural number $$n$$”. Call $$P(n)$$ that formula.

It seems that your natural numbers start at $$1$$ (not clear why), so the induction scheme is

1. prove “$$P(1)$$”;
2. prove “for every natural number $$n$$, if $$P(n)$$ then $$P(n+1)$$”.

The axiom on induction then says that you have proved “for every natural number $$n$$, $$P(n)$$” that can be so translated into

for every natural number $$n$$, for every natural number $$m$$, $$(m+n)e=me+ne$$

Does it make sense, now?

1. For $$n=1$$ we get $$(m+1)e=me+e=me+1e$$, by definition.
2. Suppose $$(m+n)e=1$$; then $$(m+n+1)e=(m+n)e+e=me+ne+e=me+(n+1)e$$.

Proved.

Your textbook is apparently using strong induction, which doesn't seem necessary here, but the idea is the same; the formula with the free variable $$n$$ becomes

for every natural number $$m$$, for every natural number $$k$$, if $$k\le n$$ then $$(m+k)e=me+ke$$

and the induction scheme is the same.

• I understand your proof but this is different than the proof I have mentioned in the question, and I am not able to understand that. My doubt is that, in that proof, the induction hypothesis is that it is true for all positive integers $\le n$ and all $m$. I don't understand the need to assume it for all positive integers $\le n$. I am also not able to get over the fact that it is assumed it to be true for all $m$. Your proof doesn't have either of these problems as we are proving for a 'general' $m$ and assuming $P(n)$ only for the previous integer to prove for the next. Commented Jun 4, 2019 at 13:30
• @NiketParikh The text uses “strong induction”, which is not really necessary here. But the methods are equivalent. Commented Jun 4, 2019 at 14:14
• Right, so strong induction hypothesis isn't necessary. The other thing I am not comfortable with in the proof is that induction hypothesis assumes the statement is true for all $m$. It has also been used in the proof when $(m+1+n)e$ is written as $(m+1)e+ne$ (this can be split like this because it holds for all $m$ including $m+1$ and for $n$). How can one assume it to be true for all $m$? Shouldn't we be proving this for 'an' $m$ and since there is no special assumption about $m$, conclude it holds for every $m$. Isn't it wrong to assume statement holds for all $m$ before proving it does? Commented Jun 4, 2019 at 14:31
• @NiketParikh There is no “assumption of truth”, actually: you just deduce. Commented Jun 4, 2019 at 14:42
• Could you please elaborate? Commented Jun 4, 2019 at 15:48