Let N be a fixed positive integer. For real α, define the sequence xk by: x0 = 0, x1 = 1, xk+2 = (αxk+1 - (N - k)xk)/(k + 1). Find the largest α such that xN+1 = 0 and the resulting xk.
Solution
Answer: α = N - 1, xk = (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 xN+1 = 0, then xN+2 = 0 and hence xi = 0 for all i > N. Now define the generating function f(z) = ∑0∞ xk+1zk. We have no convergence worries, because f(z) is in fact a polynomial. We have f '(z) = ∑0∞ (k+1)xk+2zk, zf(z) = ∑1∞ xkzk, and z2f '(z) + zf(z) = ∑1∞ k xkzk, and so the recurrence relation is equivalent to:
f '(z)/f(z) = (α - (N-1)z)/(1 - z2) = (α - (N-1))/(2(1 - z)) + (α + N-1)/(2(1+z)).
Integrating (and using x1 = 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 xk = (N-1)C(k-1).
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998