Symmetric pairing function

Question

I am trying to prove that the integer function: $$ \pi(a,b) = a + \frac{b(b-1)}{2} \qquad 1\leq a < b $$ is a pairing function; which amounts to showing that it is injective. (My end-goal would be to use it as a symmetric pairing function.)

AFAICS, proving that it is injective amounts to showing that given four integers $1\leq a<b$ and $1\leq c<d$, the following implication holds: $$ a + \frac{b(b-1)}{2} = c + \frac{d(d-1)}{2} \quad\Rightarrow\quad a=c \quad b=d $$

I have a feeling that proving this involves finding two inequalities on $a$ and $c$ (or $b$ and $d$), which can only both be true in case of equality. But I am not sure whether this approach is indeed correct, and if so, what these inequalities would be.

So far, using substitution and re-arranging terms, I have reached the following inequalities, which should hold simultaneously: $$ d(d-1) + 2c < b(b+1)\\ b(b-1) + 2a < d(d+1) $$ I like these because of the symmetry between $b$ and $d$, and the assymmetry $x(x-1)$ and $x(x+1)$, but I am not sure about the next steps needed to conclude.

---

Edit: it looks like @Brian_Scott solved this in the comments of this post. However I do not understand the proof just yet.. If anyone could please help flesh it out a little bit more, that would be greatly appreciated.

Answer 1

For $1\leq a< b$ and $1\leq c < d$, suppose: $a + \frac{b(b-1)}{2} = c + \frac{d(d-1)}{2}$ and $(a,b) \neq (c,d)$.

Wlog assume $d>b$ (if they are equal, then $a=c$ and we have a contradiction), then:

$$a -c = \frac{d(d-1)-b(b-1)}{2} = \frac{(d-b)(d+b-1)}{2}\geq \frac{(d+b-1)}{2}> \frac{2b-1}{2}=b-\frac{1}{2}>a$$

Therefore $c < 0$, and we have a contradiction.

Answer 2

You can prove this via contradiction. Suppose $\pi(a,b)=\pi(a',b')$.

First case $b=b'$, show this implies $a=a'$.

Second case, $b < b'$. Hence $b' \ge b+1$. This gives you an inequality for $a-a'$ which yields a contradiction with the assumption $a < b$.

Edit: As $b' \ge b+1$ we have $\frac{b'(b'-1)}{2}-\frac{b(b-1)}{2}\ge \frac{(b+1)b}{2}-\frac{b(b-1)}{2}=b$. Now if $\pi(a,b)=\pi(a',b')$ this gives $a-a'>b$ which contradicts $a <b$ where I used that $b' > b$ implies $a' < a$.