MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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

share|cite|improve this question
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
up vote 39 down vote accepted

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

accopmaying my article with Moa Apagodu

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


-Doron Zeilbeger

share|cite|improve this answer
Welcome to the neighborhood! – Steven Gubkin May 4 '10 at 14:42
I enthusiastically second that. – gowers May 4 '10 at 20:34

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.

share|cite|improve this answer

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?

share|cite|improve this answer
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

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.

share|cite|improve this answer
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

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$.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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