2

Suppose you have $(a_0+a_1x+a_2x^2+...+a_nx^n)^k$, and you want to expand and find a formula for the coefficients $\beta_j$ such that $\beta_j$ is the coefficient of the $x^j$ term.

I understand that when the all coefficients $a_1, ..., a_n$ are equal to 1, you would get: $$\beta_j = \sum_{i=0}^{\lfloor\frac{j-n}{k}\rfloor}(-1)^i\binom{n}{i}\binom{j-ik-1}{n-1}$$

but how would you generalize this $\forall a_1, ..., a_n \in \mathbb{R}$?

RobPratt
  • 45,619
mbohde2015
  • 23

3 Answers3

3

As indicated by @GerryMyerson we can use the multinomial theorem to extract $[x^j]$, the coefficient of $x^j$ of the multinomial.

We obtain \begin{align*} [x^j]&\left(a_0+a_1x+\cdots+a_nx^n\right)^k\\ &=[x^j]\sum_{{t_0+t_1+\cdots+t_n=k}\atop{t_0,t_1,\ldots,t_n\geq 0}} \binom{k}{t_0,t_1,\ldots,t_n}a_0^{t_0}a_1^{t_1}\cdots a_n^{t_n}x^{t_1+2t_2+\cdots+nt_n}\\ &\color{blue}{=\sum_{{{t_0+t_1+\cdots+t_n=k}\atop{t_1+2t_2+\cdots+nt_n=j}}\atop{t_0,t_1,\ldots,t_n\geq 0}} \binom{k}{t_0,t_1,\ldots,t_n}a_0^{t_0}a_1^{t_1}\cdots a_n^{t_n}} \end{align*}

Markus Scheuer
  • 108,315
2

The coefficient $\beta_j$ of $x^j$ in $(a_0 + a_1 x + \ldots + a_nx^n)^k$ will be

$$\beta_j = \sum_{r_1 + r_2 + \ldots + r_k = j} a_{r_1} a_{r_2} \cdots a_{r_k}$$

So, for instance, if we look at the $x^4$ coefficient in $(a_0 + a_1 x + a_2 x^2)^3$, we sum over all the (ordered!) ways to write $4$ as a sum of exactly $3$ of our existing indices.

  • $4 = 2 + 2 + 0$
  • $4 = 2 + 0 + 2$
  • $4 = 0 + 2 + 2$
  • $4 = 1 + 1 + 2$
  • $4 = 1 + 2 + 1$
  • $4 = 2 + 1 + 1$

so we see

$$ \begin{align} \beta_4 &= a_2 a_2 a_0 + a_2 a_0 a_2 + a_0 a_2 a_2 + a_1 a_1 a_2 + a_1 a_2 a_1 + a_2 a_1 a_1 \\ &= 3 a_0 a_2^2 + 3 a_1^2 a_2 \end{align} $$

Of course, we can check this in a computer algebra system like sage.

the same computation as above, but done in sage

To see why this is the case, you might be interested in cauchy products. Particularly since you tagged this question as "generating-functions". You can also find this information in chapter 2 of Wilf's excellent generatingfunctionology.

I hope this helps ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
  • Suggestion: The general process for multiplying two polynomials whose coefficients are given as strings of numbers is called convolution of the two strings. You can use that term as a starting point as you search for additional info. – MathFont Sep 21 '22 at 14:10
0

Wilf, in 1.5.3 of generatingfunctionology shows how binomial coefficients are related to a polynomial generating function.

My observations have been that we can do this for a polynomial like $p(x) = 1 + \sum_{i=0}^{k}c_ix^{e_i}$ where $e_i$ are positive integers and $e_0$ is the smallest. The coefficient of $x^r$ is generated by the polynomial that interpolates through the coefficients of $x_r$ in $p(x)^n$ for $n \in [0, \lfloor r/e_0 \rfloor]$.

Consider $f(x) = 2 + x^2 - 3x^3 + 7x^7$. If we are interested in the coefficient of $x^{24}$ for a given power (potentially quite large) then we

  • divide $f(x)$ by 2 to give $p(x) = f(x)/2 = 1 + x^2/2 - 3x^3/2+7x^7/2$
  • calculate the coefficient of $x^{24}$ in the powers of $p(x)$ from $0$ through $12$, e.g. $(n,a_r(n)) = (0,0), (1,0), (2,0), (3,0), (4,-1029/4), ..., (12, -216565271/4096)$
  • make an interpolating polynomial through those points, $$a_{24}(n) = 2^{n}n(n - 3)(n - 2)(n - 1)(n^8 + 11820n^7 + 8400714n^6 + 292451040n^5 - 22255776231n^4 + 157239720900n^3 + 2236325308316n^2 - 22218190890960n + 27361536048000)/1961990553600$$ where the $2$ in $2^n$ is the constant term in $f(x)$;
  • use that, for example, to calculate $a_{24}$ in $f(x)^{55}$ as $33951898828482980534298869760$ (which was verified with SymPy).

An advantage to using the generating function is that there is no need to partition the exponent to generate the multinomial coefficients needed to calculate the coefficient of interest in the exponentiated polynomial.

smichr
  • 359