\input amstex
\documentstyle{amsppt}


\headline=               
{\ifnum\pageno=1\hfil
 \else\vbox{\line {\tenit 
Knuth's old sum
 \hfil\tenrm\number\pageno}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13




\NoBlackBoxes
\TagsOnRight
\topmatter

\title 
Knuth's old sum --- a survey
\endtitle
\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics 
Technical University of Vienna, Austria
\endaffil
\address
Helmut Prodinger\newline
Department of Algebra and Discrete Mathematics \newline
 TU Vienna\newline
 Wiedner Hauptstrasse 8-10\newline A-1040 Vienna\newline Austria
\endaddress 
\abstract We take an old combinatorial sum of Knuth as an example
to show several methods of finding a closed form. Particularly,
we want to emphasize the algorithmic approach of Zeilberger. 
It is interesting to note that the sum in question appears already
in Riordan's book, where it is labelled `Reed Dawson'.
\endabstract
\endtopmatter

\document

\head 1.Introduction \endhead

The sum in question is
$$
f(n)=\sum_{k\ge0}\binom{n}{k}\binom{2k}{k}\Big(-\frac{1}{2}\Big)^k.
$$
I want to give several methods of evaluation from the literature, 
featuring especially the algorithmic aspect of combinatorial sums.

I am not a real specialist, but I like the subject, and I hope, other
people will (learn to) like it as well.

\head 2. The original approach of Jonassen  and Knuth \endhead


This one is long and elementary, \cite{4}. We give only the key steps.

Using the recursion for the binomial coefficients (``Pascal's
triangle'') they find
$$
f(n)=f(n-1)+\sum_{k}\binom{n-1}{k}\binom{2k}{k}\Big(-\frac{1}{2}\Big)^k.
$$
Pulling out parts of the sum they halt at
$$
f(n)=-f(n-1)+\frac1n
\sum_{k}\binom{n}{k+1}\binom{2k}{k}\Big(-\frac{1}{2}\Big)^k.
$$
This one will be multiplied by $n$; then the corresponding equation
where $n$ is replaced by $n-1$ is written down. The difference of the
2 equations allows finally to evaluate the extra sum;
$$
n\big(f(n)+f(n-1)\big)-(n-1)\big(f(n-1)+f(n-2)\big)=f(n-1),
$$
or finally
$$
nf(n)=(n-1)f(n-2).
$$
Since $f(0)=1$ and $f(1)=0$, the $f(2m+1)$'s are all equal to zero,
and
$$\align
f(2m)&=\frac{2m-1}{2m}f(2m-2)=\frac{2m-1}{2m}\frac{2m-3}{2m-2}\dots\frac12\\
&=\frac{1}{2^mm!}\frac{(2m)!}{2^mm!}=\frac{1}{4^m}\binom{2m}{m}.
\endalign
$$
Therefore the answer is
$$\boxed{
f(n)=\cases \frac{1}{2^n}\binom n{n/2} \qquad & \text{$n$ even}\\
0 \qquad & \text{$n$ odd}.
\endcases
}$$








\head 3. The proof of Ira Gessel \endhead

This proof is reported in \cite{3} and is as follows.

First, interchange the order of summation,
$$
f(n)=\sum_{k\ge0}\binom{n}{k}\binom{2n-2k}{n-k}\Big(-\frac{1}{2}\Big)^{n-k}.
$$















Now, express the binomial coefficients as coefficients in appropriate
generating functions,
$$
\binom{n}{k}\Big(-\frac{1}{2}\Big)^{-k}
=[x^k](1-2x)^n
$$
and
$$
\binom{2n-2k}{n-k}
=[y^{n-k}](1+y)^{2n-2k}=[y^{n}]y^k(1+y)^{2n-2k}.
$$
Hence
$$
f(n)=\Big(-\frac{1}{2}\Big)^{n}
[y^n](1+y)^{2n}\sum_{k}[x^k](1-2x)^n\Big(\frac{y}{(1+y)^2}\Big)^k.
$$
But
$$\sum_{k}u^k[v^k]g(v)=g(u),$$
and thus
$$
\align
f(n)&=\Big(-\frac1{2}\Big)^{n}
[y^n](1+y)^{2n}\left(1-2\frac{y}{(1+y)^2}\right)^n\\
&=\big(-{2}\big)^{-n}
[y^n]\left(1+y^2\right)^n
\endalign
$$
The answer is now obvious.

\head 3. The approach of C.C. Rousseau \endhead

This one is also reported in \cite{3}.

First,
$$
\binom{2k}k=[x^0]\left(x+\frac{1}{x}\right)^{2k}.
$$
Now
$$
\left(1-  \frac{\left(x+\frac{1}{x}\right)}{2}^2\right)^n=
\sum_{k=0}^n\binom nk\Big(-\frac12\Big)^k
\left(x+\frac{1}{x}\right)^{2k},$$
and
$$
f(n)=[x^0]\left(1-\frac{\left(x+\frac{1}{x}\right)}{2}^2\right)^n=
[x^0]\left(x^2+x^{-2}\right)^n,
$$
from which the answer is now immediate.

\head 4. My solution \endhead

In \cite{7} I gave a simple solution based on the so-called {\sl
Euler transformation}.

First, in general, if
$$
A(z)=\sum_{k}a_kz^k,
$$
then
$$
\frac{1}{1-z}A\Big(\frac{z}{1-z}\Big)=\sum_{n}z^n\sum_{k}\binom nk a_k.
$$
This is not hard to see:
$$
\align
\frac{1}{1-z}A\Big(\frac{z}{1-z}\Big)&=\sum_{m}\frac{1}{(1-z)^{m+1}}
a_mz^m\\
&=\sum_{m}\sum_{j}\binom{m+j}{j}z^ja_mz^m\\
&=\sum_{n}z^n\sum_{k}\binom nk a_k.
\endalign
$$
If we apply this principle to Knuth's sum, then
$$
\sum_{n}f(n)z^n=\frac{1}{1-z}A\Big(\frac{z}{1-z}\Big),
$$
with
$$
A(z)=\sum_{n}\binom{2n}{n}\Big(-\frac{1}{2}\Big)^nz^n=\frac{1}{\sqrt{
1-4\frac{-z}{2}}}=\frac{1}{\sqrt{1+2z}}.
$$
Hence
$$
\sum_{n}f(n)z^n=\frac{1}{1-z}\sqrt{\frac{1-z}{1+z}}
=\frac{1}{\sqrt{1-z^2}},
$$
and
$$
f(n)=[z^n]\frac{1}{\sqrt{1-z^2}}.
$$
From this the answer is immediate.

\medskip

Let's see whether we can say something more general. Since
$\binom{2k}{k}=\binom{-\frac12}{k}(-4)^k$, we write more generally
$$
\sum_{k=0}^n\binom{n}{k}\binom{a}{k}q^k,
$$
where $ a=-\frac12$ and $q=2$ means Knuth's sum.
The generating function is now
$$
\frac{1}{1-z}\left(1+\frac{qz}{1-z}\right)^a=\frac{\big(1+(q-1)z\big)^a}{
(1-z)^{a+1}}.
$$
When do we get a closed form? If $a$ is a natural number, which is obvious,
since the sum itself is of closed form (only $a+1$ terms), or if $a+1=-m$
is a negative integer,  since it is then
$$
\sum_{j=0}^m\binom{m}{j}(-1)^j(q-1)^{n-j}\binom{-m-1}{n-j}.
$$
If $a=-\frac12$, we get for the generating function
$$
\frac{1}{\sqrt{1+(q-2)z+(q-1)z^2\,}},
$$
and we see that $q=2$ gives Knuth's sum, while $q=1$ corresponds to
the Vandermonde formula, which is of course also of closed form.





\head 5. Riordan's approach \endhead

Recently, I found out that the famous book of Riordan \cite{8, page 71}
contains a solution as well. However, the identies are credited to
{\sl Reed Dawson}.

Riordan writes $a_n=2^{-n}\binom{2n}{n}$, $b_n=f(n)$ and notes the recursion
$$
a_n=2a_{n-1}-\frac{1}{n}a_{n-1}.
$$
The formula
$$
b_n=\sum_{k}\binom nk(-1)^ka_k
$$
means {\sl umbrally}
$$
b_n=(1-a)^n,\qquad a^k\equiv a_k.
$$
Like Jonassen and Knuth he writes
$$
b_n=-b_{n-1}+\frac{1}{n}\sum_{k}\binom{n}{k+1},
$$
which leads to
$$
c_n:=n(b_n+b_{n-1})=c_{n-1}+b_{n-1}.
$$
The $c_{n-1}$ may now be eliminated, leading to $nb_n=(n-1)b_{n-1}$,
The rest is as before.

This proof and the one of Jonassen and Knuth are very similar.

\smallskip

Riordan also gives some additional formul\ae\ and generalizations.






\head 6. Hypergeometric series\endhead

We refer to \cite{2} for this.\smallskip
We start from the reversed summation,
$$
f(n)=\sum_{k\ge0}\binom{n}{k}\binom{2n-2k}{n-k}\Big(-\frac{1}{2}\Big)^{n-k}.
$$
and compute the ratio $t_{k+1}/t_k$ of 2 consecutive terms:
$$
\frac{t_{k+1}}{t_k}=\frac{n-k}{k+1}\frac{n-k}{2n-2k}\frac{n-k}{2n-2k-1
}(-2)=\frac{(k-n)^2}{k-n+\frac12}\frac12.
$$
Since $t_0=\binom{2n}{n}(-\frac12)^n$, we have the following representation
of $f(n)$ as a hypergeometric series,
$$
f(n)=\binom{2n}{n}\Big(-\frac12\Big)^nF\left({{-n,-n}\atop {-n+\frac12}}
\Big|\frac12\right).
$$
But there is an identity of Gauss,
$$
F\left({{2a,2b}\atop {a+b+\frac12}}\Big|\frac12\right)=
F\left({{a,b}\atop {a+b+\frac12}}\Big|1\right),
$$
and we therefore find
$$f(n)=\binom{2n}{n}\Big(-\frac12\Big)^nF\bigg({{-\frac n2,-
\frac n2}\atop {-n+\frac12}}
\Big|1\bigg).
$$
But such a series can be evaluated by another formula of Gauss;
$$
F\left({{a,b}\atop {c}}\Big|1\right)
=\frac{\Gamma(c-a-b)\Gamma(c)}{\Gamma(c-a)\Gamma(c-b)}.
$$
Hence we can conclude that
$$
f(n)=\binom{2n}{n}\Big(-\frac12\Big)^n
\frac{\Gamma(\frac12)\Gamma(-n+\frac12)}{\Gamma^2(-\frac n2+\frac12)}.
$$
This formula gives already that $f(n)=0$ for odd $n$, since we
have ``infinity'' in the denominator. Let's now concentrate on even 
$n=2m$.

The functional equation for the $\Gamma$--function gives
$$
\Gamma\big(\frac12\big)=\big(-\frac12\big)\big(-\frac32\big)\dots
\big(-m+\frac12\big)\Gamma\big(-m+\frac12\big)
$$
and
$$
\Gamma\big(-m+\frac12\big)=\big(-m-\frac12\big)\big(-m-\frac32\big)\dots
\big(-2m+\frac12\big)\Gamma\big(-2m+\frac12\big).
$$
Hence
$$\aligned
\frac{\Gamma(\frac12)\Gamma(-n+\frac12)}{\Gamma^2(-\frac n2+\frac12)}&=
\frac{\big(-\frac12\big)\big(-\frac32\big)\dots
\big(-m+\frac12\big)}{\big(-m-\frac12\big)\big(-m-\frac32\big)\dots
\big(-2m+\frac12\big)}\\
&=\frac{1\cdot3\dots(2m-1)}{(2m+1)(2m+3)\dots(4m-1)}\\
&=\frac{\big[1\cdot3\dots(2m-1)\big]^2}{1\cdot3\dots(4m-1)}
\endaligned
$$
But
$$
1\cdot3\dots(2m-1)=\frac{(2m)!}{2^mm!},
$$
and
so
$$
f(2m)=\binom{4m}{2m}
\frac{1}{4^m}\left[\frac{(2m)!}{2^mm!}\right]^2\cdot
\frac{4^m(2m)!}{(4m)!}=\frac1{4^m}\binom{2m}{m},
$$
as desired.

\head 7. Sister Celine's technique \endhead

I follow the description as to be found in \cite{9}.

We write
$$
f(n)=\sum_{k\ge0}F(n,k)$$
with
$$
F(n,k)=\binom{n}{k}\binom{2k}{k}\Big(-\frac{1}{2}\Big)^k.
$$
We are looking for a non-trivial solution of
$$
\sum_{i=0}^2\sum_{j=0}^2a_{ij}(n)F(n-j,k-i)=0.
$$
For that, we divide by $F(n,k)$ and cancel out common factors:
$$
\align
&1-a_{10}(n)\frac{k^2}{(2k-1)(n-k+1)}+
a_{20}(n)\frac{k^2(k-1)^2}{(2k-1)(2k-3)(n-k+1)(n-k+2)}\\
&+a_{01}(n)\frac{n-k}{n}-a_{11}(n)\frac{k^2}{(2k-1)n}
+a_{21}(n)\frac{k^2(k-1)^2}{(2k-1)(2k-3)(n-k+1)n}\\
&+a_{02}(n)\frac{(n-k+1)(n-k)}{(n-1)n}
-a_{12}(n)\frac{k^2(n-k)}{(2k-1)(n-1)n}\\ &
+a_{22}(n)\frac{k^2(k-1)^2}{(2k-1)(2k-3)(n-1)n}=0
\endalign
$$
We multiply this by the common denominator
$$
(2k-1)(2k-3)(n-k+1)(n-k+2)(n-1)n,
$$
sort with respect to powers of $k$ and set all those coefficients $=0$.
We don't want to write down these 7 equations, but { Maple} finds
the general solution for us:
$$
\align
&
Cn^2F(n,k) +Bn(n-1) F(n,k-1)\\
&-Cn(2n-1)F(n-1,k)+(2n-1)(Cn-Bn+B)  F(n-1,k-1) \\ & +B(2n-1)(n-1)F(n-1,k-2)
+Cn(n-1)F(n-2,k)\\ &  +(n-1)(Bn-2Cn-B) F(n-2,k-1)-2B(n-1)^2 F(n-2,k-2)=0
\endalign
$$
We have the freedom to set $B=0$ and $C=1$ to get an easy recursion.
There is then a common factor $n$ which will be divided out:
$$
\align
&
nF(n,k) 
-(2n-1)F(n-1,k)+(2n-1) F(n-1,k-1) \\
&+(n-1)F(n-2,k) -2(n-1) F(n-2,k-1)=0
\endalign
$$
But now we can sum up these equations for all $k$ and get a recursion
for $f(n)$, the sum in question!
$$
nf(n)-(2n-1)f(n-1)+(2n-1)f(n-1)+(n-1)f(n-2)-2(n-1)f(n-2)=0,
$$
or simply
$$
f(n)=\frac{n-1}{n}f(n-2),
$$
from which the initial values $f(0)=1$ and $f(1)=0$ give us the result
as before.








\head 7. Zeilberger's algorithm \endhead

We cannot give the theoretical background of the algorithm. However,
it is available via anonymous ftp from {\tt math.temple.edu} in the
directory {\tt pub/Zeilberger\-/programs}. I used a modified version
which I obtained from Christian Krattenthaler.

It produces an answer like: ``There is a first-order recurrence
$$
\Big(n+1-(n+2)N^2\Big)f(n),
$$
where $N$ is the shift operator defined by $N\,f(n)=f(n+1)$.''

So, in conventional terms the recursion is
$$
(n+1)f(n)-(n+2)f(n+2).
$$
This recursion can be solved as before, which the program does automatically.

And you get a hint, how the solution is obtained (citation is not
verbally correct):

``Choose (cleverly)
$$
G(n,k)=-\frac{(2k+1)(n+1)}{n-k+1}F(n,k),
$$
then
$$
\Big(n+1-(n+2)N^2\Big)F(n,k)=G(n,k)-G(n,k-1),
$$
and the recursion follows upon summing on $k$.''

This is easy to check but a little bit mysterious if you don't know 
the theory behind it. 

\medskip

The second edition of ``Concrete Mathematics'' (just appeared) contains
a new section, emphasizing Zeilberger's algorithm.

\head 8. Koornwinder's implementation of Zeilberger's method \endhead

This Maple program gives you about this answer:
$$
\sum_{k=0}^m\Big(F(n,k)-\frac{n-1}{n}F(n-2,k)\Big)=
-\frac{(m+1)^2}{n^2}
F(n,m+1),
$$
which might be rephrased as
$$
F(n,k)-\frac{n-1}{n}F(n-2,k)=G(n,k+1)-G(n,k),
$$
with
$$
G(n,k)=-\frac{k^2}{n^2}F(n,k).
$$
Then it does, as the other one, the summation over $k$, causing the
right hand side to vanish (``telescoping''), and solves the resulting
recursion
$$
f(n)-\frac{n-1}{n}f(n-2)=0
$$
by iteration.


\head 9. Implementation of Paule and Schorn \endhead

There is also a Mathematica package doing Zeilberger's
algorithm \cite{6}, but I did not
work with it.

\head 10. WZ--Pairs \endhead

Now that we know that $f(n)$ vanishes for odd $n$, let's concentrate
on the even ones.

$$
f(2n)=\sum_{k\ge0}\binom{2n}{k}\binom{2k}{k}\Big(-\frac{1}{2}\Big)^k=
\frac{1}{4^n}\binom{2n}n.
$$
Write it as
$$
\sum_{k}F(n,k)=1,
$$
with
$$
F(n,k)=\frac{\binom{2n}{k}\binom{2k}{k}
(-\frac{1}{2})^k}{\frac{1}{4^n}\binom{2n}n}
=4^n\Big(-\frac12\Big)^k\frac{(2k)!n!^2}{k!^3(2n-k)!}.
$$
Now define
$$
R(n,k)=-\frac{k^2}{(2n-k+2)(2n-k+1)}
$$
and
$$\aligned
G(n,k)&=R(n,k)\cdot F(n,k)\\
&=-4^n\Big(-\frac12\Big)^k\frac{(2k)!n!^2}{k!(k-1)^2(2n-k+2)!}.
\endaligned
$$
Then it is easy to check (but not as easy to find this `certificate'
$R(n,k)$) that
$$
F(n+1)-F(n,k)=G(n,k+1)-G(n,k),
$$
Two discrete functions $F$ and $G$ which are related in this
way are termed ``WZ--pair'' (\cite{9}).

By summing on $k$, we obtain the recursion
$$
f(n):=\sum_{k}F(n,k)=f(n-1),
$$
which, together with $f(0)=1$ proves the identity again. But
the WZ--pair contains even more information!

\medskip

There is a dual WZ--pair, obtained in this way: 

Substitute all factorials
$(an+bk+c)!$ by $(-1)^{an+bk}/(-an-bk-c-1)!$, except in the case $a+b=0$,
then do nothing. This gives you the pair $\bar F, \bar G$. Finally,
change variables by
$$\aligned
F'(n,k)&:=\bar G(-k-1,-n)\\
G'(n,k)&:=\bar F(-k,-n-1).
\endaligned
$$
Doing that we obtain in our instance
$$\gather
F'(n,k)=(-1)^{n+1}\frac{2^n}{4^{k+1}}\frac{(n-1)!n!^2(2k-1-n)!}{(2n-1)!k!^2}\\
G'(n,k)=(-1)^{n+1}\frac{2^{n+1}}{4^{k}}\frac{n!^3(2k-2-n)!}{(2n+1)!(k-1)!^2}
\endgather
$$
Now we want -- in the usual way -- to define
$$
f'(n):=\sum_{k}F'(n,k).
$$
However, because of the $(2k-1-n)!$ term we have to be a little bit
careful. So define (only for $n\ge1$)
$$
f'(n):=\sum_{k\ge\lceil \frac{n+1}{2}\rceil}F'(n,k).
$$
Because of this dependency, summing up over $k$ in
$$
F'(n+1,k)-F'(n,k)=G'(n,k+1)-G'(n,k)
$$
does not simply let the right hand side disappear. We can only sum
up for $k\ge \lceil \frac{n}{2}\rceil+1$, but this gives us an extra term.
It is now wise to distinguish the cases $n$ even and $n$ odd. So we have
$$
F'(n+2,k)-F'(n,k)=G'(n+1,k+1)-G'(n+1,k)+G'(n,k+1)-G'(n,k).
$$
Now let's assume that $n$ is even, $n=2m$.
Then we can sum up for $k\ge m+2$, and obtain
$$
f'(2m+2)-\Big[f'(2m)-F'(2m,m+1)\Big]=-G'(2m+1,m+2)-G'(2m,m+2),
$$
or
$$
f'(2m+2)-f'(2m)=(3m+2)\frac{(2m+1)!(2m)!^2}{(4m+3)!m!(m+1)!^2}.
$$
Iterating this we find
$$
f'(2m+2)=f'(2)+\sum_{j=1}^{m}(3j+2)\frac{(2j+1)!(2j)!^2}{(4j+3)!j!(j+1)!^2}.
$$
Therefore we are going to compute
$$
f'(2)=-\frac23\sum_{k\ge2}
\frac{1}{4^{k}}\frac{(2k-3)!}{k!^2}
$$
An extremely boring computation produces the value
$$
f'(2)=-\frac12\log2+\frac13.
$$
It was done by Maple, starting from
$$
\sum_{k\ge0}\frac{(2k)!}{k!(k+1)!}z^k=\frac{1-\sqrt{1-4z\,}}{2z},
$$
by some subtractions, substitutions and integrations.

Finally we obtain the following identity
$$\boxed{
\aligned
&-4^m\frac{(2m-1)!(2m)!^2}{(4m-1)!}\sum_{k\ge m+1}
\frac{(2k-1-2m)!}{k!^2}\frac{1}{4^{k+1}}\\ &=
-\frac12\log2+\frac13+
\sum_{j=1}^{m-1}(3j+2)\frac{(2j+1)!(2j)!^2}{(4j+3)!j!(j+1)!^2}.
\endaligned
}
$$
One can even go one step further down, to $m=0$, since
$$
\lim_{m\to0}\frac{(2m-1)!}{(4m-1)!}=2.
$$
A similar computation as before (or an adaption of the previous formula)
evaluates
$$
f'(0)=-\frac{\log2}{2},
$$
and we have for $m\ge0$ (the index was shifted)
$$\boxed{
\aligned
&\frac{(2m-1)!(2m)!^2}{(4m-1)!}\sum_{k\ge 1}
\frac{(2k-1)!}{(k+m)!^2}\frac{1}{4^{k+1}}\\ &=
\frac12\log2-
\sum_{j=0}^{m-1}(3j+2)\frac{(2j+1)!(2j)!^2}{(4j+3)!j!(j+1)!^2}.
\endaligned
}
$$

This formula evaluates a certain infinite series, and it contains
about as many terms as the parameter.


For odd $n$ a similar formula could be produced. We leave it as an
exercise.






\head 11. Elimination \endhead

I follow Zeilberger's description in \cite{10}.
\smallskip

Let us again concentrate on the even values of $n$, that means, we
consider

$$
f(n):=\sum_{k}F(n,k)=\sum_{k}{\binom{2n}{k}\binom{2k}{k}
\big(-\frac{1}{2}\big)^k}.
$$
 
We use the shift operators $N$, defined by $NF(n,k)=F(n+1,k)$ and
$K$, defined by $KF(n,k)=F(n,k+1)$. 
We compute
$$
\aligned
\frac{F(n+1,k)}{F(n,k)}&=\frac{(2n+2)(2n+1)}{(2n+2-k)(2n+1-k)}\\
\frac{F(n,k+1)}{F(n,k)}&=-\frac{(2n-k)(2k+1)}{(k+1)^2}.
\endaligned
$$
Cross multiplication leads to
$$
\aligned
&
(2n+2-k)(2n+1-k)F(n+1,k)-(2n+2)(2n+1)F(n,k)=0\\
&
(k+1)^2F(n,k+1)-(k-2n)(2k+1)F(n,k)=0.
\endaligned
$$
Or, in operator notation:
$$\aligned
\Big[(2n+2)(2n+1)(N-1)-k(4n+3)N+k^2N\Big]F(n,k)&\equiv 0\\
\Big[(K-2)k^2+k(4n-1)+2n\Big]F(n,k)&\equiv 0
\endaligned
$$
Observe that $(4n+3)N$ in the first equivation can be replaced by
$N(4n-1)$.
Define the operators $P,Q$ by
$$\aligned
P&=(2n+2)(2n+1)(N-1)-kN(4n-1)+k^2N\\
Q&=(K-2)k^2+k(4n-1)+2n.
\endaligned
$$
Now compute
$$
\aligned
NQ+P&=N(K-1)k^2+2Nn+(2n+2)(2n+1)(N-1)\\
&=N(K-1)k^2+4(n+1)^2N-(2n+2)(2n+1)
\endaligned
$$
Now it has a nice form; $K-1$ times something $+$ something independent
of $K$ and $k$.

Apply it to $F(n,k)$:
$$
4(n+1)^2F(n+1,k)-(2n+2)(2n+1)F(n,k)=
G(n+1,k)-G(n,k),
$$
with
$$
G(n,k):=-Nk^2F(n,k)=\binom{2n+2}{k}\binom{2k}{k}k^2
\Big(-\frac{1}{2}\Big)^{k+1}.
$$
Now the right hand side telescopes upon summing on $k$, and we find
$$
4(n+1)^2f(n+1)-(2n+2)(2n+1)f(n)=0,
$$
which we simplify to
$$
2(n+1)f(n+1)-(2n+1)f(n)=0,
$$
or
$$f(n)=\frac{2n-1}{2n}f(n-1).
$$
Now, $f(0)=1$, and we obtain our usual answer
$$
f(n)=\frac{1}{4^n}\binom{2n}{n}
$$
again by iteration. 

\medskip

Now, if we apply the whole procedure to the original thing,
$$
f(n):=\sum_{k}F(n,k)=\sum_{k}{\binom{n}{k}\binom{2k}{k}
\big(-\frac{1}{2}\big)^k},
$$
we find
$$
\aligned
\frac{F(n+1,k)}{F(n,k)}&=\frac{n+1}{n+1-k}\\
\frac{F(n,k+1)}{F(n,k)}&=-\frac{(n-k)(2k+1)}{(k+1)^2}.
\endaligned
$$
The operators are this time
$$\aligned
P&=-Nk+(n+1)(N-1)\\
Q&=(k+1)^2K+2kn-2k^2+n-k.
\endaligned
$$
Since $Q=(K-1)k^2-k^2+2kn+n-k$, we can continue with $P$ and
$Q_1:=-k^2+2kn+n-k$. First, we have to get rid of the $k^2$--term,
whence we compute
$$
Q_2:=NQ_1-kP=k(nN+n+1)+Nn.
$$
We now want to use $P$ and $Q_2$ in order to get rid of the $k$--term.
However, when trying to get the coefficient at $k$ in both operators
equal,
we have to be a little bit careful, since only multiplication from the
left is allowed!
Thus we compute
$$
\big(Nn+n+2\big)P+NQ_2=(n+2)^2N^2-(n+2)(n+1).$$
We can divide by one factor $n+2$ and get the recursion
$$
(n+2)f(n+2)-(n+1)f(n),
$$
which is of course the usual one.

















\head 12. A contour integral for $f(n)$ \endhead

We might write
$$
f(n)=\sum_{k=0}^n\binom{n}{k}(-1)^k\varphi(k),
$$
with
$$
\varphi(k)=\binom{2k}{k}\big(\frac{1}{2}\big)^k.
$$
Since there is a ``continuation'' of $\varphi(k)$ to the complex plane via
$$
\varphi(z)=\frac{\Gamma(2z+1)}{\Gamma^2(z+1)}2^{-z},
$$
we have
$$
f(n)=- \frac{1}{2\pi i}\int_{\Cal C}\frac{\Gamma(n+1)\Gamma(-z)}{
\Gamma(n+1-z)}f(z)\, dz,
$$
where $\Cal C$ is positively oriented and encircles (exactly) the poles
$0,1,\dots,n$ of the integrand.

Such an integral is sometimes called a Rice--integral, see the recent
survey \cite{1}.

Here, this representation is probably not too useful.

\head 13. Addendum (June 28, 1994) \endhead

Herbert Wilf's book ``generatingfunctionology'' also discusses the sum,
in a manner that closely resembles the one discussed in section 4.
\medskip

Christian Krattenthaler has written a Mathematika package ``HYP''
that is very convenient for dealing with hypergeometric series.
It does the derivation in section 6 in a
half--automatic way.









\Refs

\ref\no1 \by P.Flajolet, R.Sedgewick\paper Mellin transforms and asymptotics:
Finite differences and Rice's integrals \jour Theoret. Comput. Sci.
\toappear
\yr 1994
\endref

\ref\no2 \by R.Graham,  D.E.Knuth, and O.Patashnik
\book Concrete Mathematics 
 \publ Addison-Wesley \yr 1989
\endref

\ref\no3 \by D.Greene and D.E.Knuth\book Mathematics for the Analysis
of Algorithms \publ Birkh\"auser \yr 1981
\endref

\ref \no4 \by A.Jonassen and D.E.Knuth\paper A trivial algorithm
whose analysis isn't\jour Journal of Computer and System Sciences
\vol16\pages301--322\yr1978
\endref

\ref \no5 \by T.Koornwinder \paper On Zeilberger's algorithm and its
$q$-analogue: a rigorous description \jour J. of Comput. and
Appl. Math. \vol 48\pages 91--111\yr1993
\endref

\ref \no6 \by P.Paule and M.Schorn \paper A Mathematica Version
of Zeilberger's Algorithm for Proving Binomial Coefficient Identities
\jour J. Symb. Comput. \toappear
\endref

\ref \no 7 \by H.Prodinger\paper Some information about the binomial
transform
\jour The Fibonacci Quarterly
\vol  \yr 1994 \toappear \endref


\ref \no8 \by J.Riordan\book Combinatorial Identities\yr 1968\publ
John Wiley 
\endref


\ref\no9 \by H.Wilf \book Identities (and their computer proofs)
\publ available by {\tt ftp ftp.cis.upenn.edu} as file
{\tt pub/wilf/lecnotes.ps}\yr1993
\endref

\ref\no10 \by D.Zeilberger \paper 3 Recitations on Holonomic Systems
and Hypergeometric Series \jour 
available by {\tt ftp nath.temple.edu} in the directory
{\tt pub/zeilberger/papers}\yr1993
\endref

\endRefs


\enddocument

