\magnification\magstephalf
\parskip 5pt
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}
\def\AW{Addison\kern.1em--Wesley}

{\baselineskip14pt

{\bf Solution to problem 10424.}\quad
Let $t(n,k)=2^k{n-k\choose 2k}n/(n-k)$. The algorithm of Gosper and
Zeilberger [which is explained in {\sl Concrete Mathematics\/} by Graham,
Knuth, and Patashnik, second edition (\AW, 1994)] deduces quickly that
$$2t(n,k)-t(n+1,k)+2t(n+2,k)-t(n+3,k)=2t(n,k)-2t(n,k-1)\,.$$
Summing both sides for $0\leq k<n$ yields
$$2s(n)-s(n+1)+2s(n+2)-s(n+3)=0$$
when $n>1$, where $s(n)=\sum_{0\leq k\leq n/3}t(n,k)$, since the right-hand
side telescopes to $2t(n,n-1)-2t(n,-1)=0-0$ and since $t(n,k)=0$ for $n/3<k<n$.
The initial values $s(0)=0$, $s(1)=s(2)=1$, $s(3)=4$, $s(4)=9$ now lead to the
generating function
$$\sum_{n=0}^{\infty}s(n)z^n={-z+z^2-3z^3\over 2z^3-z^2+2z-1}=-{3\over 2}
+{1\over 2-4z}+{1\over 1+z^2}\,;$$
the stated sum is therefore
$$2^{n-1}+(-1)^{n/2}\ [n\hbox{ even}]\,,\qquad n>0\,.$$

}

\bigskip

\adx 275pt:
Donald E. Knuth\cr
Computer Science Department\cr
Stanford University\cr

\end
