Help with a double sum, please

Here is a double series I have been having trouble evaluating: $$S=\sum_{k=0}^{m}\sum_{j=0}^{k+m-1}(-1)^{k}{m \choose k}\frac{[2(k+m)]!}{(k+m)!^{2}}\frac{(k-j+m)!^{2}}{(k-j+m)[2(k-j+m)]!}\frac{1}{2^{k+j+m+1}}\text{.}$$

I am confident that $S=0$ for any $m>0$. In fact, I have no doubt. I have done lots of algebraic manipulation, attempted to "convert" it to a hypergeometric series, check tables (Gradshteyn and Ryzhik), etc., but I have not been able to get it into a form from which I can prove zero equivalence.

Here is another form of the sum (well, I hope at least) that might be easier to work with:

$$S=\sum_{k=0}^{m}\sum_{j=0}^{k+m-1}(-1)^{k}\frac{m!}{k!(m-k)!}\frac{(k+m-1-j)!}{(k+m)!}\frac{(k+m-1/2)!}{(k+m-1/2-j)!}\frac{1}{2^{k-j+m+1}}\text{.}$$

I have read Concrete Mathematics and $A=B$, and looked at Gosper's and Zeilberger's work for some hints, but no cigar.

Note: $0!=1$ and $n!=n(n-1)!$ for $n\in\mathbb{N}\cup\{0\}$. For $n\in\mathbb{R}^+$, $n!=n\Gamma(n)$ where $\Gamma\colon\: \mathbb{C}\to\mathbb{C}$ and, for $\Re z>0$ and $z\notin\mathbb{Z}^{-}$, $$\Gamma\colon\: z\mapsto \int_0^\infty t^{z-1}\mathrm{e}^{-t}\,\mathrm{d}t\text{.}$$ which can be analytically extended to $\mathbb{C}$ via the recurrence $\Gamma(z+1)=z\Gamma(z)$.

-
To whom it may concern: I have also verified this identity by computer for all natural m up to 200. –  aorq Jan 24 '10 at 5:02
You can ask Zeilberger (who is very responsive). You will both benefit: you will have your solution, and he will prove once again that his computer is smarter than all human combined –  David Lehavi Jan 24 '10 at 9:40
@David: Is that meant to be a joke or an insult to Zeilberger? When I first read it I thought it was an insult, just so you know. –  Andrej Bauer Jan 29 '10 at 8:52
@Andrej: Read some of Zeilberger's own work, where he himself makes similar claims. He's got papers which were (essentially) written by his computer; he puts his computer as co-author on his papers often enough. –  Jacques Carette Feb 20 '10 at 15:57
Isn't Zeilberger the ‘author’ of the famous quote “My computer has written more papers than you have” (directed at some upstart faculty member, perhaps)? –  L Spice Mar 4 '10 at 16:18

8 Answers

Olivier Gerard just told me about this wonderful website! Regarding the question it can be done in one nano-second using the Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/MultiZeilberger

accopmaying my article with Moa Apagodu

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html

Here is the command:

F:=(-1)^k*binomial(m,k)*(k+m-1-j)!/(k+m)!*simplify((k+m-1/2)!/(k+m-1/2-j)!)/2^(k-j): lprint(MulZeil(F,[j,k],m,M,{})[1]);

and here is the output: -1/4*(2*m+1)/(m+1)+M

