Cantor配对函数

hbghlyj

如何证明Wikipedia和MathWorld的两个表达式
$$w=\left[\sqrt{8 z +1} -1\over2\right]$$与$$w=\left[\sqrt{2z} -\frac12\right]$$
对$z$为整数的值相同

Aluminiumor

原文应该是向下取整的 $\lfloor\quad\rfloor$
设
$$m=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor,n=\left\lfloor\frac{\sqrt{8z}-1}{2}\right\rfloor$$
则
$$\frac{\sqrt{8z+1}-1}{2}-1<m\leq\frac{\sqrt{8z+1}-1}{2}$$
$$\Longrightarrow m^2+m<2z<m^2+3m+2$$
同理可知
$$n^2+n+\frac14<2z<n^2+3n+\frac94$$
又 $m,n\in\mathbb{N}$
若 $n>m \Longleftrightarrow n\geq m+1$ 则
$$2z>(m+1)^2+(m+1)+\dfrac14>m^2+3m+2>2z$$
矛盾.
若 $n<m \Longleftrightarrow n\leq m-1$ 则
$$2z<(m-1)^2+3(m-1)+\dfrac94<m^2+m+1\leq2z$$
矛盾.
故 $m=n$.