<s>[INST] Show that $\varphi(\langle n, k\rangle) = \frac{1}{2}(n+k+1)(n+k)+n $ is injective How to show that the following function is an injective function?
$ \varphi : \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N} \\
\varphi(\langle n, k\rangle) = \frac{1}{2}(n+k+1)(n+k)+n$
I'm starting with $ \frac{1}{2}(a+b+1)(a+b)+a = \frac{1}{2}(c+d+1)(c+d)+c$, but how am I supposed to show from this equality that $\langle a, b\rangle = \langle c, d\rangle$, where $\langle a, b\rangle \in \mathbb{N}\times \mathbb{N}$ ?
 [/INST] Note that 
$$\begin{align}
\varphi(0, n+k) &= \frac 1 2 (n+k)(n+k+1) \\
&\le \varphi(n,k) \\
&= \frac 1 2 (n+k)(n+k+1) + n \\
&= n + \sum_{i \le (n+k)} i \\
&< \sum_{i \le (n+k+1)} i \\
&= \varphi(0, n+k+1).
\end{align}$$
Suppose $\varphi(a,b) = \varphi(c,d)$. If $a+b < c+d$, then
$$\begin{align}
\varphi(a,b) &< \varphi(0,a+b+1) \\
&\le \varphi(0,c+d) \\
&\le \varphi(c,d), \\
\end{align}$$
so $a+b \ge c+d$. Similarly, $a+b \le c+d$, so $a+b = c+d$. By definition of $\varphi$, we have $a=c$. It follows that 
$$\begin{align}
(a+b)(a+b+1) &= (c+d)(c+d+1) \\
&= c^2 + 2cd + d^2 + c + d \tag{i}\\
&= (c+b)(c+b+1) \\
&= c^2 + 2cb + b^2 + c + b.\tag{ii}
\end{align}$$
Subtracting (ii) from (i),
$$\begin{align}
0 &= (c^2 + 2cd + d^2 + c + d) - (c^2 + 2cb + b^2 + c + b) \\
&= 2c(d-b) + (d^2-b^2) + (d - b) \\
&= 2c(d-b) + (b+d)(d-b) + (d - b) \\
&= (2c+b+d+1)(d-b),\\
\end{align}$$
so $(2c+b+d+1) = 0$ or $(d-b) = 0$. But $(2c+b+d+1) > 0$ as $b,c,d\in \Bbb N$, so we must have $d-b = 0$, which is to say, $b = d$.
</s>