# Putnam 1999 B3

1. Nov 8, 2007

### ehrenfest

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

2. Nov 9, 2007

### Hurkyl

Staff Emeritus
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
3. Nov 9, 2007

### Hurkyl

Staff Emeritus
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 cancelled out in the numerator.

Last edited: Nov 9, 2007
4. Nov 9, 2007

### ehrenfest

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
5. Nov 9, 2007

### Hurkyl

Staff Emeritus
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

6. Nov 9, 2007

OK. Thanks.