# Prove a bijection between $\mathbb{N}^2$ and $\mathbb{N}$. [duplicate]

Prove that the function $$f(m,n)=\frac{1}{2}\left(m^2+2 m n+n^2+m+3 n\right)$$ is a bijection between $$\mathbb{N}^2$$ and $$\mathbb{N}$$.

The problem arose in a series problem. I have to show that for each couple $$(m,n)$$ we get a different natural number and that all natural numbers are got applying $$f$$.

Below an example of what happens for $$m,n$$ from $$0$$ to $$6$$

$$\begin{array}{ccccccc} 0 & 2 & 5 & 9 & 14 & 20 & 27 &\ldots\\ 1 & 4 & 8 & 13 & 19 & 26 & 34 &\ldots\\ 3 & 7 & 12 & 18 & 25 & 33 & 42 &\ldots\\ 6 & 11 & 17 & 24 & 32 & 41 & 51 &\ldots\\ 10 & 16 & 23 & 31 & 40 & 50 & 61 &\ldots\\ 15 & 22 & 30 & 39 & 49 & 60 & 72 &\ldots\\ 21 & 29 & 38 & 48 & 59 & 71 & 84 &\ldots\\ \ldots\\ \end{array}$$

• See, your table is just numbered by upward antidiagonals. Oct 7 '20 at 10:51
• Don't you see a pattern in your example? Oct 7 '20 at 10:51
• @QiZhu For sure! How to translate this "intuition" in a formally correct way? Oct 7 '20 at 10:59
• It might help to note that $f(m,n)=T_{m+n}+n$ where $T_k$ is the $k^{\textrm{th}}$ triangular number. Oct 7 '20 at 11:02
• @Physor This has nothing to do with number theory. Oct 7 '20 at 11:19

Here is a rigorous proof, but first we rewrite $$f$$:

$$f(m,n) = \frac12(m^2+2mn+n^2 + m + 3n) = \frac12((m+n)(m+n+1)+2n)$$

$$\Large \textbf{Injectivity}$$

Suppose we have $$f(m,n) = f(a,b)$$. Then $$(m+n)(m+n+1)+2n = (a+b)(a+b+1)+2b$$.

First, suppose $$m+n\ne a+b$$. WLOG suppose $$m+n > a+b$$. Then:

\begin{align}(m+n)(m+n+1)+2n &\ge (a+b+1)(a+b+2)\\&=(a+b)(a+b+1)+2a+2b+2 \\&>(a+b)(a+b+1)+2b \\&= (m+n)(m+n+1)+2n\end{align}

which is a contradiction. Hence $$m+n=a+b$$.

Using this fact we have $$2n=2b$$, and hence $$(m,n) = (a,b)$$.

$$\Large \textbf{Surjectivity}$$

Your table provides a great insight: $$f(m,0)$$ are precisely the triangular numbers, and $$f(m-1, n+1) = 1+f(m,n)$$ for $$m > 0$$.

We can prove this by: $$f(m,0) = \frac12(m^2+m) = T_m$$ \begin{align}f(m-1,n+1) &= \frac12((m-1+n+1)(m-1+n+1+1)+2(n+1))\\&=\frac12((m+n)(m+n+1)+2n)+1\\&=f(m,n)+1\end{align}

Now take any $$x\in \mathbb N$$. We can find a triangular number $$T_k = \frac{k(k+1)}2$$ such that $$T_k \le x < T_{k+1}$$.

Intuitively this $$k$$ would be $$m+n$$, and we need to shift over by $$x-T_k$$ numbers.

That is, notice that:

$$f(k-x+T_k, x-T_k) = \frac12((k)(k+1)+2(x-T_k))= T_k+x-T_k=x$$

This shows surjectivity.

• @halrankard2 Good point. Comment added. Oct 7 '20 at 11:28
• Thank you. This is the problem which generated my question math.stackexchange.com/questions/3853798/… Oct 7 '20 at 11:28

Your nice picture is the key.

We can formalize the picture. Each of the following is verified via a straightforward computation.

• $$f(0,0) = 0$$.
• $$f(m+1, n-1) = f(m,n) + 1$$ if $$n \geq 1$$.
• $$f(m+1, 0) = f(0,m) + 1$$.

However, these equations imply exactly the intuition from the picture. We start at $$f(0,0) = 0$$. Going "up-right" is an increment by 1. Once we reach the top and go down again, we increment by 1 again. Therefore, we hit $$\mathbb{N}$$ exactly by following the diagonal path.

If for $$m+n=k-1$$, ($$k$$ is fixed) the function gives the diagonal of $$k$$ consequentive numbers, then for $$m+n=k$$ should be proven to give the next diagonal of $$k+1$$ consquetive numbers.

Indeed, for $$m = k-n-1$$

\begin{align} f(k-n-1,n)&=\frac{1}{2}\left((k-n)^2+2 (k-n) n+n^2+(k-n)+3 n\right) \\ &=\frac{1}{2}k(k - 1)+ n, \qquad n \in \{ 0,1,\cdots,k-1 \}\\ \end{align} In particular, for $$n = k-1$$ we get $$f(k-(k-1),k-1) = f(1,k-1) = \frac{1}{2}k(k + 1) -1$$ For $$m+n=k$$ \begin{align} f(k-n,n)&=\frac{1}{2}\left((k-n)^2+2 (k-n) n+n^2+(k-n)+3 n\right) \\ &=\frac{1}{2}k(k + 1)+ n, \qquad n \in \{ 0,1,\cdots,k \}\\ \end{align} In particular, for $$n=0$$ $$f(k,0) = f(1,k-1) = \frac{1}{2}k(k + 1) = f(1,k-1) + 1$$