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}$ ?
 A: Here are two arguments.  The first should make the statement "visually obvious" while the second is more formal.
Construct a grid displaying the value of $\phi(n,k)$ for each value of $n$ and $k$:
$$\begin{matrix}
  \color{red}{\phantom{k={}}4}&14\cr
  \color{red}{\phantom{k={}}3}&9&13\cr
  \color{red}{\phantom{k={}}2}&5&8&12\cr
  \color{red}{\phantom{k={}}1}&2&4&7&11\cr
  \color{red}{n=0}&0&1&3&6&10\phantom{=n}\cr
  &\color{blue}{0}&\color{blue}{1}&\color{blue}{2}&\color{blue}{3}&\color{blue}{\!\!\!\!\!\!\!\!4\rlap{{}=k}}
\end{matrix}$$
This should make it pretty clear what is going on.  A formal proof could be as follows.
First, suppose that $n_1+k_1>n_2+k_2$.  Since we are talking about integers, this means that $n_1+k_1\ge n_2+k_2+1$ and we have
$$\eqalign{\phi(n_1,k_1)
  &=\tfrac12(n_1+k_1+1)(n_1+k_1)+n_1\cr
  &\ge\tfrac12(n_2+k_2+2)(n_2+k_2+1)+n_1\cr
  &=\tfrac12(n_2+k_2+1)(n_2+k_2)+n_2+k_2+1+n_1\cr
  &>\phi(n_2,k_2)\ .\cr}$$
Now suppose that $\phi(n_1,k_1)=\phi(n_2,k_2)$.  By the above argument we cannot have $n_1+k_1>n_2+k_2$, by a symmetrical argument we cannot have $n_2+k_2>n_1+k_1$, therefore $n_1+k_1=n_2+k_2$.  Hence
$$\eqalign{\phi(n_1,k_1)=\phi(n_2,k_2)\ 
  &\Rightarrow\ \tfrac12(n_1+k_1+1)(n_1+k_1)+n_1=\tfrac12(n_2+k_2+1)(n_2+k_2)+n_2\cr
  &\Rightarrow\ \tfrac12(n_1+k_1+1)(n_1+k_1)+n_1=\tfrac12(n_1+k_1+1)(n_1+k_1)+n_2\cr
  &\Rightarrow\ n_1=n_2\ ,\cr}$$
and so $k_1=k_2$.  Thus $\phi$ is injective.
A: You should really make a drawing. The function enumerates the pairs $(n,k)$ in a diagonal manner. Note that $$(0,0)\mapsto 0,(0,1)\mapsto 1,(1,0)\mapsto 2, (0,2)\mapsto 3,(1,1)\mapsto 4,(2,0)\mapsto 5,\ldots$$
Thus, at least empirically, the function is enumerating $\Bbb N\times\Bbb N$ by travesing the $(n,k)$ grid diagonally from the upmost right. Having this in mind, try to produce a proof that this function is in fact a bijection. One way to go is to note how the function behaves when $n+k$ is constant. You can partition $\Bbb N\times\Bbb N$ into the sets $$S[m]=\{(n,k):n+k=m\}$$
and then show that the image of $S[m]$ under your function is the interval (in $\Bbb N$!) $$\left[\binom{m+1}2, \binom {m+2}2-1\right]$$ in increasing order, thus proving your function is a bijection. 
This shouldn't prove too difficult since when $n+k=m$ you function sends $(n,k)$ to $\binom{m+1}2 +n$, thus you can let $n$ move and keep $n+k=m$. This increases from $n=0$ to $n=m$; when $$\binom{m+1}2+m=\frac{m^2+3m}2=\binom{m+2}2-1$$
A: 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$.
A: It might be easier to start by letting $(n, k)$ be such that $\varphi( \langle n, k\rangle ) = 0$. Then, $(n + k + 1)(n+k) + 2n = 0$, and since $n, k \in \mathbb{N}$, $(n + k + 1)(n + k), 2n \ge 0$, so $2n = n = 0$, so $k = 0$, and since $(n, k) = (0, 0)$, $\varphi$ is injective. 
