• Support PF! Buy your school textbooks, materials and every day products Here!

Set Theory (Countable Proof)

  • Thread starter gutnedawg
  • Start date
  • #1
35
0

Homework Statement



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

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.
 

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
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
 
Last edited:
  • #3
35
0
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
 
  • #4
lanedance
Homework Helper
3,304
2
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)
 
Last edited:
  • #5
35
0
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
 
  • #6
lanedance
Homework Helper
3,304
2
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
 
  • #7
35
0
I think it's N_p+m correct?
 
  • #8
lanedance
Homework Helper
3,304
2
what is?
 
  • #9
35
0
what I was thinking is incorrect... I'm just not seeing a pattern that would give me what I need
 
  • #10
1
0
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.
 

Related Threads for: Set Theory (Countable Proof)

  • Last Post
Replies
9
Views
2K
Replies
3
Views
10K
Replies
1
Views
1K
  • Last Post
Replies
3
Views
997
  • Last Post
Replies
2
Views
1K
Replies
3
Views
3K
  • Last Post
Replies
4
Views
2K
Replies
1
Views
2K
Top