# Wilf-Zeilberger simplification

I am working my way through the book "A=B" and doing some of the problems. One of them was to prove that:

$$\frac{1}{{n+x \choose n+r}} \sum_{k=0}^n{n \choose k}{x\choose k+r}=1$$

I am able to verify the proof using Wilf-Zeilberger theory with the following code:

f[n_, k_] = Binomial[n, k] Binomial[x, k + r]/((n + x)!/((x - r)! (n + r)!));

pc[n_, k_] = (k (k + r))/((n + x + 1) (k - n - 1));
g[n_, k_] = pc[n, k] f[n, k];

Print["Wilf-Zeilberger certification:",
FullSimplify[f[n + 1, k]-f[n, k] - g[n, k + 1] + g[n, k]]];


Here, f and g are said to constitute a "Wilf-Zeilberger pair" with "proof certificate", pc. The above code returns:

Wilf-Zeilberger certification:0


as it should.

My problem is that I had to write out the first binomial factor $\frac{1}{{n+x \choose n+r}}$ replacing it by hand with $\frac{1}{ \frac{(n+x)!}{(x-r)!(n+r)!}}$. The following code would be preferred in applications as you don't want to expand stuff by hand because it is error prone:

fB[n_, k_] = (Binomial[n, k] Binomial[x, k + r])/Binomial[(n + x), (n + r)];

Print["f-fB=", FullSimplify[f[n, k] - fB[n, k]]];

gB[n_, k_] = pc[n, k] fB[n, k];

Print["g-gB=", FullSimplify[g[n, k] - gB[n, k]]];

Print["Wilf-Zeilberger certification:",
FullSimplify[fB[n + 1, k]-fB[n,k]-gB[n, k + 1]+gB[n, k]]]


The first two lines are just to show that both f and fB are equal as are g and gB. When I attempt the Wilf-Zeilberger certification I get a mess.

f-fB=0
g-gB=0


Wilf-Zeilberger certification: ((k^2+(1+n) (1+n+x)-k (1+n-r+x)) Binomial[n,k] Binomial[x,k+r])/((-1+k-n) (1+n+x) Binomial[n+x,n+r])-((1+k) (1+k+r) Binomial[n,1+k] Binomial[x,1+k+r])/((k-n) (1+n+x) Binomial[n+x,n+r])+(Binomial[1+n,k] Binomial[x,k+r])/Binomial[1+n+x,1+n+r]

I presume the mess is "correct" but it is far from obvious the complicated expression above equals 0 as it should. How can I use the preferred input (with the three binomial factors and no explicit factorials) to obtain the preferred output (0) ?

• Use f[n_, k_] = FunctionExpand[ Binomial[n, k] Binomial[x, k + r]/Binomial[n + x, n + r]]; – Daniel Lichtblau Mar 21 '17 at 23:19
• Thanks for the answer. That's the sort of thing I was hoping for. – JEP Mar 23 '17 at 13:53
• @JEP I don't see the problem. My Version 10.1.0 gives immediately Sum[Binomial[n, k] Binomial[x, k + r]/Binomial[n + x, n + r], {k, 0, n}] -> 1 or Sum[Binomial[n, k] Binomial[x, k + r], {k, 0, n}] -> Binomial[n + x, n + r]. – Dr. Wolfgang Hintze Apr 22 '17 at 17:09
• I wasn't trying to show that Mathematica can evaluate the sum. I am trying to learn Wilf-Zeilberger theory. Wilf-Zeilberger theory is used to prove combinatoric identities such as this example. – JEP Apr 23 '17 at 17:43

JEP, FunctionExpand[ ] will often get it for you, but sometimes the results will look nothing like what you want them to. For example, if I use FunctionExpand[ ] in this expression... $$\frac{(2 k-1)\text{!!} (-2 k+2 \text{nn}+1)\text{!!}}{(2 k-2)\text{!!} (2 \text{nn}-2 k)\text{!!}}$$ I get this, even after assuming variables are integers, > 0, etc. $$\frac{(2 k-1) \Gamma \left(k-\frac{1}{2}\right) \left(\frac{2}{\pi }\right)^{\frac{1}{4} \cos (\pi (2 \text{nn}-2 k))-\frac{1}{4} \cos (\pi (-2 k+2 \text{nn}+1))+\frac{1}{2} (-1)^{2 k}} \Gamma \left(-k+\text{nn}+\frac{3}{2}\right)}{\Gamma (k) \Gamma (-k+\text{nn}+1)}$$ Mathematica then struggles to prove leftSide = rightSide for whatever it is I am proving.

My recommendation is to download the fastZeil package from the RISC site. It implements the Zeilberger Algorithm, and does a fine job dissecting the input function and generating a recurrence. This is linked to by the page for the "A=B" book. It will absorb the various odd double factorials, pochhammers, and binomials, generate the proof certificates for you, and generate a nice proof expression.

I ran your example through it, and got...

In: Zb[fB[nn, k], {k, 0, nn}, nn]
Out: If nn' is a natural number, then:
{SUM[nn]] - SUM[1 + nn]] == 0}
`

$$R(k,\text{nn})=\frac{k (k+r)}{(-k+\text{nn}+1) (\text{nn}+x+1)}$$ and $$F(k,\text{nn})-F(k,1+\text{nn})=\Delta _k(F(k,\text{nn}) R(k,\text{nn}))$$

• This problem is in Chapter 2 of A=B. They don't explain the use of Zb until Chapter 6. – JEP Mar 23 '17 at 18:38