How to prove properly that $\mathbb{N \times N}$ $\rightarrow$ $\mathbb{N}$ : $(p,q) \rightarrow \frac{(p+q)(p+q+1)}{2} +q$ is a bijection? I tried to show that for : $\frac{(p_1+q_1)(p_1+q_1+1)}{2} +q_1$=$\frac{(p_2+q_2)(p_2+q_2+1)}{2} +q_2$
we have $(p_1,q_1)=(p_2,q_2)$ to prove that it's an injection.
But I obtain  : $p_{1}^{2}+2p_{1}q_{1}+q_{1}^{2}+p_1+3q_1$ = $p_{2}^{2}+2p_{2}q_{2}+q_{2}^{2}+p_2+3q_2$ and I don't know what to do next.
And for surjectivity I have no idea.
Thanks in advance.
 A: Hint: The bijection works as follows
$$(0,0), (0,1), (1,0), (0,2), (1,1),(2,0)...$$
So you first look at the pairs $(x,y)$ so that $x+y=0$ and you order them lexicographically then all pairs so that $x+y=1$ and you order them lexicographically and so on....
A: I suggest plotting the function: draw a $5 \times 5$ grid and place the values of the function into the grid. A distinctive pattern will emerge, and you'll get better results proving that the pattern really is there, and using the pattern to prove bijectivity.
A: I think this link contains a good proof http://www.math.drexel.edu/~tolya/cantorpairing.pdf
I think the best and elegant way is to show its bijection by algebraic methods. 
We need a lemma:
if $ p_{1}+p_{2} < q_{1}+q_{2} $ then $ f(p_{1},p_{2}) < f(q_{1},q_{2}) $
Proof. Let $ k \in N $ be a fixed natural number and let $ p_{1}+p_{2} = k$. Then it's clear that maximum value of $ f(p_{1},p_{2}) $ is $ f(k, 0) $ and minimum value of $ f(p_{1},p_{2}) $ is $ f(0, k) $ . Given that $ p_{1}+p_{2} < q_{1}+q_{2} $, minimum value of $ f(q_{1},q_{2}), \ where \ q_{1}+q_{2} =  k+n, for \ n\geq 1, n \in N $ is $f(0,k+1)$. But this value is still greater than $ f(k,0) $ which is maximum value of $ f(p_{1},p_{2})$. Then we're done. By symmetry $ p_{1}+p_{2} > q_{1}+q_{2} $ then $ f(p_{1},p_{2}) > f(q_{1},q_{2}) $ is also true. 
So, $ f(p_{1},p_{2}) = f(q_{1},q_{2}) $ implies $ p_{1}+p_{2} = q_{1}+q_{2} $. If we keep in mind for example $ p_{1}+p_{2} = q_{1}+q_{2} = k $ then, we easily see, $p_{1}=q_{1}$ and $p_{2}=q_{2}$ which proves that our function is injective.
With respect to surjectivity, assume $ z \in N$. Think about largest triangular number not greater than z, that is $t_{k} = k*(k+1)/2 $ (you may want to draw the diagonals to get some intuition). Then, $ p_{1} = z - t_{k}$ and $p_{2} = k - p_{1}$ will do, that is, $f(p_{1},p_{2}) = z$. Its absent in the link but, you need to prove that $p_{2} \in N$.
Sincerely       
