How to expand nth power of a polynomial.

Question

Is there any general way to write down the expansion of $n^{th}$ power of a polynomial $\sum_{i=0}^s c_ix^i$, i.e., $(\sum_{i=0}^s c_ix^i)^n$ for some positive integer $n$. I know it for only two terms and by induction i can do the same. But is there any other method or explicit formula known?

Answer 1

One could write down a somewhat-explicit formula via the multinomial theorem; it might look something like $$ \sum_{k_0 + \dots + k_s = n} \frac{n!}{k_0!\,k_1!\dotsb k_s!}c_0^{k_0} c_1^{k_1} \dotsb c_s^{k_s} x^{k_1 + 2k_2 + \dots + s k_s} $$ where the sum is over all nonnegative integers $k_0, k_1, \dots, k_s$ that add up to $n$.

This is only a partial solution because there are too many terms: there are $\binom{n+s}{s}$ ways to choose $k_0, \dots, k_s$, but there are actually only $ns + 1$ different powers of $x$ that occur in the final answer.

Unfortunately, a better formula is out of the question. Even the next simplest case after the binomial theorem, expanding $(1 + x + x^2)^n$, does not have a nice closed form: see sequence A027907 in the OEIS.

Answer 2

As in the two term case with the binomial theorem, the $m$ term to the $n$th power case is the multinomial theorem, with the multinomial coefficient $\binom{n}{k_1! k_2! \cdots k_m!}$.

Answer 3

A standard way (i.e., nothing original here) to generate the coefficients for $f(x) =g^n(x) $ where $g(x) =\sum_{k=0}^{\infty} a_kx^k $ is this:

$f'(x) =ng'(x)g^{n-1}(x) $ so $f'(x)g(x) =ng'(x)g^{n}(x) =ng'(x)f(x) $.

Writing $f(x) =\sum_{k=0}^{\infty} b_kx^k $, $f'(x) =\sum_{k=1}^{\infty} kb_kx^{k-1} =\sum_{k=0}^{\infty} (k+1)b_{k-1}x^{k} $ and $g'(x) =\sum_{k=0}^{\infty} (k+1)a_{k-1}x^{k} $.

Equating coefficients in $f'(x)g(x) =ng'(x)f(x) $, we get a recurrence for the $b_k$.

Note that $n$ does not have to be an integer.

This takes about $k$ operations to generate each $b_k$, so about $k^2$ operations for the first $k$ $b_k$s.

If $g$ is a polynomial, either stop at the non-zero coefficients or set the higher order terms to zero.

For more of this, see generatingfunctionology:

https://www.math.upenn.edu/~wilf/DownldGF.html

This is a free download and an invaluable resource.