Prove commutativity of product in natural numbers 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?
 A: 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.
A: *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)$ :-)
A: 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)$
