Positive rational numbers may be arranged in the form of a simple series: Show that is the term of the series.

I have already considered arithmetic sequences for p and q but I don't think it works. How should I approach the problem?

Thanks.

Printable View

- February 11th 2011, 08:38 AMakyngShow that p/q is the ...th term of the series...
Positive rational numbers may be arranged in the form of a simple series: Show that is the term of the series.

I have already considered arithmetic sequences for p and q but I don't think it works. How should I approach the problem?

Thanks. - February 11th 2011, 01:09 PMemakarov
This expression of p and q is called Cantor pairing function. It maps pair of positive integers onto positive integers in a one-to-one manner. It is useful because it demonstrates that there are as many positive integers as pairs of positive integers.

https://lh3.googleusercontent.com/_S...or-pairing.png

To understand why it works, consider this picture. The value of the pairing function is shown near each point. Arrow show the direction in which the value of the function increases.

Note that p + q is constant on the diagonals. Let's look at the blue diagonal, where p + q = 5. How many points come before, i.e., how many points are in the green triangle? It's 1 + 2 + 3, or, in terms of p and q, it's 1 + 2 + ... + (p + q) - 2 = 1/2 [(p + q - 2) * (p + q - 1)] (as the sum of an arithmetic progression). If we add the vertical coordinate q, we get the value of the function on the blue diagonal. - February 11th 2011, 06:20 PMakyng
Thank you for your solution. I didn't expect an advanced topic like the Cantor pairing function to be required for this problem. I was told by a teaching assistant that this problem can be solved by mathematical induction. But he said it may not work because after p or q reaches the end of its arithmetic progression, it "jumps" to a different number. In the inductive step, we assume the statement is true for some n, then we try to show that (p-1)/(q+1) is the (n+1)th term of the series. This would result in the wrong numbers in some cases. Can induction still be used anyway? In a different way maybe?

- February 11th 2011, 11:55 PMskoker
@ akyng

could you post the exact problem. or a copy of it. there is some differences from what you posted and emakarovs expression.

akyng

emakarov

notice you have 1/2 fraction in different grouping, there is +q at the end of your expression and emakarov has a (p+q)-2 nth term. that would give you 0,1,2,3,4 etc, for the sequence. - February 12th 2011, 01:15 AMemakarov
I think our expressions are exactly the same. The green triangle has points. To this one adds q: the position of the current point on the blue diagonal.

- February 12th 2011, 02:02 AMskoker
ah I see :)

so what would you put for first element? ((2+1)-2)? - February 12th 2011, 07:09 AMakyng
The first element of the series is 1/1 or 0.5*(1+1-2)(1+1-1)+1. Does someone know something to the question I asked in post #3, about whether mathematical induction can be used for this problem?

- February 12th 2011, 11:16 AMemakarovQuote:

Does someone know something to the question I asked in post #3, about whether mathematical induction can be used for this problem?

Let . Also, let be defined by mutual recursion as follows: ,

and .

The original problem:Quote:

Show that is the term of the series.

Proposition 1. For all there exists an such that and .

Proposition 2. for all .

This is proved by induction on . In the induction step, one has to consider two cases depending on whether .

Then, given and , we use Proposition 1 to find an such that and . By Proposition 2, , which proves the required claim. - February 12th 2011, 10:10 PMskoker
this one is interesting. I have been doing some of the induction proofs in pre-calculus book but not with 2 variables. so I take a crack at it for my own personal fun. (Rock)

we start with the chart emakarov posted. we pair the outside numbers as . now set . call these elements in a statement involving n. we can fallow the little place numbers to build our values.

now if you run through you get a repeat value for each diagonal row like in the chart. if you run through you get the sum of the row values. so I assume that is what we want. so therefore is the nth partial sum of the row values.

is equal to so we have proof that is true. the truth of implies the truth of . we assume that is true and build the statement.

now we add to .