Proof of Fraction Position in Countable Set of Positive Rational Numbers

[gutnedawg]

Homework Statement

Prove that the fraction m/n occurs in position
$$\frac{m^2 +2mn + n^2 - m -3n}{2}$$

of the enumeration {1/1, 1/2, 2/1, 1/3, 2/2, 3/1,...}

of the set Q+ of positive rational numbers. (Hint: Count how many terms precede m/n in the enumeration.)

Homework Equations

The Attempt at a Solution

I'm not sure how to 'prove' this. But what I know is that Q is countable so I know that if I can count to a position j and plug in the m and n into the above formula I will get j.

 

[lanedance]

i would start by seeiong if you can finde a general form for the number of terms for a given m+n eg.
m+n = 2 gives 1/1, so there is 1 term
m+n = 3 gives 1/2, 2/1, 1/3, so there is 3 terms

 

[gutnedawg]

could I write that:

m+n=a_j and call this a set with a_j elements

then create a position set {{1/1},{1/2,2/1},{1/3,2/2,3/1},...} that is a_0,a_1,a_2 etc...

the position would be the addition of the number of elements in a_0+a_1+a_2...

I don't know where I'm going with this

 

[lanedance]

ok so let p = m+n, and N_p, be the number of terms corresponding to p
for
p = 2, gives 1/1, so N_2 = 1
p = 3, gives 1/2, 2/1, so N_3 = 2
p = 4, gives 1/3, 2/2, 3/1, so N_3 = 3

spotting any pattern, then consider summing over p to account for teh term with p<m+n, whilst you'll need to account for the p=m+n terms before the term separately

note the correction to the original post as well (N_3 case)

 

[gutnedawg]

ok so let p = m+n, and N_p, be the number of terms corresponding to p
for
p = 2, gives 1/1, so N_2 = 1
p = 3, gives 1/2, 2/1, so N_3 = 2
p = 4, gives 1/3, 2/2, 3/1, so N_3 = 3

spotting any pattern, then consider summing over p to account for teh term with p<m+n, whilst you'll need to account for the p=m+n terms before the term separately

note the correction to the original post as well (N_3 case)

Yea this was what I was trying to get at however you put it much more elegantly... My question before was how could I 'count' the number that come before m/n in a specific p. IE 3/1 is at position 5 we know p=2 + p=3 =3 but how can I include the fact that 1/3 and 2/2 come before 3/1 within the p=4

 

[lanedance]

I would first start by attempting the part I have given

Yea this was what I was trying to get at however you put it much more elegantly... My question before was how could I 'count' the number that come before m/n in a specific p. IE 3/1 is at position 5 we know p=2 + p=3 =3 but how can I include the fact that 1/3 and 2/2 come before 3/1 within the p=4

for this look at the ordering of the terms and compare to m & n and try and spot a pattern

 

[gutnedawg]

I think it's N_p+m correct?

 

[lanedance]

what is?

 

[gutnedawg]

what I was thinking is incorrect... I'm just not seeing a pattern that would give me what I need

 

[Loot]

the pattern is as follows:
M N
1 1
1 2
2 1
1 3
2 2
3 1
1 4
2 3
3 2
4 1

Use that formula and you'll see that it calculates the 0 based index correctly for the above.

Then with induction:
let P(m,n) be the position
P(m,n) = big equation.

Now, we have to prove that P(m+1,n-1) = P(m,n) + 1

Write it out and you will see that it's provable.