4
$\begingroup$

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} $$

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

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.

$\endgroup$
2
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.