Is there an intuitive way to understand $Pair(x,y) = \frac{(x+y)(x+y+1)}{2} + x$?

Question

After a lot of effort I discovered some pattern that the function:

$$Pair(x,y) = \frac{(x+y)(x+y+1)}{2} + x$$

essentially zigzags along the grid with $\mathbf N$ vs $\mathbf N$ (natural numbers). So intuitively, given any P(x,y) we follow the grid path. However, this seems like a very hacky way to understand it. How could someone have come up with this? Where did it come from? It looks nothing at all random and it has very interesting properties like:

1. its bijective
2. its computable (easy to prove)
3. if $Pair(x,y) =a $ then $Right(a) = x \leq a$ and $Left(a) = y < a$.

number 1 and 3 seem especially especial (and I wonder why they are true). But is this property of zigzagging obvious just by looking at the equation? (as well as the other properties)? Should this zigzaging be obvious without brute forcing the computaiton of 100 of these numbers? I am assuming their is some sort of pattern to this function but I can't see it...

---

context: comes up in development of Godel numbering: https://faculty.math.illinois.edu/~vddries/main.pdf

page 85.

Answer 1

Zigzagging is kind of obvious if you look at it in the right way. Pair of $x$ and $y$ is equal to the $(x+y)$th triangle number, plus $x$. The $y$ term is guaranteeing that the "plus $x$" term on the end will not cause the traversal to run more than the full length of the hypotenuse. So $y$ is effectively telling you how tall the triangle is (in the sense of distance from the origin along the line $y=x$ to the hypotenuse), and $x$ is telling you where along the hypotenuse you're located.

Answer 2

Look at it like this:

$$\begin{array} {ccccr} (0, 0)_{\color{red}0} \\ (1, 0)_{\color{red}1} & (0, 1)_{\color{red}2} & \\ (2, 0)_{\color{red}3} & (1, 1)_{\color{red}4} & (0, 2)_{\color{red}5} & \\ (3, 0)_{\color{red}6} & (2, 1)_{\color{red}7} & (1, 2)_{\color{red}8} & (0, 3)_{\color{red}9} & \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}$$

Notice that in each row $x + y$ doesn't change. So if you want the value for $(x, y)$,

• first add up $1 + 2 + \cdots + (x + y)$, which is a simple arithmetic series, it is $\frac12 (x+y)(x + y + 1)$.
• second add the column value, which is just $x$

So you get simply $\frac{(x + y - 1)(x + y - 1 + 1)}{2} + x$.