Consider $(a_1+a_2+ \cdots + a_n)^r$. We know that it has $n^r$ elements. I want to calculate the number of elements, where all $a_i$ coefficiants have even powers, i.e. $(a_1+a_2+ \cdots + a_n)^r = \sum_{k_1+k_2+ \cdots + k_n = r} \frac{r!}{k_1! k_2! \cdots k_n!}a_1^{k_1} \cdots a_n^{k_n},$ to calculate the following sum $\sum_{k_1+k_2+ \cdots + k_n = r, \forall k_i even} \frac{r!}{k_1! k_2! \cdots k_n!}.$ How can I calculate this sum?
3
-
$\begingroup$ Hmm, I thought the question as it was originally, was interesting. Note that now with the edit the answer will always be $0$ if $r$ is odd since $\sum_i k_i = r$ and therefore at least 1 of $k_i$ must itself be odd. $\endgroup$– DanCommented Feb 26, 2015 at 16:50
-
$\begingroup$ yes, I am interested in the case when $r$ is even, otherwise it's obviuosly $0$. $\endgroup$– MerylCommented Feb 26, 2015 at 16:52
-
$\begingroup$ An alternative way of phrasing what you're after is the elements of $(a_1^2 + \ldots + a_n^2)^{r/2}$. $\endgroup$– Peter TaylorCommented Feb 26, 2015 at 17:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider i.i.d. random variables $X_1, \ldots, X_n$ with $\operatorname{Pr}(X_i = -1) = \operatorname{Pr}(X_i = 1) = 1/2$ for all $i$. It is easy to see that $$\operatorname{E}[(X_1+\ldots+X_n)^r] = \operatorname{E}\left[\sum_{k_1+\ldots+k_n=r}{\frac{r!}{k_1!\ldots k_n!}X_1^{k_1}\ldots X_n^{k_n}}\right] = \sum_{k_1+\ldots+k_n=r,\ k_i {\text{ is even }} \forall i}{\frac{r!}{k_1!\ldots k_n!}}.$$ On the other hand, for all $0\leq k\leq n$, we have $$\operatorname{Pr}(X_1 + \ldots + X_n = -n+2k) = \frac{1}{2^n}{n\choose k}.$$ Therefore $$\operatorname{E}[(X_1+\ldots+X_n)^r] = \frac{1}{2^n}\sum_{k=0}^n {n\choose k}(-n+2k)^r.$$ Assume we are interested in the case when $r$ is relative small comparing to $n$, we can further deduce that the above is equal to $$\frac{1}{2^n}\sum_{k=0}^n {n\choose k}\sum_{i=0}^r{r\choose i}(-n)^{r-i}(2k)^i.$$ Now we have $$\sum_{k_1+\ldots+k_n=r,\ k_i {\text{ is even }} \forall i}{\frac{r!}{k_1!\ldots k_n!}} = \sum_{i=0}^r {r\choose i}(-n)^{r-i}\sum_{k=0}^n \frac{1}{2^n}{n\choose k}(2k)^i.$$ Note that for $i$ fixed, we have $$\sum_{k=0}^n\frac{1}{2^n}{n\choose k}k^i = \sum_{k=0}^n\frac{1}{2^n}{n\choose k}\sum_{j=0}^i S(i,j)(k)_j = \sum_{j=0}^iS(i,j)\sum_{k=0}^n\frac{1}{2^n}{n\choose k}(k)_j = \sum_{j=0}^iS(i,j)2^{-j}(n)_j,$$ where $S(i,j)$ is the Stirling number of the second kind and $(k)_j = k(k-1)\ldots(k-j+1)$. Plug in the above, we obtain $$\sum_{k_1+\ldots+k_n=r,\ k_i {\text{ is even }} \forall i}{\frac{r!}{k_1!\ldots k_n!}} = \sum_{i=0}^r {r\choose i}(-n)^{r-i}\sum_{j=0}^iS(i,j)2^{i-j}(n)_j.$$
