Putnam 1997 Problem A6 Let N be a fixed positive integer. For real α, define the sequence x k by: x 0 = 0, x 1 = 1, x k+2 = (αx k+1 - (N - k)x k )/(k + 1). Find the largest α such that x N+1 = 0 and the resulting x k . Solution
: α = N - 1, x k = (N-1)C(k-1) for k ≤ N and 0 for k > N. Easy to get the answer, harder to prove it (but straightforward provided you are familiar with generating functions). Playing around with low values of N quickly generates the binomial coefficients and the value α = N - 1. It is then straightforward to verify that these values satisfy the recurrence relation. But that still leaves open the possibility that a larger value of α might work. So we have to use a little more machinery. Notice first that if x N+1 = 0, then x N+2 = 0 and hence x i = 0 for all i > N. Now define the generating function f(z) = ∑ 0 ∞ x k+1 z k . We have no convergence worries, because f(z) is in fact a polynomial. We have f '(z) = ∑ 0 ∞ (k+1)x k+2 z k , zf(z) = ∑ 1 ∞ x k z k , and z 2 f '(z) + zf(z) = ∑ 1 ∞ k x k z k , and so the recurrence relation is equivalent to: f '(z)/f(z) = (α - (N-1)z)/(1 - z 2 ) = (α - (N-1))/(2(1 - z)) + (α + N-1)/(2(1+z)). Integrating (and using x 1 = 0): f(z) = (1-z) (N-1-α)/2 (1+z) (α+N-1)/2 . Now we see immediately that the largest value of α which gives a polynomial is α = N - 1. The generating function is then (1 + z) N-1 , and so x k = (N-1)C(k-1). Putnam 1997 © John Scholes jscholes@kalva.demon.co.uk 12 Dec 1998