36
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ To whom it may concern: I have also verified this identity by computer for all natural m up to 200. $\endgroup$
    – aorq
    Jan 24, 2010 at 5:02
  • 29
    $\begingroup$ 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 $\endgroup$ Jan 24, 2010 at 9:40
  • $\begingroup$ @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. $\endgroup$ Jan 29, 2010 at 8:52
  • $\begingroup$ @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. $\endgroup$ Feb 20, 2010 at 15:57
  • $\begingroup$ 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)? $\endgroup$
    – LSpice
    Mar 4, 2010 at 16:18

7 Answers 7

44
$\begingroup$

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

$\endgroup$
2
  • 11
    $\begingroup$ Welcome to the neighborhood! $\endgroup$ May 4, 2010 at 14:42
  • 7
    $\begingroup$ I enthusiastically second that. $\endgroup$
    – gowers
    May 4, 2010 at 20:34
17
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ the second term in the recurrence relation for $\beta$ should read $\frac{1}{(n+1)2^(n+1)$ $\endgroup$ Jan 29, 2010 at 8:27
9
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 24, 2010 at 6:27
  • $\begingroup$ 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. $\endgroup$ Jan 24, 2010 at 9:50
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 24, 2010 at 6:22
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 17, 2010 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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