Results 1 to 9 of 9

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

  1. #1
    Newbie
    Joined
    Feb 2011
    Posts
    3

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

    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.
    Last edited by akyng; February 11th 2011 at 08:09 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2011
    Posts
    3
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2010
    From
    Heart of Winter
    Posts
    115
    Thanks
    1
    @ 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2010
    From
    Heart of Winter
    Posts
    115
    Thanks
    1
    ah I see

    so what would you put for first element? ((2+1)-2)?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2011
    Posts
    3
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773
    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}=<br />
\begin{cases}<br />
p_n-1 & p_n>1\\<br />
q_n+1 & \mbox{otherwise}<br />
\end{cases} and q_{n+1}=\begin{cases}<br />
q_n+1 & p_n>1\\<br />
1 & \mbox{otherwise}<br />
\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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2010
    From
    Heart of Winter
    Posts
    115
    Thanks
    1
    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.

    <br />
\begin{aligned}<br />
a_{n+1} &=(p+q)-2) \\<br />
&= (((p+q)+1)-2) \\<br />
&= ((p+q)-1).<br />
\end{aligned}<br />

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

    <br />
\begin{aligned}<br />
S_{n+1} <br />
&= \frac{1}{2} [(p + q - 2)(p + q - 1)]+(p+q-1) \\<br />
&= \frac{1}{2} [(p + q - 2)(p + q - 1)+2(p+q-1)] \\<br />
&= \frac{1}{2} [(p + q - 2)(p + q - 1) + 2p + 2q - 2] \\<br />
&= \frac{1}{2} [p^2 +  2pq + q^2 - p - q]  \\<br />
&= \frac{1}{2} [(p + q)^2 - p - q] \\<br />
&= \frac{1}{2} [(p + q)^2 - (p  + q)]  \\<br />
\end{aligned}<br />
    Last edited by skoker; February 13th 2011 at 03:18 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Power series, term-by-term integration
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 8th 2010, 02:14 AM
  2. Show me how to reduce into a single term
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: December 4th 2009, 04:37 PM
  3. term of a series
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 26th 2009, 01:14 AM
  4. Series - nth term - Is this right?
    Posted in the Calculus Forum
    Replies: 4
    Last Post: October 25th 2008, 08:36 PM
  5. nth term for series
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 8th 2007, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum