Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Putnam 1999 B3

  1. Nov 8, 2007 #1
    1. The problem statement, all variables and given/known data
    At this link, in the solution to question B3,
    http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/1999s.pdf [Broken]
    how did they get the second-to-last equality? Right above the words "and the desired limit is"?

    I tried factoring every way I know how and it did not work out!

    2. Relevant equations

    3. The attempt at a solution
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Nov 9, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It seemed straightforward to grind it out.

    After finding a common denominator, xy is clearly a factor of the numerator. If you collect terms w.r.t. x, 1-y is clearly a factor of each coefficient. (And by symmetry, the same will be true when you collect terms w.r.t. y)

    Alternatively, if you just attempted to naively compute the limit without bothering to factor, you'd see that

    xy * [ 1 - x^2 + x^3 y^2 - y^2 + x^2 y^3 - x^3 y^3 ]

    has a zero at x = 1. Therefore, x-1 must be a factor, and so you can divide it out of the numerator and denominator. Similarly for y-1.

    Incidentally, you don't have to be quite so clever to solve this problem. If you simply rearrange the sum for S(x, y) into an ordinary double sum (maybe, split it into even n and odd n), it looks like you can just brute force compute the closed form for S(x, y) by repeatedly applying the geometric series formula.
    Last edited: Nov 9, 2007
  4. Nov 9, 2007 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Incidentally, what I said is surely what I would have done if I were actually taking the exam.

    (1) Rewrite the problem in a familiar form.
    [tex]S = \sum_{\frac{1}{2} \leq \frac{m}{n} \leq 2} x^m y^n
    \sum_{n = 1}^{+\infty} \sum_{m = \lceil \frac{n}{2} \rceil}^{2n} x^m y^n

    (2) To eliminate the ceiling function, separate into even and odd n.

    [tex]S_1 = \sum_{p = 1}^{+\infty} \sum_{m = p}^{4p-2} x^m y^{2p-1}[/tex]

    [tex]S_2 = \sum_{p = 1}^{+\infty} \sum_{m = p}^{4p} x^m y^{2p}[/tex]

    [tex]S = S_1 + S_2[/tex]

    (3) Compute the inner sum.

    [tex]S_1 = \sum_{p = 1}^{+\infty} y^{2p-1}
    \frac{x^{4p - 1} - x^p}{x - 1}[/tex]

    (4) Separate the sums and compute again.

    [tex]S_1 = \frac{1}{x-1} ( S_{1,1} - S_{1,2} )[/tex]

    [tex]S_{1,1} = \sum_{p=1}^{+\infty} y^{2p-1} x^{4p-1}
    = \frac{y x^3}{1 - y^2 x^4}[/tex]

    [tex]S_{1,2} = \sum_{p=1}^{+\infty} y^{2p-1} x^{p}[/tex]

    And so forth.

    Once I get the closed form solution, unless I make a lucky observation, I would either

    (A) Manage to factor the numerator.
    (B) Plug in x=1 and thus notice that x-1 must be a factor.
    (C) Realize that the limit can only exist if the x-1 in the denominator gets cancelled out in the numerator.
    Last edited: Nov 9, 2007
  5. Nov 9, 2007 #4
    What do you mean collect terms with respect the variable x? Do you mean write it as a polynomial in x? I do not see how that is straightforward?
    Last edited: Nov 9, 2007
  6. Nov 9, 2007 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Example of collecting terms in x:

    1 + y + x - x^2 - xy^2 - x^2 y = (1 + y) + (1 - y^2) x - (1 + y) x^2
  7. Nov 9, 2007 #6
    OK. Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook