 
  
%knuth.tex:A 1-page plain TeX file. 
%Only in http://www.math.temple.edu/~zeilberg
%begin macros
\def\mod{\mathop{\rm mod} \nolimits}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline{Proof of an Identity of Don Knuth}
\rm
\bigskip
\centerline{ {\it Doron ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
{\eighttt zeilberg@math.temple.edu \break
http://www.math.temple.edu/\Tilde zeilberg \quad
 ftp://ftp.math.temple.edu/pub/zeilberg} \quad .
\break
Sept. 19, 1995.
} 
}
 
Don Knuth, in a letter to Richard Stanley, Cc-d to several
people, asked whether anybody has seen the following identity
before:
 
$$\displaylines{\quad
\sum_{0\le x_1,\ldots,x_{n}\le 1}
{(z-x_1z^{n+1})(z^2-x_2z^{n+1})\ldots (z^{n}-x_{n}z^{n+1})
z^{-nx_1-(n-1)x_2-\cdots -x_{n}}
\over
(x_1+1)(x_1x_2+x_2+1)\ldots 
(x_1\ldots x_{n}+\cdots+x_{n}+1)}\hfill\cr
\hfill{}
={(1-z)(1-z^2)\ldots (1-z^{n+1})\over (n+1)!\,(1-z)^{n+1}}.\qquad\cr}
$$
 
 
I have not. Here is a proof.
 
I will prove the more general identity:
 
$$\displaylines{\quad A(n,r):=\quad
\sum_{0\le x_1,\ldots,x_{n}\le 1}
{(z-x_1z^{n+1})(z^2-x_2z^{n+1})\ldots (z^{n}-x_{n}z^{n+1})
z^{-nx_1-(n-1)x_2-\cdots -x_{n}}
\over
(r x_1+1)(r x_1x_2+x_2+1)\ldots 
(r x_1\ldots x_{n} +  x_2\ldots x_{n} + \cdots+x_{n}+1)}\hfill\cr
\hfill{}
={(1-z)(1-z^2)\ldots (1-z^{n})\over (1-z)^{n+1} }
\cdot \sum_{l=1}^{n+1}
{{z^{n-l+1}(1-z)^l r!} \over {(r+l-1)!(n-l+1)!}}
.\qquad\cr}
$$
$$
\eqno(*)
$$
 
The original identity follows by plugging $r=1$ and using the
Binomial Theorem: $(z+(1-z))^{n+1}-z^{n+1}=1-z^{n+1}$.
 
To prove the identity for $A(n,r)$, split the sum according
to whether $x_1=0$ or $x_1=1$ to get the recurrence:
 
$$
A(n,r)=z^n A(n-1,1) + {{(1-z^n)} \over {r+1}} A(n-1,r+1) \quad .
$$
 
Since $A(0,r)=1$, and the expression on the right of $(*)$ obviously
also satisfies this recurrence, we are done. \halmos
\bye
 
