Injective mapping
Task number: 2816
Show that the mapping \(f: \mathbb N\times \mathbb N\to \mathbb N\) defined by the equation \(\displaystyle f(x,y)=\frac{(x+y)(x+y+1)}{2}+y \) is injective.
Hint
First try to arrange the pairs \((x,y)\) such that the value of the function \(f\) increases.
Resolution
Without loss of generality we first consider the case \((x+y)<(x'+y')\). Then
\[ f(x,y)=\frac{(x+y)(x+y+1)}{2}+y=\frac12(x^2+2xy+y^2+x+3y) <\frac12(x^2+2xy+y^2+3x+3y)= \] \[=\frac12(x+y+1)(x+y+2)\le\frac12(x'+y')(x'+y'+1) <\frac{(x'+y')(x'+y'+1)}{2}+y=f(x',y')\] .If \((x+y)=(x'+y')\) and \(y<y'\) we have \(f(x,y)<f(x',y')\) immediately.
In the case that \((x+y)=(x'+y')\) and \(y=y'\) then also \(x=x'\). So the function \(f\) is injective.