(Note that I had to divide the summand by 1/2^(m+1) if you don't you get FAIL, the prgram does not like extraneous factors)

Translated to humaneze we have that (my S(m) is hte original S(m) times 2^(m+1)) S(m+1)=(2m+1)/(m+1)S(m)

Since S(1)=0 (check!) This is a completely rigorous proof.

P.S. The proof can be gotten by finding the so-called multi-certificate

lprint(MulZeil(F,[j,k],m,M,{})[2]);

-Doron Zeilbeger

-
Welcome to the neighborhood! –  Steven Gubkin May 4 '10 at 14:42
I enthusiastically second that. –  gowers May 4 '10 at 20:34

are you sure about S=0 for m>0 ? Check for some values please. So you have,

$$$(-1)^k \frac{2^{-1+j-k-m} \Gamma[1+m] \Gamma\left[\frac{1}{2}+k+m\right] \Gamma[-j+k+m]}{\Gamma[1+k] \Gamma[1-k+m] \Gamma[1+k+m] \Gamma\left[\frac{1}{2}-j+k+m\right]}$$$

-
I checked for $0 < m \le 50$. –  Quadrescence Jan 24 '10 at 4:44
scott, for downvoting my comments all along, it's kinda pathetic .... –  steve Jan 24 '10 at 6:59
The poster of this answer doesn't have enough rep to comment, so perhaps downvoting is unwarranted. However, Steve, I am mystified by your comment to Scott. –  Jonas Meyer Jan 24 '10 at 7:41
@Steve, I'm mystified too -- I didn't downvote you here, or anywhere else I can tell. My email is in my profile if you'd like to explain. –  Scott Morrison Jan 24 '10 at 17:37
I'm pretty sure that only moderators have any way to do that. At least, they can look at the voting history of each user, even if they can't see directly the source of a vote on a given answer/question. The fact that no one else can even see voting histories (if I'm correct) is part of why I was so mystified. –  Jonas Meyer Jan 30 '10 at 6:03

Shall we try teamwork? Please feel free to edit this post if you have simplifications.

The original sum may be re-expressed as $$\frac{1}{2^{2m+1}} \sum_{k=0}^m (-1)^k \binom{m}{k} \binom{2(k+m)}{k+m} \frac{1}{2^{2k}} \sum_{j=0}^{k+m-1} \frac{2^{k+m-j}}{(k+m-j) \binom{2(k+m-j)}{k+m-j}}.$$ If we're trying to prove this is 0, we may drop the fraction out front. Also, change variables from $j$ to $\ell=k+m-j$: $$\sum_{k=0}^m \left( -\frac14 \right)^k \binom{m}{k} \binom{2(k+m)}{k+m} \sum_{\ell=1}^{k+m} \frac{2^\ell}{\ell \binom{2\ell}{\ell}}.$$ At this point, my idea was to change the order of summation based on $$\sum_{k=0}^m \sum_{\ell=1}^{k+m} \Diamond = \sum_{\ell=1}^m \sum_{k=0}^m \Diamond + \sum_{\ell=m+1}^{2m} \sum_{k=\ell-m}^m \Diamond,$$ but I can't get quite it to work out. The first sum simplifies, but the second sum I can't do much with.

Any ideas?

-
One idea I was thinking was to split the sum into positive and negative pieces with the $(-1)^k$ and prove the resulting sums are equal. Though I didn't have much luck with the approach. –  Quadrescence Jan 24 '10 at 6:27
I tried replacing (-1)^k by x^k, and looked at the resulting polynomials. The first few factored with a (1+x) term times an irreducible term with no obviously helpful pattern. Clearing denominators didn't turn up anything in the OEIS. –  Douglas Zare Jan 24 '10 at 9:50

Better than reading A=B, you should download and learn to use their Mathematica package. I've used it successfully in the past to obtain automagic proofs of similar identities.

-
Well, this is a particularly difficult sum since it's not hypergeometric, which is what many sums dealt with via Zeilberger's and related methods are good at. It'd be particularly hard to convert this into a holonomic recurrence with the $2^{-j}$, no? Anyway, I haven't tried $A=B$ packages specifically, but I have tried using computer algebra systems with their summation algorithms to at least evaluate it even without proof. –  Quadrescence Jan 24 '10 at 6:22
There is a version of Gosper-Zeilberger for hypergeometric double sums as well (the whole machinery works for multiple sums as well, at least theoretically). The Mathematica packages are done by RISC people in Linz, Austria. –  Wadim Zudilin Apr 17 '10 at 12:39

Let's define $$\beta_n \doteq \sum_{i\le (n-1)/2 } \binom{n-(i+1)}{i} (-1)^i \frac{1}{ (2i+1) 2^{2i+1} }.$$ The following problem is equivalent to proving that $S=0$: prove that the sequence $\beta_n$ satisfies the recursion $$\beta_{n+1} = \frac{2n+1}{2n+2} \beta_n +\frac{1}{(n+1) 2^{n+1}}.$$ Similar with $S=0$, numerical computations suggest that this statement is true. Unfortunately, I didn't see a straightforward way to prove it.

Below is one way to think about the problem, which led to the above reformulation.

The connection between the above problem and $S=0$.

Using the notation developed in the previous answer, let's define $$F(m,n) = \sum_{k=0}^m (-1)^k \binom{m}{k} \binom{2(n+k)}{n+k} \frac{1}{2^{2(n+k)}} \sum_{l=1}^{k+n} \frac{2^l}{l \binom{2l}{l} },$$ and $$f(n)= F(0,n)= \binom{2n}{n} \frac{1}{2^{2n}} \sum_{l=1}^n \frac{2^l}{l \binom{2l}{l} }.$$ The statement $S=0$ is the same as $F(m,m)= 0$. Note that $F$ satisfies $$F(m,n) = \frac{1}{2} F(m-1,n) - \frac{1}{2}F(m-1,n+1) ~~~~~~\text{(r1)}$$ Define the difference operator $D(x_1,x_2) = (x_1 - x_2)/2.$ (r1) in terms of $D$ is $$F(m,n) = D( F(m-1,n), F(m-1,n+1) ).$$ Define $D^k$ by iterating $D$: $$D^n(x_1,x_2,x_3,\ldots,x_{n+1}) = D( D^{n-1}(x_1,x_2,x_3,\ldots,x_{n}), D^{n-1}(x_2,x_3,\ldots,x_{n+1} ))$$ Iterating (r1) gives

$$F(m,n) = D^m( f(n),f(n+1),f(n+2), f(n+3),\cdots,f(n+m)).$$

In particular: $$F(m,m) = D^m( f(m),f(m+1),f(m+2), f(m+3),\cdots,f(m+m)).$$

Define ${\mathcal D}:{\mathbb R}^\infty\rightarrow {\mathbb R}^\infty$ as follows: the $i^{th}$ component of ${\mathcal D}(x_{1}^\infty)$ is $$D^n(x_n,x_{n+1},x_{n+2},\ldots,x_{2n}).$$

We can restate our original problem as follows: show that $(f(1),f(2),f(3),...,f(n),...)$ is in the kernel of ${\mathcal D}$.

Because we are looking for a zero of this operator, the $1/2$ in the definition of $D$ is not important; thus let us assume that $D(x_1,x_2)$ is simply $x_1 -x_2$.

Note that $D^{n}(f(n),f(n+1),...,f(2n)) =0$ is the same as $$D^{n-1}(f(n),f(n+1),f(n+2),...,f(2n-1)) = D^{n-1}(f(n+1),f(n+2),f(n+3),...,f(2n)).$$ A numerical computation reveals that these discrete derivatives equal $\frac{1}{(2n-1)2^{2n-1}}$. One can go back from these values to an element of the kernel of ${\mathcal D}$ by inverting each $D$ in the above display. A bit of computation in this direction yields the vector $\beta$ in the first display. By its construction $\beta$ is in the kernel of ${\mathcal D}$. Thus if one can prove that $f$ equals $\beta$ then we are done.

Finally, using its definition, we see that $f$ satisfies: $$f(n+1) = \frac{2n+1}{2n+2} f(n) + \frac{1}{(n+1)2^{n+1}}, ~~~ f(1) = 1/2.$$ These relations determine $f$ and thus we can take them as $f$'s definition. Thus to verify $f=\beta$ it is enough to show that $\beta$ satisfies this recursion.

-
the second term in the recurrence relation for $\beta$ should read $\frac{1}{(n+1)2^(n+1)$ –  Martin Rubey Jan 29 '10 at 8:27
Now corrected, thanks! –  has2 Jan 29 '10 at 14:45

has2's beta satisfies

$$4(n + 2)\beta_{n + 2} - 2(3n + 4)\beta_{n + 1} + (2n + 1)\beta_n= 0$$

(use any guessing package) which might be easier to use.

-

Well, if algebra doesn't help, let's try good old complex analysis. Put $u=k-j+m$, $s=k+m$ and rewrite the sum as $$\sum_{u\ge 1}2^u\frac{u!(u-1)!}{(2u)!}[x^m]\sum_{s\ge u}2^{-2s}{2s\choose s}x^s(1-\frac 1x)^m$$ where $[x^m]F(x)$ is the $m$-th Laurent coefficient of $F$ at $0$.

Now we can at least recognize the coefficients. The sum in $s$ is just the truncated Taylor sum for $\frac 1{\sqrt{1-x}}$ and $2^u\frac{u!(u-1)!}{(2u)!}=\int_0^1{[2t(1-t)]^u}\frac{dt}{t}$. Recalling that the truncation of analytic functions to high frequences is just $z^uP_+z^{-u}$ where $P_+$ is the Cauchy integral, and that the coefficient at the $m$-th power can be obtained by integration against $z^{-m}$ over a circle, we can write this monster as $$\int_0^1 \frac{dt}{t}\sum_{u\ge 1}[2t(1-t)]^u\oint\oint \frac{z^u z^{-2m}(z-1)^m}{\zeta^u\sqrt{1-\zeta}(1-\frac z\zeta)}dm(z)dm(\zeta)$$ with circular integral taken over the circles of radii less than $1$ with the radius for $z$ smaller than that for $\zeta$ ($m$ is the averaging measure here, so the integrals are just the averages over the corresponding circles). Now, summing over $u$, we get $$\int_0^1 \frac{dt}{t}\oint\oint\left(\frac{1}{1-2t(1-t)\frac z\zeta}-1\right) \frac{z^{-2m}(z-1)^m}{\sqrt{1-\zeta}(1-\frac z\zeta)}dm(z)dm(\zeta)$$ Now $(\frac{1}{1-pw}-1)\frac 1{1-w}=\frac p{1-p}(\frac1{1-w}-\frac1{1-pw})$ Thus, using the Cauchy formula again and integrating over $\zeta$, we convert it into $$\int_0^1 \frac{2(1-t)dt}{1-2t(1-t)}\oint\left(\frac{1}{\sqrt{1-z}}-\frac{1}{\sqrt{1-2t(1-t)z}}\right) {z^{-2m}(z-1)^m}dm(z)$$ The integral in $t$ is an elementary function of $z$ analytic near the origin (have a nice CAS!) The claim that the integral is $0$ for all $m$ is equivalent to the claim that after change of variable $w=\frac z{\sqrt {1-z}}$ all the Taylor coefficients of the new integrand in $w$ with even indices are $0$, i.e., the new integrand is an odd function in $w$ (have more nice CAS!). Whether true or false, it is verifiable now. So, I'll stop here -:).

Edit: It is true. After some moderately tedious computations, it boils down to the fact that $\operatorname{arctan}\sqrt{1-z}-\frac\pi 4$ is an odd function of $w=\frac{z}{\sqrt{1-z}}$, which, believe it or not, is correct. I think you have already checked it using those cute CAS programs, which I haven't on my old laptop, so I'm not posting the details.

Of course, the challenge to find a combinatorial interpretation of this formula still remains.

-

Some observations. Define $$T(N)=\binom{2N}{N}\sum_{j=0}^{N-1}\left[\binom{2(N-j)}{N-j} \cdot (N-j) \cdot 2^{(N+j+1)}\right]^{-1}.$$ Then $$S(m)=\sum_{k=0}^m (-1)^k \binom{m}{k} T(m+k) .$$ Experimentation shows that $T$ satisfies the recursion $$T(n)=T(n-1) - \frac{1}{12}T(n-2),$$ though I don't know how to prove that. For any $F$ satisfying such a recursion $$F(n) = F(n-1) - c \cdot F(n-2)$$ we have $$\sum_{k=0}^m (-1)^k \binom{m}{k} F(m+k) = c^m F(0),$$ which is probably easy to prove; and $T(0)=0$.

-