# 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