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

• Feb 11th 2011, 07:38 AM
akyng
Show that p/q is the ...th term of the series...
Positive rational numbers may be arranged in the form of a simple series: $\displaystyle \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 $\displaystyle \frac{p}{q}$ is the $\displaystyle [\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.
• Feb 11th 2011, 12:09 PM
emakarov
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.
• Feb 11th 2011, 05:20 PM
akyng
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?
• Feb 11th 2011, 10:55 PM
skoker
@ akyng
could you post the exact problem. or a copy of it. there is some differences from what you posted and emakarovs expression.

akyng

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

emakarov

$\displaystyle 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.
• Feb 12th 2011, 12:15 AM
emakarov
I think our expressions are exactly the same. The green triangle has $\displaystyle 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.
• Feb 12th 2011, 01:02 AM
skoker
ah I see :)

so what would you put for first element? ((2+1)-2)?
• Feb 12th 2011, 06:09 AM
akyng
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?
• Feb 12th 2011, 10:16 AM
emakarov
Quote:

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

The original problem:
Quote:

Show that $\displaystyle \frac{p}{q}$ is the $\displaystyle [\frac{1}{2}(p+q-1)(p+q-2)+q]^t^h$ term of the series.
asks to prove that for all $\displaystyle p,q$ it is the case that $\displaystyle p=p_{f(p,q)}$, $\displaystyle q=q_{f(p,q)}$. This statement can be broken into two parts.

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

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

Then, given $\displaystyle p$ and $\displaystyle q$, we use Proposition 1 to find an $\displaystyle n$ such that $\displaystyle p=p_n$ and $\displaystyle q=q_n$. By Proposition 2, $\displaystyle n=f(p,q)$, which proves the required claim.
• Feb 12th 2011, 09:10 PM
skoker
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 $\displaystyle \frac{p}{q}$. now set $\displaystyle (p+q)=n$. call these elements $\displaystyle a_n$ in a statement involving n. we can fallow the little place numbers to build our $\displaystyle a_n$ values.

now if you run $\displaystyle a_n$ through $\displaystyle ((p+q)-2)$ you get a repeat value for each diagonal row like in the chart. if you run $\displaystyle a_n$ through $\displaystyle \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 $\displaystyle S_n$ is the nth partial sum of the row values.

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

$\displaystyle 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...$

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

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

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

\displaystyle \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}