# 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?

#### Solutions Collecting From Web of "Prove a function is one-to-one and onto"

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 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}$

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)