Proving that the function $g\left(n,m\right)=\frac{1}{2}\left(n-1\right)n+m$ is bijective

Question

Let $X=\left\{ \left(n,m\right)\in\mathbb{N}\times\mathbb{N}:n\geq m\right\}$ and let $g:X\rightarrow\mathbb{N}$ be defined by $\left(n,m\right)=\frac{1}{2}\left(n-1\right)n+m$. I want to show that $f$ is a bijection. I want to use techniques which only use the basic properties of $\mathbb{N}$, such as induction, well ordering, etc. Unique factorization is also not allowed. I am having trouble showing that $f$ is a bijection.

Answer 1

The function $f : \mathbb{N} \to \mathbb{N} \cup \lbrace 0 \rbrace, f(n) = \frac{(n-1)n}{2}$ is strictly monotonically increasing such that $f(1) = 0$ and $f(n) + n = f(n+1)$. Hence for each $k \in \mathbb{N}$ there exists a unique $n \in \mathbb{N}$ such that $f(n) < k \le f(n+1)$. We obtain $k = f(n) + (k - f(n))$, where $1 \le k - f(n) \le f(n+1) - f(n) = n$. With $m = k - f(n)$ we get $k = g(n,m)$. This shows that $g$ is surjective. As we have seen, $n$ and $m = k - f(n)$ are uniquely determined by $k$ which shows that $g$ is injective.

You can generalize this as follows: Take any strictly monotonically increasing function $f : \mathbb{N} \to \mathbb{N} \cup \lbrace 0 \rbrace$ such that $f(1) = 0$. Define $X(f) = \lbrace (n,m) \in \mathbb{N} \times \mathbb{N} \mid m \le f(n+1) - f(n) \rbrace$. Then $f^\ast : X(f) \to \mathbb{N}, f^\ast(n,m) = f(n) + m$ is a bijection.

Answer 2

We can show $f$ is a bijection by showing there is an inverse function.

Consider $h:\mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ defined by $h(k) = (n(k), m(k))$ where

$n(k)=\max \{r:\frac{1}{2}r(r-1)<k\}$

and

$m(k)=k-n(k)$

Then $1 \le m(k) \le n(k)$ because $\frac{1}{2}n(n-1) + n + 1= \frac{1}{2}(n+1)n + 1$. So the range of $h$ is actually $X$, and we have

$f(h(k))=k$

and

$h(f(n,m)) = (n,m)$

Answer 3

Given any positive integer, it can be written as the sum $$\sum_{i=1}^{n-1}{i}+m,$$ where $m\le n.$ We prove this by induction.

Suppose for the positive integer $N$, we have $$N=\frac{(n-1)n}{2}+m,$$ where $m\le n$. Then we have that $$N+1=\frac{(n-1)n}{2}+m+1=\frac{n^2-n}{2}+n+(1-n+m)=\frac{n(n+1)}{2}+(m-n+1).$$ From the inequality $m\le n$ of the inductive hypothesis we obtain $m-n\le 0<n\implies m-n+1\le n+1.$ Obviously, $1$ can be written in this form. Thus, the function is surjective.