Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Did you try proving it is one-one? –  user4140 Feb 6 at 2:17
    
Yes, thats where the $F(i, j) = F(n, m)$ comes into play. –  John Feb 6 at 2:19
    
By the way, this is Cantor's pairing function‌​. Logicians use it to code finite sequences of numbers by single numbers. –  Andres Caicedo Feb 6 at 3:04
    
proving surjectivity is actually quite fun, maybe you could read at [ juanmarqz.wordpress.com/2011/02/17/… ] –  janmarqz Feb 6 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 at 15:39
show 1 more comment

3 Answers

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.

share|improve this answer
    
I guess I'm tired or something but I still don't quite get where this is going. –  John Feb 6 at 2:26
3  
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 at 2:31
add comment

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

enter image description here

share|improve this answer
    
Does this help you? –  user4140 Feb 6 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 at 2:37
    
yes, I believe that is another approach. –  user4140 Feb 6 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 at 2:39
    
This is a visual proof –  user4140 Feb 6 at 2:41
add comment

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)

share|improve this answer
    
this little algorithm is adapted from the one in [ juanmarqz.wordpress.com/2011/02/17/… ] –  janmarqz Feb 6 at 5:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.