How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?

When showing that $\mathbb{N}\times\mathbb{N}$ is in bijection with $\mathbb{N}$, it seems standard to give a proof by picture that shows a way to systematically weave through all the points in $\mathbb{N}\times\mathbb{N}$ and label each one as you go.

I know there is a polynomial expression for this method, given by $$ J(m,n)=[1+2+\cdots+(m+n)]+m=\frac{1}{2}[(m+n)^2+3m+n] $$ where $m$ is the usual $x$-coordinate and $n$ the usual $y$-coordinate.

But how does one "see" how this formula is arrived at? I know how to manipulate the middle expression to arrive at the rightmost expression, but how does the middle expression relate to the weaving pattern through $\mathbb{N}\times\mathbb{N}$? Thank you.

Solution 1:

To weave all the way to $(m,n)$, you first have $m+n$ complete top-left to bottom-right passes, of which the first contains 1 point $(0,0)$, the second two points $(0,1)$ and $(1,0)$, ..., the $m+n$'th $m+n$ points $(0,m+n-1)$ to $(m+n-1,0)$, and then the $m+1$'th point on the next pass is $(m,n)$.

Solution 2:

Looking at the diagram, the order is lexicographic, first in $m+n$, then in $m$. The motivation is that it is easy to see you get all the points of $\mathbb{N} \times \mathbb{N}$, so now you just need to figure out what $J(m,n)$ is.