Finding inverse of $g:\mathbb N × \mathbb N \to \mathbb N$

Question

Let function $g:\mathbb N × \mathbb N \to \mathbb N$
$$g(x,y) = \frac{(x+y)(x+y+1)}{2}+y$$ I want to prove that $g$ is bijective. I tried to prove it is injective by contrapositive, but I had some difficulties proving its surjection.
Also, I don't know how to derive its inverse function.
I know that given a number $z$, I have to find the closest triangular number less than or equal to $z$, and change the $y$ value to make the equation hold, but it's somehow difficult to me to translate that into some math language.
Any help will be appreciated.

Answer 1

Given a natural $z$, I tried to find the only $x,y \in \mathbb{N}$ such that verify your equation and since I constructed $x,y$ in terms of $z$ it will be easy to finde the inverse function just by reverse ingenering this process.

Notice that $\frac{(x+y)(x+y+1)}{2} = \binom{x+y}{2}$ which is also the sum of the first $x+y$ natural numbers.

Let $z ∈ \mathbb{N}$ Let $T_n < z$ the greatest triangular number such that $T_n < z$. Now let $y = z-T_n$. Now we must find the only $x$ that could be correct. Since $T_n = \binom{n+1}{2} = \binom{x+y}{2}$ we have $x = n-y+1$.

At this point, the only thing we need to prove the uniqueness of $x$ and $y$ but first, lets give the inverse function:

$$ f^{-1}(z) = (n-y+1,z-T_n) \text{ where } T_n \text{ is the greatest triangular number lower than z} $$

With that out of the way, allow me to prove those are the unique $x,y$ posibble. Suppouse there are $(x,y)$ and $(x',y')$

Let $T_n$ and $ y = z-T_n$ with the same hypothesis above. Let $T_m$ and $y' = z-T_m$ be another triangular number with $m<n$. Clearly $y \neq y'$.

Let $α = T_n - T_m = \sum_{k = m+1}^n$ then $y' = \alpha + y = \sum_{k = m+1}^n + y$. Now we will find $x'$ the same way we did before.

$T_m = \binom{m+1}{2} = \binom{x'+y'}{2}$ hence $m+1 = x' + y' \Rightarrow x' = m+1-y' = m+1 - y - \sum_{k = m+1}^n < 0$ thus $x'$ is not a natural number.

Answer 2

If $g(z)=\frac{z(z+1)}{2},$ then your function is $$f(x,y)=g(x+y)+y.$$

Essentially, this is a composition of two bijections. Let $X=\{(z,y)\in\mathbb N^2\mid z\geq y\}.$ You get the easy bijection $\mathbb N\times\mathbb N\to X$ sending $(x,y)\mapsto (x+y,y)$ and the slightly harder bijection $X\to \mathbb N$ defined by $(z,y)\mapsto g(z)+y.$

Note that $g(z+1)-g(z)=z+1.$

More generally, given any strictly increasing function $g_0:\mathbb N\to\mathbb N$ with $g_0(0)=0,$ we can define find a bijection between $$X_0=\{(z,y)\in\mathbb N^2\mid 0\leq y< g_0(z+1)-g_0(z)\}$$ to $\mathbb N$ defined by $h(z,y)= g_0(z)+y.$

This is onto because for every $n\in \mathbb N$ there is a $z$ such that $g_0(z)\leq n<g_0(z+1),$ and we can take $y=n-g_0(z)\in X_0.$

Showing it is onto is not much harder.

If two pairs $(z_i,y_i)\in X_0,$ $i=1,2$ have the same image $n$ under $h,$ then $z_1=z_2,$ since $g(z_i)\leq n<g(z_i+1)$ and the intervals $[g_0(z),g_0(z+1))$ are disjoint, so $n$ can’t be in two of them.

Once you have the two $z_i$ equal, you get that $y_i=n-g(z_i)$ are equal.

---

In our case, we can get an explicit formula, but it isn’t very instructive. Given $n,$ we find a formula for the largest $z$ such that $n\geq \frac{z(z+1)}2.$

We have $$8n+1\geq (2z+1)^2,$$ or $$\frac{\sqrt{8n+1}-1}{2}\geq z.$$ So we can compute the inverse via $$\begin{align}z(n)&=\left\lfloor \frac{\sqrt{8n+1}-1}2\right\rfloor,\\y(n)&=n-\frac{z(n)(z(n)+1)}2,\\x(n)&=z(n)-y(n) \end{align} $$