0]+b''_i\bigr)!}
z^k\,.
\enddisplay
Then we have $\deg(\phat)=\deg(f)+\max\bigl(
\sum_{i=1}^q b_i\[b_i>0]-\sum_{i=1}^p a_i\[a_i<0],\allowbreak
\sum_{i=1}^p a_i\[a_i>0]-\sum_{i=1}^q b_i\[b_i<0]\bigr)
\ge\deg(f)+\half l@\bigl(\vert a_1\vert+\cdots+\vert a_p\vert
+\vert b_1\vert+\cdots+\vert b_q\vert\bigr)$, except in
unusual cases where cancellation occurs in the leading coefficient. And
$\deg(q)=\sum_{i=1}^p a'_i\[a'_i>0]-\sum_{i=1}^q b'_i\[b'_i<0]$,
$\deg(r)=\sum_{i=1}^q b'_i\[b'_i>0]-\sum_{i=1}^p a'_i\[a'_i<0]$,
again except in unusual cases.\par
(These estimates can be used to show directly that, as $l$ increases, the
degree of $\phat$ eventually becomes large enough to make a polynomial
$s(n,k)$ possible, and the number of unknown $\alpha_j$ and $\beta_j$
eventually becomes larger than
the number of homogeneous linear equations to be solved. So we obtain another
proof that the Gosper-Zeilberger algorithm succeeds, if we argue as in
the text that there must be a solution with $\beta_0(n)$, \dots,~$\beta_l(n)$
not all zero.)
\ex:
Use the Gosper-Zeilberger procedure to verify the remarkable identity
\begindisplay
\sum_k(-1)^k{r-s-k\choose k}{r-2k\choose n-k}{1\over r-n-k+1}
={s\choose n}{1\over r-2n+1}\,.
\enddisplay
Explain why the simplest recurrence for this sum is not found.
\answer Let $t(n,k)=(-1)^k(r-s-k)!\,(r-2k)!/\bigl((r-s-2k)!\,(r-n-k+1)!
\,(n-k)!\allowbreak\,k!\bigr)$.
Then $\beta_0(n)t(n,k)+\beta_1(n)t(n+1,k)$ is not summable in hypergeometric
terms, because $\deg(\phat)=1$, $\deg(q-r)=3$,
$\deg(q+r)=4$, $\lambda=-8$, $\lambda'=-4$;
but $\beta_0(n)t(n,k)+\beta_1(n)t(n+1,k)+\beta_2(n)t(n+2,k)$
is\dash---basically
because $\lambda'=0$ when $q(n,k)=-(r-s-2k)(r-s-2k-1)(n+2-k)(r-n-k+1)$ and
$r(k)=(r-s-k+1)(r-2k+2)(r-2k+1)@k$. The solution is
\begindisplay
\beta_0(n)&=(s-n)(r-n+1)(r-2n+1)\,,\cr
\beta_1(n)&=(rs-s^2-2rn+2n^2-2r+2n)(r-2n-1)\,,\cr
\beta_2(n)&=(s-r+n+1)(n+2)(r-2n-3)\,,\cr
\alpha_0(n)&=r-2n-1\,,\cr
\enddisplay
and we may conclude that $\beta_0(n)S_n+\beta_1(n)S_{n+1}+\beta_2(n)S_{n+2}=0$
when $S_n$ denotes the stated sum. This suffices to prove the identity by
induction, after verifying the cases $n=0$ and $n=1$.\par
\def\betabar{{\bar\beta}}
But $S_n$ also satisfies the simpler recurrence
$\betabar_0(n)S_n+\betabar_1(n)S_{n+1}=0$, where
$\betabar_0(n)=(s-n)(r-2n+1)$ and $\betabar_1(n)=-(n+1)(r-2n-1)$. Why didn't
the method discover this? Well, nobody ever said that such a recurrence
necessarily forces the terms $\betabar_0(n)t(n,k)+\betabar_1(n)t(n+1,k)$ to be
indefinitely summable. The surprising thing is that the Gosper-Zeilberger
method actually does find the simplest recurrence in so many other cases.\par
Notice that the second-order recurrence we found can be factored:
\begindisplay
&\beta_0(n)+\beta_1(n)@N+\beta_2(n)@N^2\cr
&\qquad=
\bigl((r-n+1)N+(r-s-n-1)\bigr)\;\bigl(\betabar_0(n)+\betabar_1(n)@N\bigr)\,,
\enddisplay
where $N$ is the shift operator in \equ(5.|ldo|).
\source{Volker "Strehl".*}
\ex:
Show that if $\omega=e^{2\pi i/3}$ we have
\begindisplay
\sum_{k+l+m=3n}{3n\choose k,l,m}^{\!2}\omega^{l-m}={4n\choose n,n,2n}\,,
\qquad\hbox{integer $n\ge0$.}
\enddisplay
\answer Set $a=1$ and compare
the coefficients of $z^{3n}$ on both sides of
"Henrici"'s ``"friendly monster"'' identity,
\begindisplay
&f(a,z)\,f(a,\omega z)\,f(a,\omega^2z)\cr
&\quad=\hyp{\half a-{1\over4},\,\,\,\half a+{1\over4}}
{{1\over3}a,\,\,{1\over3}a{+}{1\over3},\,\,{1\over3}a{+}{2\over3},\,\,
{2\over3}a{-}{1\over3},\,\, {2\over3}a,\,\,{2\over3}a{+}{1\over3},\,\,
a\,\,}{\left(4z\over9\right)^{\!\!3}\,},
\enddisplay
where $f(a,z)=F(1;a,1;z)$. The identity can be proved by showing that both
sides satisfy the same differential equation.
\par
Peter "Paule" has found another interesting way to evaluate the sum:
\begindisplay
\sum_{k,l}{N\choose k,l,N-k-l}^{\!2}&\omega^{k+2l}
=\sum_{k,l}{N\choose k-l,l,N-k}^{\!2}\omega^{k+l}\cr
&=\sum_{k,l}{N\choose k}^{\!2}{k\choose l}^{\!2}\omega^{k+l}\cr
&=\sum_k{N\choose k}^{\!2}\omega^{k}\,
[z^k]\,\bigl((1+z)(\omega+z)\bigr)^k\cr
&=[z^0]\,\sum_k{N\choose k}^{\!2}
\left(\omega(1+z)(\omega+z)\over z\right)^{\!k}\cr
&=[z^0]\,\sum_{k,j}{N\choose k}^{\!2}{k\choose j}
\left({\omega(1+z)(\omega+z)\over z}-1\right)^{\!j}\cr
&=[z^0]\,\sum_{k,j}{N\choose k}{N-j\choose N-k}{N\choose j}
\left((\omega z-1)^2\over\omega z\right)^{\!j}\cr
&=\sum_j{2N-j\choose N}{N\choose j}\,[z^j]\,(z-1)^{2j}\cr
&=\sum_j{2N-j\choose N}{N\choose j}{2j\choose j}(-1)^j\,,\cr
\enddisplay
using the binomial theorem, Vandermonde's convolution, and the fact that
$[z^0]g(az)=[z^0]g(z)$. We can now set $N=3n$ and apply the Gosper-Zeilberger
algorithm
to this sum~$S_n$, miraculously obtaining the first-order recurrence
$(n+1)^2S_{n+1}=4(4n+1)(4n+3)S_n$; the result follows by induction.\par
If $3n$ is replaced by $3n+1$ or $3n+2$, the stated sum is zero.
Indeed, $\sum_{k+l+m=N}t(k,l,m)\omega^{l-m}$ is always zero when
$N\bmod3\ne0$ and $t(k,l,m)=t(l,m,k)$.
\source{"Henrici" [|henrici-bieberbach|, p.~118].}
\ex:\exref|reprove-bc-quad|%
Prove the amazing identity \eq(|bc-quad|) by letting $t(r,j,k)$ be the
summand divided by the right-hand side, then showing that there are
functions $T(r,j,k)$ and $U(r,j,k)$ for which
\begindisplay
t(r+1,j,k)-t(r,j,k)&=T(r,j+1,k)-T(r,j,k)\cr
&\qquad{}+U(r,j,k+1)-U(r,j,k)\,.
\enddisplay
\answer (Solution by Shalosh B "Ekhad".) Let
\begindisplay
%T(r,j,k)&={(1{-}j{+}s{+}sk{+}n{-}jn{+}r{-}jr{-}kr{+}sr{+}nr)(j-l)@j\over
T(r,j,k)&={((1{+}n{+}s)(1{+}r)-(1{+}n{+}r)@j+(s{-}r)@k)(j{-}l)@j\over
(l-m+n-r+s)(n+r+1)(j-r-1)(j+k)}t(r,j,k)\,;\cr
U(r,j,k)&={(s+n+1)(k+l)@k\over(l-m+n-r+s)(n+r+1)(j+k)}t(r,j,k)\,.
\enddisplay
The stated equality is routinely verifiable, and \equ(5.|bc-quad|) follows
by summing with respect to $j$ and $k$. (We sum $T(r,j+1,k)-T(r,j,k)$ first
with respect to~$j$, then with respect to~$k$; we sum the other terms
$U(r,j,k+1)-U(r,j,k)$ first with respect to~$k$, then with respect to~$j$.)
\par Well, we also need to verify \equ(5.|bc-quad|) when $r=0$. In that
case it reduces via trinomial revision
to $\sum_k(-1)^k{n\choose n+l}{n+l\choose k+l}{s+n-k\choose m}
=(-1)^l{n\choose n+l}{s\choose m-n-l}$. We are assuming that $l$, $m$, and $n$
are integers and $n\ge0$. Both sides are clearly zero unless
$n+l\ge 0$. Otherwise we can replace $k$ by $n-k$ and use \equ(5.|bc-prod3|).
\ex:\exref|not-holonomic|%
Prove that $1/(nk+1)$ is not a "proper term".
\answer If it were proper, there would be a linear difference operator
\g Noticee that $1/nk$ is proper, since it's\par
$(n-1)!(k-1)!/$\par
$n!\,k!$. Also\par $1/(n^2-k^2)$ is proper. But\vskip2pt $1/(n^2+k^2)$ isn't.\g
that annihilates it. In other words, we would have a finite summation identity
\begindisplay
\sum_{i=0}^I\sum_{j=0}^J\alpha_{i,j}(n)\big/\bigl((n+i)(k+j)+1\bigr)=0\,,
\enddisplay
where the $\alpha$'s are polynomials in $n$, not all zero. Choose integers
$i$, $j$, and $n$ such that $n>1$ and $\alpha_{i,j}(n)\ne0$. Then when
$k=-1/(n+i)-j$, the $(i,j)$ term in the sum is infinite but the other
terms are finite.
\ex:\exref|apery-mn|%
Show that the Ap\'ery numbers $A_n$ of \eq(|apery-sum|) are the
diagonal elements $A_{n,n}$ of a matrix of numbers defined by
\begindisplay
A_{m,n}=\sum_{j,k}{m\choose j}^2\,{m\choose k}^2\,{2m+n-j-k\choose 2m}\,.
\enddisplay
Prove, in fact, that this matrix is symmetric, and that
\begindisplay
A_{m,n}
&=\sum_k{m+n-k\choose k}^2\,{m+n-2k\choose m-k}^2\cr
&=\sum_k{m\choose k}\,{n\choose k}\,{m+k\choose k}\,{n+k\choose k}\,.
\enddisplay
\answer Replace $k$ by $m-k$ in the double sum, then
use \equ(5.|bc-saalschutz|) to sum on~$k$, getting
\begindisplay
A_{m,n}=\sum_j{m\choose j}^2\,{m+n-j\choose m}^2\,;
\enddisplay
trinomial revision \equ(5.|bc-tc|) then yields one of the desired
formulas.\par
It appears to be difficult to find a direct proof that the two symmetrical
sums for $A_{m,n}$ are equal. We can, however, prove the equation
indirectly with the Gosper-Zeilberger
algorithm, by showing that both sums satisfy the recurrence
\begindisplay
(n+1)^3A_{m,n}-f(m,n)A_{m,n+1}+(n+2)^3A_{m,n+2}=0\,,
\enddisplay
where $f(m,n)=(2n+3)(n^2+3n+2m^2+2m+3)$.
Setting $t_1(n,k)={m\choose k}{n\choose k}{m+k\choose k}{n+k\choose k}$ and
$t_2(n,k)={m+n-k\choose k}^2{m+n-2k\choose m-k}^2$, we find
\begindisplay
&(n+1)^2t_j(n,k)-f(m,n)t_j(n+1,k)+(n+2)^2t_j(n+2,k)\cr
&\qquad=T_j(n,k+1)-T_j(n,k)\,,\cr
\enddisplay
where $T_1(n,k)=-2(2n+3)k^4t_1(n,k)/(n+1-k)(n+2-k)$ and
$T_2(n,k)=-\bigl((n+2)(4mn+n+3m^2+8m+2)-2(3mn+n+m^2+6m+2)k+{(2m+1)k^2}\bigr)
k^2(m+n+1-k)^2t_2(n,k)/(n+2-k)^2$. This proves the recurrence, so we
need only verify equality when $n=0$ and $n=1$.
(We could also have used the simpler recurrence
\begindisplay
m^3A_{m,n-1}-n^3A_{m-1,n}=(m-n)(m^2+n^2-mn)A_{m-1,n-1}\,,
\enddisplay
which can be discovered by the method of exercise |legendre-recs|.)\par
The fact that the first formula for $A_{m,n}$ equals the third implies a
remarkable identity between the
generating functions $\sum_{m,n}A_{m,n}w^mz^n$:
\begindisplay
\sum_k{w^kS_k(z)^2\over(1-z)^{2k+1}}=
\sum_k{2k\choose k}^2\!{w^k\over(1-w)^{2k+1}}{z^k\over(1-z)^{2k+1}}\,,
\enddisplay
where $S_k(z)=\sum_j{k\choose j}^2z^j$. It turns out, in fact, that
\begindisplay
\sum_k{w^k@S_k(x)@S_k(y)\over(1-x)^k(1-y)^k}=
\sum_k{2k\choose k}{w^k\over(1-w)^{2k+1}}{\sum_j{k\choose j}^2x^jy^{k-j}\over
(1-x)^k(1-y)^k}\,;
\enddisplay
this is a special case of an identity discovered by "Bailey" [|bailey-jacobi|].
\source{"Ap\'ery" [|apery|].}
\ex:
Prove that the "Ap\'ery numbers" \eq(|apery-sum|) satisfy
\begindisplay
A_n\=A_{\lfloor n/p\rfloor}A_{n\,\bmod\,p}\qquad\hbox{(mod~$p$)}
\enddisplay
for all primes~$p$ and all integers $n\ge0$.
\answer Let $X_n=\sum_k{n\choose k}^{a_0}{n+k\choose k}^{a_1}\ldots
{n+lk\choose k}^{a_l}x^k$ for any positive integers $a_0$, $a_1$, \dots,~$a_l$,
and any integer~$x$. Then if $0\le m3160$?
\itemitem{b} Is $q(n)=11$ for infinitely many $n$?
\smallskip
\par A "reward" of \$$7\cdot11\cdot13$ is offered for
a solution to either (a) or~(b).
\answer See [|ruzsa-et-al|] for partial results. The computer experiments
were done by V.\thinspace A. "Vyssotsky".
\source{[|erdos-graham|, p.~71].}
\ex:
Is $2n\choose n$ divisible either by $4$ or by $9$, for all $n>4$ except
$n=64$ and $n=256$?
\answer If $n$ is not a power of $2$, $2n\choose n$ is a multiple of~$4$
because of exercise~|bc-div-p|. Otherwise the stated phenomenon
was verified for $n\le2^{22000}$ by A.~"Granville" and O.~"Ramar\'e",
who also sharpened a theorem of S\'ark\"ozy [|sarkozy|]
by showing that $2n\choose n$ is divisible by the square of a prime for
all $n>2^{22000}$. This established a long-standing conjecture that
$2n\choose n$ is never "squarefree" when $n>4$.\par
The analogous conjectures for cubes are that $2n\choose n$ is divisible
by the cube of a prime for all $n>1056$, and by either $2^3$ or $3^3$ for
all $n>2^{29}+2^{23}$. This has been verified for all $n<2^{10000}$.
Paul "Erd\H os" conjectures that, in fact,
$\max_p \epsilon_p\bigl({2n\choose n}\bigr)$ tends to infinity as $n\to\infty$;
this might be true even if we restrict $p$ to the values $2$ and~$3$.
\source{[|erdos-graham|, p.~71].}
\ex:
If $t(n+1,k)/t(n,k)$ and $t(n,k+1)/t(n,k)$ are rational functions of $n$
and~$k$, and if there is a nonzero linear difference operator $H(N,K,n)$ such
that $H(N,K,n)@t(n,k)=0$, does it follow that $t(n,k)$ is a "proper term"?
\answer The theorem about generating functions in exercise 7.|d-finite-defined|
may help resolve this conjecture.
\source{"Wilf" and "Zeilberger" [|wilf-zeil|].}
\ex:
Let $m$ be a positive integer, and define the sequence $c_n^{(m)}$ by the
recurrence
\begindisplay
\sum_k{n\choose k}^{\!m}{n+k\choose k}^{\!m}=
\sum_k{n\choose k}{n+k\choose k}\,c_k^{(m)}\,.
\enddisplay
Are these numbers $c_n^{(m)}$ integers?
\answer "Strehl" [|strehl|] has shown that $c_n^{(2)}=\sum_k{n\choose k}^3
=\sum_k{n\choose k}^2{2k\choose n}$
is a so-called "Franel number"~[|franel|], and that $c_n^{(3)}=
\sum_k{n\choose k}{}^2{2k\choose k}{}^2{2k\choose n-k}$.
In another direction, H.\thinspace S. "Wilf" has shown that
$c_n^{(m)}$ is an integer for all~$m$ when $n\le9$.
\source{"Strehl" [|strehl|] credits A. "Schmidt".}