What is the solution to Problem A-6 in the 1997 Putnam Mathematical Competition?

[Ackbach]

Here is this week's POTW:

-----

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

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 232 - Sep 07, 2016

This was Problem A-6 in the 1997 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

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,\dots, 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,
\begin{align*}
(1-t^2) f'(t) &= f(t) [(n-1-r)(1-t) - r(1+t)] \\
&= f(t) [(n-1-2r) - (n-1)t]
\end{align*}
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 $\displaystyle x_k =\binom{n-1}{k-1}$ for $k= 1, 2, \dots, n$.