# How to show that this function is bijective [duplicate]

Possible Duplicate:
Proving the Cantor Pairing Function Bijective

Assume I define

$$f: \mathbb N \times \mathbb N \to \mathbb N, (a,b) \mapsto a + \frac{(a + b ) ( a + b + 1)}{2}$$

How to show that this function is bijective? For injectivity I tried to show that if $f(a,b) = f(n,m)$ then $(a,b) = (n,m)$ but I end up getting something like $3(n-a) + (n+m)^2 -(a+b)^2 + m - b = 0$ and don't see how to proceed from there. There has to be something cleverer than treating all possible cases of $a \leq n, b \leq m$ etc.

For surjectivity I'm just stuck. If I do $f(0,n)$ and $f(n,0)$ it doesn't seem to lead anywhere.

## marked as duplicate by Asaf Karagila♦, Martin Sleziak, Rudy the Reindeer, joriki, Grigory MOct 28 '12 at 12:15

• You switched from $f$ to $J$ at some point. – Asaf Karagila Oct 28 '12 at 11:08
• @AsafKaragila Fixed. Now that I know what this function is called I could as well have looked up the proof on the internet. – Rudy the Reindeer Oct 28 '12 at 11:09

Introduce two other functions $$p(z)=z-\frac{n(n+1)}{2}\textrm{ and }q(z)=n-p(z)$$ where $$n=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor$$

You can try to prove $p(f(a,b))=a$ and $q(f(a,b))=b$.

In order to prove this, you can use some 2D diagram for integers because $(f,p,q)$ are actually Pairing functions.

The term $(a+b)(a+b+1)/2$ is the sum of the numbers from $1$ to $a+b$. For a fixed value of $s=a+b$, $a$ ranges from $0$ to $s$, so we need $s+1$ different results for these arguments. Now you can prove by induction that the range from $s(s+1)/2$ to $(s+1)(s+2)/2-1$ contains precisely the images of the pairs with sum $s$.