# How does $(a_0+a_1x+a_2x^2+a_3x^3+\cdots)^k$ become $\sum_{n\geq 0}\big(\sum_{i_1+\cdots+i_k=n\\ i_{ij}\geq 0} a_{i_1}a_{i_2}\cdots a_{i_k}\big)x^n$?

There is this corollary:

Let $h_{n,k}$ be the number of ways to split the interval $[1,\cdots , n]$ $(n\geq 0, k\geq 0)$ into $k$ (possibly empty) subintervals and then building structure $A$ on each of these subintervals.
Note that $A(x)=\sum_{n\geq 0}a_nx^n$ $$H_k(x)=\sum_{n=0}^{\infty} h_{n,k}x^n=(A(x))^k=\underbrace{(a_0+a_1x+a_2x^2+\cdots)\cdots (a_0+a_1x+a_2x^2+\cdots)}_{k\text{ times} } \\=\sum_{n\geq 0}\big(\sum_{i_1+\cdots+i_k=n\\ i_{ij}\geq 0} a_{i_1}a_{i_2}\cdots a_{i_k}\big)x^n$$

How does the following $$(a_0+a_1x+a_2x^2+a_3x^3+\cdots)^k$$ become $$\sum_{n\geq 0}\big(\sum_{i_1+\cdots+i_k=n\\ i_{ij}\geq 0} a_{i_1}a_{i_2}\cdots a_{i_k}\big)x^n$$

• start with $k=2$ and try to notice some pattern, then induction maybe works. – Arian Mar 25 '18 at 14:40

## 1 Answer

Observe we have \begin{align} \left(\sum^\infty_{i=0}a_ix^i \right)^k=&\ \underbrace{\left(\sum^\infty_{i_1=0}a_{i_1}x^{i_1} \right)\cdots \left(\sum^\infty_{i_k=0}a_{i_k}x^{i_k} \right)}_{k-\text{times}}\\ =&\ \sum^\infty_{i_1=0}\cdots \sum^\infty_{i_k=0}\ [a_{i_1}a_{i_2}\ldots a_{i_k}]\ x^{i_1+\ldots +i_k}\\ =&\ \sum^\infty_{n=0}\left(\sum_{i_1+\ldots +i_k=n} a_{i_1}\ldots a_{i_k} \right)x^n \end{align}

• Wow, it's so clear actually. Thanks! – Leyla Alkan Mar 25 '18 at 14:47