Prove commutativity of product in natural numbers

Question

The objective of this excersise it's to demostrate the result known as commutativity in $\mathbb{N}.$

For that it's defined the function p: $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} $

$ p(m,n) = m + ... + m $ (n times)

The formal inductive definition it's as follows:

$$ p(m,n) = \left\{ \begin{array}{l l} m & \quad \text{if n = 1,}\\ p(m,n-1) +m & \quad \text{other case.} \end{array} \right. $$

Prove that for every pair of natural numbers: $$ p(m,n) = p(n,m)$$

as a hint, they tell me to do induction in $max(n,m).$

any sugetions on how to start?

Answer 1

Don't really know how to use $\text{max}$ function — I've done it the other way — may be it will help you.

You have two axioms:
$p(a,1)=a$ — number one,
$p(a,n+1)=p(a,n)+a$ — number two.

Lemma 1: $$p(1,a)=a.$$

Induction.
Base: $p(1,1)=1$ — the first axiom.

Induction hypothesis: $p(1,n)=n$

Induction step:
$p(1,n+1)=p(1,n)+1$ — the second axiom,
$p(1,n)+1=n+1$ — induction hypothesis.

So, $$p(1,n+1)=n+1$$ and Lemma 1 is proved.

Lemma 2 — right-distributive property, $$p(a+b,c)=p(a,c)+p(b,c)$$

Base: $p(a+b,1)=a+b=p(a,1)+p(b,1)$ — the first axiom.

Induction hypothesis: $p(a+b,n)=p(a,n)+p(b,n)$

Step:
$p(a+b,n+1)=p(a+b,n)+(a+b)$ — the second axiom,
$p(a+b,n)+(a+b)=p(a,n)+p(b,n)+(a+b)$ — induction hypothesis,
$p(a,n)+p(b,n)+(a+b)=(p(a,n)+a)+(p(b,n)+b)$ — the associative and commutative laws for addition,
$(p(a,n)+a)+(p(b,n)+b)=p(a,n+1)+p(b,n+1)$ — the second axiom.

So, $$p(a+b,n+1)=p(a,n+1)+p(b,n+1)$$ proved.

Now your Theorem: $$p(m,n)=p(n,m).$$

Base: $p(m,1)=p(1,m)$ — Lemma 1 and the first axiom.

Induction hypothesis: $p(m,n)=p(n,m)$.

Step: $p(m,n+1)=p(m,n)+m$ — the second axiom,
$p(m,n)+m=p(n,m)+m$ — induction hypothesis,
$p(n,m)+m=p(n,m)+p(1,m)$ — Lemma 1,
$p(n,m)+p(1,m)=p(n+1,m)$ — Lemma 2.

We have $p(m,n+1)=p(n+1,m)$ and that's all.

Answer 2

*Assuming the associative and commutative laws for addition.

Lemma: For all $n,m \in \mathbb{N}$: $p(m+1,n)=p(m,n)+n$.
Proof: $p(m+1,n)=\sum_{i=1}^{n}m+1=\sum_{i=1}^{n}m + \sum_{i=1}^{n}1 = p(m,n)+n.$

Let $n \in \mathbb{N}$. For $k=0$:
$$p(n,n+k)=p(n,n)=p(n+k,n)$$ Induction hypothesis ($k \in \mathbb{N} \cup \{0\}$): $$p(n,n+k)=p(n+k,n)$$ Stepping to $k+1$ (Using the above Lemma in the 3rd equality): $$p(n,n+k+1) = p(n,n+k) + n = p(n+k, n) + n \\ = p(n+k+1,n) + n - n = p(n+k+1,n)$$

Since for all $m,n \in \mathbb{N}$ there exists $k \in \mathbb{N} \cup \{0\}$ such that $(m=n+k) \lor (n=m+k)$ holds, we are done. (Note that $k=max(m,n)+max(-m,-n)$ :-)

Answer 3

OUTLINE: Prove $P(u,1)$ is commutative, and $P(u,2)$ is commutative... The strategy is to proceed by induction on the second argument of $P(u,n)$

Obviously $P(u,1)=u=\underbrace{1+\ldots+1}_\text{u times}=\Sigma_{1}^{u}\,1=P(1,u)$
Suppose for some $n \in \mathbb{N}$, $P(u,n)=P(n,u)$ for all $u\in \mathbb{N}$. Consider $n+1$. $P(u,n+1)=\Sigma_{1}^{n+1}\,u=\Sigma_{1}^{n}\,u+u=P(u,n)+u=P(n,u)+u=\Sigma_{1}^{u}\,n+\Sigma_{1}^{u}\,1$. And so by commutativity of addition (I hope you have proved this), the LHS$=\Sigma_{1}^{u}\,n+1=P(n+1,u)$