Proving injectivity of $g(d)= d^2 + d + 1$ by contradiction

Question

Define the function $g:\mathbb N \rightarrow \mathbb N$ with $g(d)= d^2 + d + 1$

I started out by assuming that if two arbitrary elements of $\mathbb N$, $x$ and $y$,where $x>y$ without loss of generality, then $g(x)=g(y)$. So \begin{align*}x^2 + x + 1 &= y^2 + y + 1\\ (x+1)(x-1)&=(y+1)(y-1)\\ x^2 + x &= y^2 + y.\end{align*}

I've tried rearranging the equation like this to try and find the contradiction. Am I on the right track? Any hints or advice would be appreciated.

You may wish to have a look at our basic MathJax tutorial to learn how to typeset math here. — A.P., Mar 27 '15 at 00:33
Well... you would be if it weren't that $(x+1)(x-1) = x^2 - 1 \neq x^2 +x$... what about $x^2 +x = x (x+1)$ instead? — A.P., Mar 27 '15 at 00:41
You can asume that $x\neq y$ and then you have $x+y=-1,$ which is imposible since $x,y\in\Bbb N$ — CIJ, Mar 27 '15 at 00:42
A more efficient way would be to first write $g(d)$ as $g(d)=\left(d+\dfrac{1}{2}\right)^2+\dfrac{3}{4}$ — Prasun Biswas, Mar 27 '15 at 00:42
Suppose that $g(x)=g(y),$ then $x^2+x+1=y^2+y+1$ and hence $(x-y)(x+y)=-(x-y)$ @A.P. — CIJ, Mar 27 '15 at 00:46

score 2 · Accepted Answer · answered Mar 27 '15 at 00:41

2

Use the fact that since $x>y$ and $x,y\in \mathbb N$, then $x^2 >y^2$, so $x^2+x>y^2+y$, in contradiction of your equality

answered Mar 27 '15 at 00:41

Alan

16,582

So that would be sufficient to justify that the function is injective? – user3699546 Mar 27 '15 at 00:46
@user3699546 Injectivity means that different numbers have different images... – A.P. Mar 27 '15 at 00:47

score 1 · Answer 2 · answered Mar 27 '15 at 00:41

1

A simpler proof uses the fact that $g$ is monotone increasing, that is $g(d) < g(d+1)$. There are many ways of showing that: you can calculate $g(d+1) - g(d) = 2d+2 > 0$, or you can calculate $g'(d) = 2d+1 > 0$.

answered Mar 27 '15 at 00:41

Yuval Filmus

57,157

Or say it is the sum of functions known to be increasing. That's what is implicitly used in @Alan's proof. – Bernard Mar 27 '15 at 01:42

Proving injectivity of $g(d)= d^2 + d + 1$ by contradiction

2 Answers2