Surjectivity of an $\mathbb{N}^2$ to $\mathbb{N}$ function (This is my first post on here - let me know if I need to edit anything.)
I'm just starting an introductory topology course and I've come across a problem that I've been trying to solve for a few hours now. I'm supposed to prove the bijectivity of the $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ function $f(i,j)=i+\frac{(i+j-2)(i+j-1)}{2}$. 
Most of my struggle is coming from proving that the function is onto. I understand that I need to find an $i$ and $j$ so that $f(i,j)=z$ $\epsilon$ $\mathbb{N}$, but I'm having a hard time finding definitions of $i$ and $j$ that don't depend on each other. 
And I have a start to a proof of one-to-one, where I started with $f(i,j)=f(h,k)$ and pretty much factored and simplified down to $(i+j)^2-i-3j=(h+k)^2-h-3k$, but I'm not sure where to go from there. 
I think I'm mainly having conceptual problems because the last time I did this sort of proof was in my discrete math course, which was much lower-level. All that aside, any hints would help immensely :)
 A: It is unnecessary to modify the function since it is one-to-one and onto as proposed.
Show that $f(i,j)=i+\dfrac{(i+j-2)(i+j-1)}{2}$ is one-to-one and onto from $\mathbb{N}^2\,\to\,\mathbb{N}$, where $\mathbb{N}=\{1,2,3,\cdots\}$
The onto part is fairly simple since $\left\{\dfrac{(k-2)(k-1)}{2}\right\}_{k=2}^\infty$ is an increasing sequence in $\mathbb{N}\backslash \{1\}$ but achieves a minimum value of $0$ in $\mathbb{Z}$ when $k=1$ and $k=2$.
$$0,1,3,6,10,15,21,28,36,45,55,66,78,\cdots$$
For each $m\in\mathbb{N}$ define ${\langle m \rangle}=\max\left\{k:\frac{(k-2)(k-1)}{2}<m\right\}$ and let $i=m-\dfrac{({\langle m \rangle}-2)({\langle m \rangle}-1)}{2}$ and let $i+j={\langle m \rangle}$.
Then $f(i,j)=i+\dfrac{(i+j-2)(i+j-1)}{2}=i+\dfrac{({\langle m \rangle}-2)({\langle m \rangle}-1)}{2} =m$ 
Using this we can see that, for example


*

*$f(1,1)=1$

*$f(1,2)=2$

*$f(2,1)=3$

*$f(1,3)=4$


Or we can skip ahead and see that for $m=25$, ${\langle m \rangle}=8$ since $\frac{(8-2)(8-1)}{2}=21$ is the largest value of $\frac{(k-2)(k-1)}{2}$ smaller than $25$. So $i=25-21=4$ and $j={\langle m \rangle}-i=8-4=4$. Thus $f(4,4)=25$.
But what if, in the case of $m=25$ rather than letting $i+j={\langle m \rangle}=8$ we let $i+j={\langle m \rangle}-1=7$. Then $i=25-\frac{(7-2)(7-1)}{2}=10$  And since $i+j=7$ then$j=-3$ which is not in $\mathbb{N}$.
To show that the function $f$ is one-to-one it would be necessary to show that for $m\in\mathbb{N}$ if $i+j={\langle m \rangle}-p$ for some $p<{\langle m \rangle}-1$ where $i=m-\dfrac{({\langle m \rangle}-p-2)({\langle m \rangle}-p-1)}{2}$then it would be the case that $j\le0$. This is in fact the case.
Let 
\begin{eqnarray}
j&=&{\langle m \rangle}-p+\frac{({\langle m \rangle}-p-2)({\langle m \rangle}-p-1)}{2}-m\text{ for }1\le p\le {\langle m \rangle}-2\\
&=&{\langle m \rangle}-p+\frac{({\langle m \rangle}-2-p)({\langle m \rangle}-1-p)}{2}-m\\
&=&\frac{({\langle m \rangle}-2)({\langle m \rangle}-1)}{2}+\frac{p^2-p(2{\langle m \rangle}-1)}{2}-m
\end{eqnarray}
Since this must be positive and since $\dfrac{({\langle m \rangle}-2)({\langle m \rangle}-1)}{2}-m<0$ then $\dfrac{p^2-p(2{\langle m \rangle}-1)}{2}$ must be positive for all values of $p$ in the interval $[1,{\langle m \rangle}-1]$. However, that is not the case since $\dfrac{p^2-p(2{\langle m \rangle}-1)}{2}\le0$ for every $p\in[0,2{\langle m \rangle}-1]$. So $j\le0$.
Thus $f$ is one-to-one and onto.
For $m\in\mathbb{N}$, 
\begin{eqnarray}
f^{-1}(m)=\left(m-\langle m\rangle,\frac{3+\sqrt{1+8\langle m \rangle}}{2}-(m-\langle m \rangle)\right)
\end{eqnarray}
For example, find $f^{-1}(53)$.
$\langle 53\rangle=45$ so $i=53-45=8$ and $j=\dfrac{3+\sqrt{1+8(45)}}{2}-8=3$ so $f^{-1}(53)=(8,3)$ which can be verified by substitution back into $f$.
A: The formula you are using in incorrect, because it leads to $f(0,0)=f(1,0)=1$, so that $f$ is not injective.
You could replace it by the following :
$$f:\mathbb{N}^2\to\mathbb{N},(i,j)\mapsto \frac{(i+j)(i+j+1)}{2}+j$$
Here is a proof for the surjectivity of the modified function :
Given $n\in\mathbb{N}$, consider :
$$N=\max\left\{k\in\mathbb{N};\frac{k(k+1)}{2}\le N\right\}$$
$N$ is well defined because $\lim_{k\to\infty}\frac{k(k+1)}{2}=+\infty$
By definition of $N$ whe have :
$$\frac{N(N+1)}{2}\le n<\frac{(N+1)(N+2)}{2}$$
Now consider :
$$q=n-\frac{N(N+1)}{2}\qquad\mathrm{and}\qquad p=N-q$$
It is clear that $q\ge0$. And we have also :
$$p=N-\left(n-\frac{N(N+1)}{2}\right)=\frac{N^2+3N}{2}-n=\frac{(N+1)(N+2)}{2}-n-1\ge0$$
so that $(p,q)\in\mathbb{N}^2$ and $f(p,q)=n$.
