Little question regarding bijection from $ \mathbb N \times \mathbb N$ to $\mathbb N$ 
I want to make explicit (by a formula) the function $σ : ℕ^2 → ℕ$, defined by the pattern $σ(0,0) = 0, σ(1,0) = 1, σ(0,1) = 2, σ(2,0) = 3, σ(1,1) = 4, σ(0,2) = 5,…$, and prove that σ is bijective.

Looking at the sequence I thought that $σ(i,j) = M(i+j) + j$ with $M(m) = m(m+1)/2 $ should do, but proving that this is a bijection turned out to be more complicated than I expected. Any suggestion?
 A: Well, it's easy to sure $M(k)$ are increasing and unbounded.  So for any $n\in \mathbb N$ there is a unique $k$ so that $M(k) \le n < M(k+1)= M(k) + (k+1)$.  Or in other words $M(k) \le n \le M(k) +k$.
Let $j = n - M(k) \le k$.  Let $i = k - j$ and so $\sigma(i,j)= M(i+j) + j = M(k) + j = n$.
So $\rho$ is surjective.
Suppose $\rho(i,j) = \rho(k,l)$
$M(i+j) + j = M(m+u) + u = C$.  But bear in mind, as we showed above, there is an unique $k$ so that $M(k) \le C < M(k+1)$ that $j < i+j+1$ and $u < m+u + 1$ so $i+ j = m+u =k$.
So $C = M(k) + j = M(k) + u$ so $j = u$.  And so $i = k-j = k-u =m$.
So $(i,j) = (m,u)$.  
So $\sigma$ is injective.
A: I think you're talking about this pairing function. The proof of its bijectivity is on the linked page.. It gives a way to compute the inverse; with examples.
A: Note that $M(m+1) = M(m) + m+1$, so $$\{ \{M(0)=0\}, \{M(1)=M(0)+1,M(1)+1\}, \{M(2)=M(1)+2,M(2)+1,M(2)+2\}, …\}$$ is a partition of $\{0,1,…\}$.
Injectivity: If $$σ(i,j) = σ(i',j') ∈ \{M(i+j),…,M(i+j)+i+j\}∩\{M(i'+j'),…,M(i'+j')+i'+j'\}$$ then 
$$\{M(i+j),…,M(i+j)+i+j\} = \{M(i'+j'),…,M(i'+j')+i'+j'\} ⇒ \\ i+j = i'+j' ⇒ j = σ(i,j) - M(i+j) = σ(i',j') - M(i'+j') = j' ⇒ \\ i = (i+j) - j = (i'+j') - j' = i'.$$
Surjectivity: If $k ∈ \{0,1,…\}$ then $k ∈ \{M(m),…,M(m)+m\}$ for some $m ∈ {0,1,…}$, this means $k = M(m) + j$ and thus $k = σ(i,j)$ with $i = m-j$.
