inverting the Pairing function

• Nov 15th 2009, 09:22 PM
dayscott
inverting the Pairing function
Pairing function - Wikipedia, the free encyclopedia

(1) i cant really understand why he is using the triangle number anyway

(2) why is t <= z ?
• Nov 16th 2009, 01:17 AM
Hello dayscott

Welcome to Math Help Forum!
Quote:

Originally Posted by dayscott
Pairing function - Wikipedia, the free encyclopedia

(1) i cant really understand why he is using the triangle number anyway

(2) why is t <= z ?

Why is this true (1): $z = t+y$ ? Because
$t = \frac{w(w+1)}{2}$
$= \frac{(x+y)(x+y+1)}{2}$, since $w = x+y$
$\Rightarrow z =\frac{(x+y)(x+y+1)}{2}+y = t+y$
Why is this true (2): $t \le z$ ? Because
$t=z-y$, and $y$ is a natural number.
As far as your question about triangle numbers is concerned, it is simply that the expression $\tfrac12w(w+1)$ happens to be the sum of the first $w$ natural numbers; which is the $w^{th}$ triangle number.

• Nov 16th 2009, 02:48 AM
dayscott
thx a lot !

another question - the red arrow marks the gap in my thinking ^^: http://uploadz.eu/images/s73wq0xx7c8aurcvgylt.png
• Nov 18th 2009, 09:55 PM
dayscott
no one ? : /
• Nov 18th 2009, 10:24 PM
Hello dayscott

I didn't post a reply earlier, because I can't see it either!

The LHS of the inequality is straightforward enough:
$w=\frac{\sqrt{8t+1}-1}{2}$, which is strictly increasing,

and $t\le z$

$\Rightarrow w\le\frac{\sqrt{8z+1}-1}{2}$
but I can't see where the right-hand part $\frac{\sqrt{8z+1}-1}{2} comes from.

Perhaps someone else may be able to help?