Evaluating 'combinatorial' sum 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)}
$$
 A: 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)}.
$$
