Help with a double sum, please - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T21:35:58Z http://mathoverflow.net/feeds/question/12810 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12810/help-with-a-double-sum-please Help with a double sum, please Quadrescence 2010-01-24T03:42:25Z 2010-05-04T14:33:53Z <p>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{.}$$</p> <p>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.</p> <p>Here is another form of the sum (well, I hope at least) that might be easier to work with:</p> <p>$$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{.}$$</p> <p>I have read Concrete Mathematics and $A=B$, and looked at Gosper's and Zeilberger's work for some hints, but no cigar.</p> <p>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)$.</p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/12813#12813 Answer by steve for Help with a double sum, please steve 2010-01-24T04:38:39Z 2010-01-24T04:57:23Z <p>are you sure about S=0 for m>0 ? Check for some values please. So you have,</p> <p>$( (-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]})$</p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/12820#12820 Answer by aorq for Help with a double sum, please aorq 2010-01-24T05:58:57Z 2010-01-24T05:58:57Z <p>Shall we try teamwork? Please feel free to edit this post if you have simplifications.</p> <p>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.</p> <p>Any ideas?</p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/12823#12823 Answer by Scott Morrison for Help with a double sum, please Scott Morrison 2010-01-24T06:08:17Z 2010-01-24T06:08:17Z <p>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.</p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/13321#13321 Answer by has2 for Help with a double sum, please has2 2010-01-29T02:11:58Z 2010-01-29T14:43:56Z <p>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.</p> <p>Below is one way to think about the problem, which led to the above reformulation.</p> <p><strong>The connection between the above problem and $S=0$.</strong></p> <p>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</p> <p>$$F(m,n) = D^m( f(n),f(n+1),f(n+2), f(n+3),\cdots,f(n+m)).$$</p> <p>In particular: $$F(m,m) = D^m( f(m),f(m+1),f(m+2), f(m+3),\cdots,f(m+m)).$$</p> <p>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}).$$</p> <p>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}$.</p> <p>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$.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/13357#13357 Answer by Martin Rubey for Help with a double sum, please Martin Rubey 2010-01-29T08:46:24Z 2010-01-29T08:46:24Z <p>has2's beta satisfies </p> <p>$$4(n + 2)\beta_{n + 2} - 2(3n + 4)\beta_{n + 1} + (2n + 1)\beta_n= 0$$</p> <p>(use any guessing package) which might be easier to use. </p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/13387#13387 Answer by fedja for Help with a double sum, please fedja 2010-01-29T17:51:23Z 2010-01-30T01:47:49Z <p>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 <code>$$\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$$</code> where $[x^m]F(x)$ is the $m$-th Laurent coefficient of $F$ at $0$.</p> <p>Now we can at least recognize the coefficients. The sum in $s$ is just the truncated Taylor sum for <code>$\frac 1{\sqrt{1-x}}$ and $2^u\frac{u!(u-1)!}{(2u)!}=\int_0^1{[2t(1-t)]^u}\frac{dt}{t}$</code>. Recalling that the truncation of analytic functions to high frequences is just <code>$z^uP_+z^{-u}$</code> where <code>$P_+$</code> 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 <code>$$\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)$$</code> 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 <code>$$\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)$$</code> 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 <code>$$\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)$$</code> 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 -:). </p> <p>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.</p> <p>Of course, the challenge to find a combinatorial interpretation of this formula still remains. </p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/13470#13470 Answer by balazs komuves for Help with a double sum, please balazs komuves 2010-01-30T12:20:37Z 2010-01-30T12:20:37Z <p>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$.</p> http://mathoverflow.net/questions/12810/help-with-a-double-sum-please/23434#23434 Answer by Doron Zeilberger for Help with a double sum, please Doron Zeilberger 2010-05-04T14:33:53Z 2010-05-04T14:33:53Z <p>Olivier Gerard just told me about this wonderful website! Regarding the question it can be done in one nano-second using the Maple package </p> <p><a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/MultiZeilberger" rel="nofollow">http://www.math.rutgers.edu/~zeilberg/tokhniot/MultiZeilberger</a></p> <p>accopmaying my article with Moa Apagodu</p> <p><a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html" rel="nofollow">http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html</a></p> <p>Here is the command:</p> <p>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]);</p> <p>and here is the output: -1/4*(2*m+1)/(m+1)+M</p> <p>(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)</p> <p>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)</p> <p>Since S(1)=0 (check!) This is a completely rigorous proof.</p> <p>P.S. The proof can be gotten by finding the so-called multi-certificate</p> <p>lprint(MulZeil(F,[j,k],m,M,{})[2]);</p> <p>-Doron Zeilbeger</p>