# Prove a function is one-to-one and onto

I need some help proving the following function is one-to-one and onto for $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$.

$F(i, j) = {i + j - 1 \choose 2} + j$

I know you guys like to see some attempt at a problem but I honestly have no idea where to start. A naive attempt simply making $F(i, j) = F(n, m)$ seems like it will have way too many cases to prove and I'm not even sure if that will prove 1-1. Is the best approach to define some sort of function and show it is invertible?

-
Did you try proving it is one-one? – Carry on Smiling Feb 6 '14 at 2:17
Yes, thats where the $F(i, j) = F(n, m)$ comes into play. – John Feb 6 '14 at 2:19
By the way, this is Cantor's pairing function‌​. Logicians use it to code finite sequences of numbers by single numbers. – Andrés E. Caicedo Feb 6 '14 at 3:04
proving surjectivity is actually quite fun, maybe you could read at [ juanmarqz.wordpress.com/2011/02/17/… ] – janmarqz Feb 6 '14 at 3:19
what's up @John? could you tell now what are $(i,j)$, positive integers, such that $F(i,j)=100,000$ for example? Kudos for your problem that made me sweat :D – janmarqz Feb 6 '14 at 15:39

You could start by listing the function values out in a grid. You might see something like the following:

$$\begin{array}{cccccccccc} 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\ 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & 54 & 65 \\ 4 & 8 & 13 & 19 & 26 & 34 & 43 & 53 & 64 & 76 \\ 7 & 12 & 18 & 25 & 33 & 42 & 52 & 63 & 75 & 88 \\ 11 & 17 & 24 & 32 & 41 & 51 & 62 & 74 & 87 & 101 \\ 16 & 23 & 31 & 40 & 50 & 61 & 73 & 86 & 100 & 115 \\ 22 & 30 & 39 & 49 & 60 & 72 & 85 & 99 & 114 & 130 \\ 29 & 38 & 48 & 59 & 71 & 84 & 98 & 113 & 129 & 146 \\ 37 & 47 & 58 & 70 & 83 & 97 & 112 & 128 & 145 & 163 \\ 46 & 57 & 69 & 82 & 96 & 111 & 127 & 144 & 162 & 181 \\ \end{array}$$

Now, can you explain that? One hint might be to look up triangular numbers.

-
I guess I'm tired or something but I still don't quite get where this is going. – John Feb 6 '14 at 2:26
Can you see the pattern in @Mark's table? If so then you could try two steps: (1) assuming the pattern continues, explain why $F$ is one-to-one and onto; (2) explain why the pattern does in fact continue. – David Feb 6 '14 at 2:31

I would like to point out I love Mark's answer. Triangular numbers are these ones. and they are of the form $\binom{n+1}{2}$

-
Does this help you? – Carry on Smiling Feb 6 '14 at 2:33
Would it be helpful to express the binomial coefficient in summation notation and then handle the cases where i + j - 1 < 2 separately? – John Feb 6 '14 at 2:37
yes, I believe that is another approach. – Carry on Smiling Feb 6 '14 at 2:38
Is it different than what you are trying to show me here? I see that the triangular numbers correspond to the expression I have but I'm unsure how it helps. – John Feb 6 '14 at 2:39
This is a visual proof – Carry on Smiling Feb 6 '14 at 2:41

Surjectivity of $F(i, j) = {i + j - 1 \choose 2} + j$.

Here it goes an algorithm to find for a given natural $\lambda$, a pair $(i,j)$ of natural numbers such that $F(i, j) = \lambda$:

For,

1) Find a couple $(1,m)$ such that $F(1,m)\approx\lambda$

2) Then you are lead to consider ${m\choose 2}+m\approx\lambda$ which is a quadratic $m^2+m-2\lambda\approx0$

3) Seek $m_+=\frac{-1+\sqrt{1+8\lambda}}{2}$

4) Verify that $F(1,\lfloor m_+\rfloor)\le\lambda$, where $\lfloor m_+\rfloor$ is the positive integer $\le$ than $m_+$.

5) Take $r=\lambda-F(1,\lfloor m_+\rfloor)$

6) Then $F(\lfloor m_+\rfloor+2-r,r)=\lambda$

Check the next exemplification:

Do you need $i,j\in{\Bbb{N}}$ such that $F(i,j)=308$?

-- Find the greatest solution for $m^2+m-616=0$:

-- this is $m_+=\frac{-1+\sqrt{1+2464}}{2}=24.3243...$

-- so $\lfloor m_+\rfloor=24$

-- then $F(1,24)={24\choose 2}+24=300$

-- so $r=8$

-- Then $F(18,8)={25\choose 2}+8=308$.

Injectivity of $F(i, j) = {i + j - 1 \choose 2} + j$.

(Pending)

-
this little algorithm is adapted from the one in [ juanmarqz.wordpress.com/2011/02/17/… ] – janmarqz Feb 6 '14 at 5:33