Putnam 1997, Problem A-6

For a positive integer $n$ and any real number $c$, define $x_k$ recursively by $x_0 = 0$, $x_1 = 1$, and for $k \geq 0$,
$$x_{k+2} = \frac{cx_{k+1} - (n - k)x_k}{k + 1}.$$
Fix $n$ and then take $c$ to be the largest value for which $x_{n+1} = 0$. Find $x_k$ in terms of $n$ and $k$, $1 \leq k \leq n$.

Solution:
Clearly \( x_{n+1} \) is a polynomial in \( c \) of degree \( n \), so it suffices to identify \( n \) values of \( c \) for which \( x_{n+1} = 0 \). We claim these are \( c = n - 1 - 2r \) for \( r = 0, 1, \ldots, n - 1 \); in this case, \( x_k \) is the coefficient of \( t^{k-1} \) in the polynomial \( f(t) = (1 - t)^r (1 + t)^{n-1-r} \). This can be verified by noticing that \( f \) satisfies the differential equation  
\[
\frac{f'(t)}{f(t)} = \frac{n - 1 - r}{1 + t} - \frac{r}{1 - t}
\]  
(by logarithmic differentiation) or equivalently,  
\[
(1 - t^2) f'(t) = f(t) [(n - 1 - r)(1 - t) - r(1 + t)] = f(t) [(n - 1 - 2r) - (n - 1)t]
\]  
and then taking the coefficient of \( t^k \) on both sides:  
\[
(k + 1) x_{k+2} - (k - 1) x_k = (n - 1 - 2r) x_{k+1} - (n - 1) x_k.
\]  
In particular, the largest such \( c \) is \( n - 1 \), and \( x_k = \binom{n - 1}{k - 1} \) for \( k = 1, 2, \ldots, n \).  

Greg Kuperberg has suggested an alternate approach to show directly that \( c = n - 1 \) is the largest root, without computing the others. Note that the condition \( x_{n+1} = 0 \) states that \( (x_1, \ldots, x_n) \) is an eigenvector of the matrix  
\[
A_{ij} = \begin{cases} 
i & j = i + 1 \\
n - j & j = i - 1 \\
0 & \text{otherwise}
\end{cases}
\]  
with eigenvalue \( c \). By the Perron-Frobenius theorem, \( A \) has a unique eigenvector with positive entries, whose eigenvalue has modulus greater than or equal to that of any other eigenvalue, which proves the claim.