5
$\begingroup$

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) ?

$\endgroup$
  • 1
    $\begingroup$ Use f[n_, k_] = FunctionExpand[ Binomial[n, k] Binomial[x, k + r]/Binomial[n + x, n + r]]; $\endgroup$ – Daniel Lichtblau Mar 21 '17 at 23:19
  • $\begingroup$ Thanks for the answer. That's the sort of thing I was hoping for. $\endgroup$ – JEP Mar 23 '17 at 13:53
  • $\begingroup$ @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]. $\endgroup$ – Dr. Wolfgang Hintze Apr 22 '17 at 17:09
  • $\begingroup$ 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. $\endgroup$ – JEP Apr 23 '17 at 17:43
1
$\begingroup$

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})) $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.