# Expansion of $\bigl(\sum x_i\bigr)^4$

Show that $$(\sum_{i=1}^n X_i)^4=\sum_{i=1}^n X_i^4+4\sum_{i\neq j}^n X_i^3X_j+3\sum_{i\neq j}^n X_i^2X_j^2+6\sum_{i\neq j\neq k}^n X_i^2X_jX_k+\sum_{i\neq j\neq k\neq l}^n X_iX_jX_kX_l$$ Please show it step by step.Thanks in advance.

-
Have you tried induction on $n$ ? –  pritam Sep 6 '12 at 6:18
Do you see what $(\sum X_i)^2$ is? –  Karolis Juodelė Sep 6 '12 at 6:19
I don't know if its just me, but: yould you please try to formulate "Show it step by step,Please." as a question? –  vanguard2k Sep 6 '12 at 6:21
What is is $X_i$, $X_j$, etc.? –  Emmad Kareem Sep 6 '12 at 6:25

More directly, if you prefer:

\begin{align} \left(\sum_i X_i\right)^4&=\left(\sum_i X_i\right)\left(\sum_j X_j\right)\left(\sum_k X_k\right)\left(\sum_\ell X_\ell\right)\\ &=\sum_i\sum_j\sum_k\sum_\ell X_iX_jX_kX_\ell\\ &=\sum_{i,j,k,\ell} X_iX_jX_kX_\ell\\ \end{align}

Now just break apart the 4-tuples according to multiplicities.

\begin{align} &=\sum_{i=j=k=\ell} X_iX_jX_kX_\ell\\ &+\left(\sum_{i=j=k\neq\ell} X_iX_jX_kX_\ell+\sum_{i=j=\ell\neq k} X_iX_jX_kX_\ell+\sum_{i=\ell=k\neq j} X_iX_jX_kX_\ell+\sum_{\ell=j=k\neq i} X_iX_jX_kX_\ell\right)\\ &+\left(\sum_{i=j\neq k=\ell} X_iX_jX_kX_\ell+\sum_{i=k\neq j=\ell} X_iX_jX_kX_\ell+\sum_{i=\ell\neq k=j}X_iX_jX_kX_\ell\right)\\ &+\left(\text{six such things with two equal indices and a third and fourth distinct index}\right)\\ &+\sum_{i, j, k, \ell \text{ distinct}} X_iX_jX_kX_\ell\end{align}

-
Just a minor point: when you write $i\neq j\neq k\neq l$ you mean that $i,j,k,l$ should all be distinct. But the "unequal" relation is not transitive, so that's not quite what it says... –  Marc van Leeuwen Sep 6 '12 at 8:20
@Marc Oops! I was getting lazy after all of the previous sums. I'll edit it. –  alex.jordan Sep 6 '12 at 16:54
@Marc And your comment applies to the OP's stated question as well, in two places. –  alex.jordan Sep 6 '12 at 17:01

When you raise a sum to the fourth power, you are trying to multiply that sum by itself four times (or is it three times?). Each term from the first copy will be multiplied by each term from the second copy, which in turn will be multiplied by each term from the third copy, and lastly by each term from the fourth.

So in the expanded and uncondensed product, every term will consist of a degree-four monomial. I suppose you might write $X_iX_jX_kX_\ell$. But what if all four indices are the same? You'd have $X_i^4$. And for any particular $i$ only one of the degree-four monomials will be that $X_i^4$. So $\sum\limits_iX_i^4$ accounts for some of the degree-four monomials in the expanded product.

Now what if $i=k$ and $j=\ell$, but $k\neq j$? Then there would be a monomial $X_i^2X_j^2$. This time, for any particular pair $i$ and $j$, there are actually six ways to obtain a monomial $X_i^2X_j^2$. Count all of the ways that the index $i$ could have arisen twice from the four original sums: $$X_iX_iX_jX_j,\quad X_iX_jX_iX_j,\quad X_iX_jX_jX_i,\quad X_jX_jX_iX_i,\quad X_jX_iX_jX_i,\quad\text{ and }\quad X_jX_jX_iX_i.$$ However, if you plan to sum over $i\neq j$, then each $X_i^2X_j^2$ arises twice. So the expanded product of four sums has 3 copies of $X_i^2X_j^2$, and then again 3 more copies when $i$ and $j$ trade places. So $3\sum\limits_{i\neq j}X_i^2X_j^2$ accounts for more of the degree-four monomials in the expanded product.

Continue these considerations, with $i=k=\ell\neq j$, $i=\ell\neq j\neq k\neq i$, and lastly with all four indices different.

-

From Multinomial theorem:

For any positive integer $m$ and any nonnegative integer $n$, the multinomial formula tells us how a sum with $m$ terms expands when raised to an arbitrary power $n$: $$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} \prod_{1\le t\le m}x_{t}^{k_{t}}\,,$$ where $${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$$ is a multinomial coefficient.

In your case $n=4$, then the multinomial coefficients are

• ${4 \choose 4,0,0,0}=1$,
• ${4 \choose 3,1,0,0}=4$,
• ${4 \choose 2,2,0,0}=6$,
• ${4 \choose 2,1,1,0}=12$ and
• ${4 \choose 1,1,1,1}=24$.

This differs from your values because we count differently. To get your coefficients, divide by the faculty of the number of degenerate occurrences, e.g. two "$2$"'s in ${4 \choose 2,2,0,0}=6$, to get $\frac6{2!}=3$ or four "$1$"'s in ${4 \choose 1,1,1,1}=24$, to get $\frac{24}{4!}=1$.

-