Binary function problem

Define $f:\mathbb{Z}\to\mathbb{N}$ by $f(n)=3n^2 + 2n + 5$. Prove that $f:\mathbb{Z}\to\mathbb{N}$ and that $f$ is one-to-one.

I have the definitions of a function and one-to-one, but I'm just new to this sort of material. I would appreciate if someone could walk me through how to at least start this problem.

Thanks.

-
Hint: $3n^2 + 2n + 5 = 2n^2 + 4 + (n+1)^2$. Is this always positive? Is it increasing? – M.B. Oct 17 '12 at 18:58

You have to prove two things. In order to show that $f:\Bbb Z\to\Bbb N$, you must show that $f(n)\in\Bbb N$ for every $n\in\Bbb Z$. In other words, you must show that for each integer $n$, the number $3n^2+2n+5$ is in $\Bbb N$. It’s clear that $f(n)$ is always an integer: it’s a sum of products of integers. What may not be immediately obvious is that it’s always non-negative and therefore in $\Bbb N$ rather than just in $\Bbb Z$. One easy way to see this is to complete the square:

\begin{align*} f(n)&=3n^2+2n+5\\ &=3\left(n^2+\frac23n+\frac53\right)\\ &=3\left(\left(n+\frac13\right)^2-\frac19+\frac53\right)\\ &=3\left(n+\frac13\right)^2+\frac{14}3\\ &\ge\frac{14}3\;, \end{align*}

since $\left(n+\frac13\right)^2$ is always at least $0$.

The other thing that you must prove is that $f$ is one-to-one. There’s a standard approach to this that works nicely in most simple problems: assume that $f(n)=f(m)$ for some integers $m$ and $n$, and prove that this forces $m=n$. That shows that if you start with $m\ne n$, you can never get $f(m)=f(n)$, and hence that $f$ is one-to-one.

So begin by supposing that $n,m\in\Bbb Z$ and $f(n)=f(m)$. This simply means that $$3n^2+2n+5=3m^2+2m+5\;,\tag{1}$$ and all that you have to do is manipulate $(1)$ algebraically until you can infer that $n=m$. Here’s a hint to get you started: $(1)$ is equivalent to $$3\left(n^2-m^2\right)+2(n-m)=0\;,$$ and if you factor the lefthand side, this becomes $$(n-m)\Big(3(n+m)+2\Big)=0\;.$$ If a product of two numbers is $0$, what can you say about the numbers? What does that tell you here about $n$ and $m$?

-

We need to show that if $f(m)=f(n)$ then $m=n$. So suppose that $3m^2+2m+5=3n^2+2n+5$. Then $$3(m^2-n^2)=-2(m-n).$$ Note that $m^2-n^2=(m-n)(m+n)$. So if $m\ne n$, then by cancellation we get $$3(m+n)=-2.$$ This is not possible, since $3$ divides the left-hand side but $3$ does not divide $-2$.

We also need to show that $f(n)$ is positive for all integers $n$. The no-thinking way of doing this is to complete the square. If we want to think a little more and compute less, we can note that $3n^2+2n+5\ge n^2+2n+5=(n+1)^2+4$.

-
Nicely done. Your factoring and cancelling gets the 1-1 immediately. And I also agree it's not necessary to show the square-completion part of the argument, presumably the problem poser should be able to do that. – coffeemath Oct 17 '12 at 19:10

Clearly $f(n)\in\mathbb Z$ for all $n\in \mathbb Z$. Moreover, $3n^2+2n+5 = \frac13\left(3n+1\right)^2+\frac{14}3\ge \frac{14}3\ge1$. From $f(n)\in\mathbb Z$ and $f(n)\ge 1$, we conclude $f(n)\in \mathbb N$, so $f$ is indeed a function $\mathbb Z\to\mathbb N$.

For one-ton-one, assume $f(n)=f(m)$. Then $\frac13\left(3n+1\right)^2+\frac{14}3=\frac13\left(3m+1\right)^2+\frac{14}3$, hence $(3n+1)^2=(3m+1)^2$, i.e. $0=(3n+1)^2-(3m+1)^2=(3n+3m+2)(2n-2m)$. The first factor is one less than a multiple of $3$, hence nonzero. Hence $m=n$. We have shown that $f(n)=f(m)$ implies $n=m$, i.e. $f$ is one-to-one.

-