Solving Question B3 from the 1999 Putnam Exam

[ehrenfest]

Homework Statement

At this link, in the solution to question B3,
http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/1999s.pdf
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!

Homework Equations

The Attempt at a Solution

 

[Hurkyl]

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.

 

[Hurkyl]

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

$$S_1 = \sum_{p = 1}^{+\infty} \sum_{m = p}^{4p-2} x^m y^{2p-1}$$

$$S_2 = \sum_{p = 1}^{+\infty} \sum_{m = p}^{4p} x^m y^{2p}$$

$$S = S_1 + S_2$$

(3) Compute the inner sum.

$$S_1 = \sum_{p = 1}^{+\infty} y^{2p-1} \frac{x^{4p - 1} - x^p}{x - 1}$$

(4) Separate the sums and compute again.

$$S_1 = \frac{1}{x-1} ( S_{1,1} - S_{1,2} )$$

$$S_{1,1} = \sum_{p=1}^{+\infty} y^{2p-1} x^{4p-1} = \frac{y x^3}{1 - y^2 x^4}$$

$$S_{1,2} = \sum_{p=1}^{+\infty} y^{2p-1} x^{p}$$

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 canceled out in the numerator.

 

[ehrenfest]

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)

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?

 

[Hurkyl]

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

 

[ehrenfest]

OK. Thanks.