Show that p/q is the ...th term of the series...

**akyng** · February 11th 2011, 07:38 AM

Positive rational numbers may be arranged in the form of a simple series: $\frac{1}{1}, \frac{2}{1}, \frac{1}{2}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \frac{4}{1}, \frac{3}{2}, \frac{2}{3}, \frac{1}{4}, ...$ Show that $\frac{p}{q}$ is the $[\frac{1}{2}(p+q-1)(p+q-2)+q]^t^h$ 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.

**emakarov** · February 11th 2011, 12:09 PM

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.

**akyng** · February 11th 2011, 05:20 PM

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?

**skoker** · February 11th 2011, 10:55 PM

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

akyng

$[\frac{1}{2}(p+q-1)(p+q-2)+q]^t^h$

emakarov

$1 + 2 + ... + (p + q) - 2 = \frac{1}{2} [(p + q - 2)(p + q - 1)]$

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.

**emakarov** · February 12th 2011, 12:15 AM

I think our expressions are exactly the same. The green triangle has $1 + 2 + ... + ((p + q) - 2) = \frac{1}{2} [(p + q - 2)(p + q - 1)]$ points. To this one adds q: the position of the current point on the blue diagonal.

**skoker** · February 12th 2011, 01:02 AM

ah I see

so what would you put for first element? ((2+1)-2)?

**akyng** · February 12th 2011, 06:09 AM

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?

**emakarov** · February 12th 2011, 10:16 AM

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

OK, first a couple of definitions.

Let $f(p,q)=(p+q-1)(p+q-2)/2+q$ . Also, let $p_n,q_n$ be defined by mutual recursion as follows: $p_1=q_1=1$ ,
$p_{n+1}= \begin{cases} p_n-1 & p_n>1\\ q_n+1 & \mbox{otherwise} \end{cases}$ and $q_{n+1}=\begin{cases} q_n+1 & p_n>1\\ 1 & \mbox{otherwise} \end{cases}$ .

The original problem:

Show that $\frac{p}{q}$ is the $[\frac{1}{2}(p+q-1)(p+q-2)+q]^t^h$ term of the series.

asks to prove that for all $p,q$ it is the case that $p=p_{f(p,q)}$ , $q=q_{f(p,q)}$ . This statement can be broken into two parts.

Proposition 1. For all $p,q$ there exists an $n$ such that $p=p_n$ and $q=q_n$ .

Proposition 2. $f(p_n,q_n)=n$ for all $n\ge 1$ .
This is proved by induction on $n$ . In the induction step, one has to consider two cases depending on whether $p_n>1$ .

Then, given $p$ and $q$ , we use Proposition 1 to find an $n$ such that $p=p_n$ and $q=q_n$ . By Proposition 2, $n=f(p,q)$ , which proves the required claim.

**skoker** · February 12th 2011, 09:10 PM

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 $\frac{p}{q}$ . now set $(p+q)=n$ . call these elements $a_n$ in a statement involving n. we can fallow the little place numbers to build our $a_n$ values.

now if you run $a_n$ through $((p+q)-2)$ you get a repeat value for each diagonal row like in the chart. if you run $a_n$ through $\frac{1}{2} [(p + q - 2)(p + q - 1)]$ you get the sum of the row values. so I assume that is what we want. so therefore $S_n$ is the nth partial sum of the row values.

$a_n= ((p+q)-2):a_1=0,a_{2-3}=1,a_{4-6}=2,a_{7-10}=3,a_{11-15}=4...$

$S_n= \frac{1}{2} [(p + q - 2)(p + q - 1)]:S_1=0,S_{2-3}=1,S_{4-6}=3,S_{7-10}=6,S_{11-15}=10...$

$a_1=0$ is equal to $S_1=0$ so we have proof that $a_1$ is true. the truth of $a_n$ implies the truth of $a_{n+1}$ . we assume that $a_n$ is true and build the $a_{n+1}$ statement.

$ \begin{aligned} a_{n+1} &=(p+q)-2) \\ &= (((p+q)+1)-2) \\ &= ((p+q)-1). \end{aligned} $

now we add $a_{n+1}$ to $S_n$ .

$ \begin{aligned} S_{n+1} &= \frac{1}{2} [(p + q - 2)(p + q - 1)]+(p+q-1) \\ &= \frac{1}{2} [(p + q - 2)(p + q - 1)+2(p+q-1)] \\ &= \frac{1}{2} [(p + q - 2)(p + q - 1) + 2p + 2q - 2] \\ &= \frac{1}{2} [p^2 + 2pq + q^2 - p - q] \\ &= \frac{1}{2} [(p + q)^2 - p - q] \\ &= \frac{1}{2} [(p + q)^2 - (p + q)] \\ \end{aligned} $

Thread: Show that p/q is the ...th term of the series...

LinkBack

Thread Tools

Display

Show that p/q is the ...th term of the series...

Similar Math Help Forum Discussions

Power series, term-by-term integration

Show me how to reduce into a single term

term of a series

Series - nth term - Is this right?

nth term for series

Search Tags