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.
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.
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.
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.
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?
@ 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.
OK, first a couple of definitions.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:asks to prove that for all it is the case that , . This statement can be broken into two parts.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.
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.
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 .