Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Towards the end of this, how do I get

$$ \frac{\sqrt{8z + 1} - 1}{2} < w + 1 $$

Here $w = x + y \geq 0, t = (w^2 + w)/2 , z = t + w, x,y \in \mathbb N_{\geq 0}$.

Thanks.

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

In that Wikipedia article it is shown that inverse function to $$f(w)=\frac{w^2+w}2$$ is the function $$f^{-1}(t)=\frac{\sqrt{8t+1}-1}2.$$

These functions are strictly increasing on $[0,\infty)$.

So $$f(w)\le z<f(w+1)$$ implies $$w\le f^{-1}(z)<w+1,$$ which is what you wrote.


I'll add the link to the current revision of the Wikipedia article, so that this post makes sense even in the case the article is changed.

share|improve this answer
    
And how did you get $z = f(w) + y < f(w+1)$? –  Matt N. Oct 28 '12 at 15:10
1  
If I understand their proof correctly, you have the sequence $f(0)=0<f(1)=1<\dots<f(w)<f(w+1)<\dots$ So for a given $z$ there is exactly one $w$ such that $f(w)\le z < f(w+1)$. Then you can find $y$ such that $z=f(w)+y$. –  Martin Sleziak Oct 28 '12 at 16:31
add comment

Actually \begin{eqnarray*} z<\frac{(w+1)(w+2)}{2}&\Leftrightarrow&2z<w^2+3w+2\\ &\Leftrightarrow&2z<\left(w+\frac{3}{2}\right)^2-\frac{1}{4}\\ &\Leftrightarrow&2z+\frac{1}{4}<\left(w+\frac{3}{2}\right)^2\\ &\Leftrightarrow&\frac{\sqrt{8z+1}}{2}<w+\frac{3}{2}\\ &\Leftrightarrow&\frac{\sqrt{8z+1}-1}{2}<w+1 \end{eqnarray*}

share|improve this answer
add comment

Rather than follow the Wikipedia derivation, I’ve produced my own; it’s essentially the same, but I think that it may be a bit easier to follow.

Let $T_n=\binom{n+1}2=\sum_{k=1}^nk$, the $n$=th triangular number. We can write the pairing function as $$\langle x,y\rangle=\frac{(x+y)(x+y+1)}2+y=T_{x+y}+y\;,$$ making it clear that every $\langle x,y\rangle$ is of the form $T_n+k$ for some $n,k\in\Bbb N$ with $k\le n$.

Lemma. Every natural number has a unique decomposition of this form.

Proof. To prove existence, fix $m\in\Bbb N$, let $n\in\Bbb N$ be maximal such that $T_n\le m$, and let $k=m-T_n$. Then $T_n\le m<T_{n+1}$, so $k=m-T_n<T_{n+1}-T_n=n+1$, i.e., $k\le n$.

To prove uniqueness, suppose that $T_m+i=T_n+k$, where $i\le m$ and $k\le n$, and without loss of generality assume that $m\le n$. Then $$i+\sum_{j=1}^mj=k+\sum_{j=1}^nj\;,$$ so $$i-k=\sum_{j=m+1}^nj\;.\tag{1}$$ If $m<n$, this implies that $m>i-k\ge m+1$, so $m=n$, $i-k=0$, and $i=k$. $\dashv$

Inverting the pairing function is then simply a matter of calculating the unique $n$ and $k$ such that $z=T_n+k$ and $k\le n$: once $n$ and $k$ are known, just set $y=k$ and $x=n-k$.

From the proof of the lemma it’s clear that finding $n$ and $k$ boils down to finding the maximal $n$ such that $T_n\le z$, i.e., the unique $n$ such that

$$\frac12n(n+1)\le z<\frac12(n+1)(n+2)\tag{1}\;.$$

The first inequality in $(1)$ can be rewritten $n^2+n\le2z$, or $n^2+n-2z\le0$; over $\Bbb R$ this has the solution

$$\frac{-1-\sqrt{1+8z}}2\le n\le\frac{-1+\sqrt{1+8z}}2\tag{2}$$

from the quadratic formula. The first inequality in $(2)$ says nothing useful, since $n\ge 0$ anyway.

Similarly, the second inequality in $(1)$ becomes $n^2+3n+2-2z>0$, with the solution

$$n<\frac{-3-\sqrt{1+8z}}2\quad\text{or}\quad n>\frac{-3+\sqrt{1+8z}}2\;,\tag{3}$$

where the first alternative is plainly impossible. Combining the useful parts of $(2)$ and $(3)$, we see that

$$\frac{-3+\sqrt{1+8z}}2<n\le \frac{-1+\sqrt{1+8z}}2\;.\tag{4}$$

Let $$\alpha=\frac{-1+\sqrt{1+8z}}2\;;$$ then $(4)$ just says that $\alpha-1<n\le\alpha$, i.e., that $n$ is the unique integer in the range $(\alpha-1,\alpha]$ so that $n=\lfloor\alpha\rfloor$. (If that’s not immediately clear, note that from $\alpha-1<n$ we get $\alpha<n+1$, and we already have $n\le\alpha$.)

The computation of the inverse is now essentially complete. Given $z\in\Bbb N$, let

$$n=\left\lfloor\frac{-1+\sqrt{1+8z}}2\right\rfloor\;;$$

then $z=\langle x,y\rangle$, where $y=z-T_n=z-\frac12n(n+1)$ and $x=n-y$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.