Help me please to calculate the following sum. I have seen such kind of formulas in the papers related to combinatorics, specifically 'trees'. I am curious how to calculate or approximate this sum: Let $n \in N$, $q\geq 2$ $$ \sum_{m=-n}^n m^q {n \choose (m+n)/2}=\Gamma(n+1)\sum_{m=-n}^nm^q\frac{1}{\Gamma(n/2-m/2+1)\Gamma(n/2+m/2+1)} $$
Evaluating 'combinatorial' sum
-
0This sum involves terms like $n\choose{1/2}$, which needs some defining. – 2012-05-01
-
0$\sum\limits_{m=0}^n (2m-n)^q \binom{n}{m}$ might be a better representation... – 2012-05-01
-
0@Gerry Myerson: sorry, I am not sure what kind of definition I should do here... I ' ve got this formula after few substitutions... Anyway, using Stirling's approximation formula, one can get $\sum_{m=-n}^n \frac{2^{n+1}m^qn^{n+1/2}}{(m+n)^{(m+n+1)/2}(n-m)^{(n-m+1)/2}}$. but, it did not help... – 2012-05-01
-
0@J.M. : I am not sure how it helps... I've never seen such formulas before. could you please provide any book or paper... I would appresiate it. Thank you. – 2012-05-01
-
0I just converted your formula to something slightly more manageable. Check it out, test it yourself. – 2012-05-01
-
0@J.M., you're assuming that in the original formulation there is supposed to be a condition that the sum is over $m$ of the same parity as $n$? – 2012-05-01
-
0@Gerry: I don't know how to make sense of what was given, otherwise... – 2012-05-01
-
2Well, you can define $n \choose (m+n)/2$ using the Gamma function. Note that for nonnegative integers $k$, $\Gamma(k+1/2) = (2k+1)!! \sqrt{\pi}/2^k$ – 2012-05-01
1 Answers
It seems the idea is to consider the sum over $m=-n+2k$ for $0\leqslant k\leqslant n$, which guarantees that every $k=\frac12(m+n)$ is an integer. Thus, the sum with parameter $q$ is $$ \color{red}{s_n(q)=2^n\sum_{k=0}^n\binom{n}{k}2^{-n}(2k-n)^q}. $$ If $q$ is odd, $s_n(q)=0$ thanks to the symmetry $k\to n-k$. From now on, assume that $q$ is even. Note that $$ s_n(q)=2^n\mathrm E((2X_n-n)^q), $$ where $X_n$ is the sum of $n$ i.i.d. Bernoulli random variables with parameter $\frac12$. Define some random variables $G_n$ by the identity $X_n=\frac12n+\frac12\sqrt{n}G_n$, then $$ s_n(q)=2^nn^{q/2}\mathrm E((G_n)^q). $$ The central limit theorem asserts that $G_n$ converges in distribution to a standard normal random variable $G$. For binomial random variables, it happens that the moments of $G_n$ also converge to the moments of $G$, which are well known. Finally, for every even nonnegative integer $q$, $$ \color{red}{\lim\limits_{n\to\infty}2^{-n}n^{-q/2}s_n(q)=\mathrm E(G^q)}, $$ with $\mathrm E(G^q)=0$ if $q$ is odd and $\mathrm E(G^q)=(q-1)!!$ if $q$ is even.
Edit: Likewise, one can consider, for every nonnegative real number $q$, $$ \color{green}{t_n(q)=\sum_{k=0}^n\binom{n}{k}\cdot|2k-n|^q}. $$ The same reasoning yields $$ \color{green}{\lim\limits_{n\to\infty}2^{-n}n^{-q/2}t_n(q)=\mathrm E(|G|^q)=\frac{2^{q/2}}{\sqrt{\pi}}\Gamma\left(\frac{q+1}2\right)}. $$
-
0Thank you very much, Didier, For your answer. I've never seen such kind of methods before. I would like to study it deeply. Could you provide any literature which would give me the similar examples? Thank you very much. – 2012-05-06
-
0A famous example is the constructive [proof of the Stone–Weierstrass approximation theorem](http://en.wikipedia.org/wiki/Bernstein_polynomial#Proof) using Bernstein polynomials and the (weak) law of large numbers. – 2012-05-06
-
0@did: its a very interesting solution. But I do not get how did you do the first 'changeover'? For which $n$, $k$? Thank you. – 2012-06-05
-
0@Michael: Sorry but I have no idea what you are talking about. Could you make your question more precise? – 2012-06-05
-
0@Michael: Additionally, simply for correction you should have mentioned [this](http://math.stackexchange.com/q/141399/6179). – 2012-06-05
-
0@did: Dear did, what would be solution you've posted if we take sum of absolute values $|2k-n|^q$. I understand that we wouldn't have zero for $q$ odd, but I cannot get how whole solution will change. Thank you very much for your explanations. – 2012-07-03
-
0The same asymptotics with $\mathrm E(|G|^q)$ instead of $\mathrm E(G^q)$. – 2012-07-04
-
0Thank you. But how about zero. Am I right that we would not get zero with $q$ odd? – 2012-07-04
-
0Sure, $E(|G|^q)\ne0$, whether $q$ is odd or even. – 2012-07-04
-
0Thank you. But then how solution would differe with $q$ odd. That's what I could not get. Same as with $q$ even? – 2012-07-04
-
0See Edit. $ $ $ $ – 2012-07-04
-
0@did: I've got it now. Thank you very much for your explanations. – 2012-07-11