Find the coefficients of product

Question

Given the following product, $$(1+ax)(1+a^2x)(1+a^3x)\cdots (1+a^mx) $$ where $a$ is some real number which will be taken to be unity in the end. I want to know the coefficient of general term of expansion $x^p$. I know that the coefficient of $x^p$ comes from choosing $p$ terms from $m$, but the terms will reduce because some kinds of products have the same coefficients. How to write the coefficient step by step? Thanks in advance.

Answer 1

I would try induction over $m$. Define $$ P_m=(1+aX)(1+a^2X)\dots(1+a^m X). $$ Lets denote the coefficients of $P_m$ by $c_p^m$ so that $$ P_m=\sum_{p=0}^m c_p^m X^p. $$ Assume that $m\in \mathbb N$ and that we know the coefficients $c_p^m$. Now what do the coefficients for $P_{m+1}$ look like?

Notice that $P_{m+1}=P_m \cdot (1+a^{m+1}X)$ and thus $$ P_{m+1}=\sum_{p=0}^m c_p^m x^p \cdot (1+a^{m+1}X) = \sum_{p=0}^m c_p^m X^p + c_p^m a^{m+1} X^{p+1}=\left(\sum_{p=0}^m (c_p^m + c_{p-1}^{m}a^{m+1})X^p\right) + c_m^ma^{m+1}X^{m+1} $$ but also by defintion $$ P_{m+1}=\sum_{p=0}^{m+1} c_p^{m+1} X^p. $$ and thus by comparing the coefficients we find $$ c_p^m+c_{p-1}^{m}a^{m+1}=c_p^{m+1}\quad\text{and}\quad c_{m+1}^{m+1}=c_m^ma^{m+1} $$

Answer 2

Products of this type are known to be generalisations of the binomial \begin{align*} (1+x)^m=\sum_{k=0}^m\binom{m}{k}x^k \end{align*} Often such generalisations are written with $q$ instead of $a$ and here I'll follow this convention. We denote with $[x^p]$ the coefficient of $x^p$ in a series and want to find \begin{align*} [x^p]\left(1+qx\right)\left(1+q^2x\right)\cdots\left(1+q^mx\right)=[x^p]\prod_{k=1}^m\left(1+q^kx\right)\tag{1} \end{align*}

According to the q-binomial theorem the following is valid \begin{align*} \color{blue}{\prod_{k=0}^{m-1}\left(1+q^kx\right)=\sum_{k=0}^mq^{\binom{k}{2}}\binom{m}{k}_q x^k}\tag{2} \end{align*} with $\binom{m}{k}_{q}$ the so-called q-binomial coefficients. The q-binomial coefficients follow a recurrence relation similar to the binomial coefficients, namely \begin{align*} \binom{m}{k}_q&=q^k\binom{m-1}{k}_q+\binom{m-1}{k-1}_q\qquad\qquad 1\leq k\leq m\tag{3.1}\\ \binom{m}{0}_q&=\binom{m}{m}_q=1\tag{3.2}\\ \binom{m}{1}_q&=\binom{m}{m-1}_q=1+q+\cdots+q^{k-1}\tag{3.3} \end{align*} We can now transform (1) to use the sum formula in (2) so that we can extract the coefficient of $x^p$.

We obtain from (1) and (2) \begin{align*} \color{blue}{[x^p]}\color{blue}{\prod_{k=1}^m\left(1+q^kx\right)} &=[x^p]\prod_{k=1}^m\left(1+q^{k-1}(qx)\right)\tag{4.1}\\ &=[x^p]\prod_{k=0}^{m-1}\left(1+q^k(qx)\right)\tag{4.2}\\ &=[x^p]\sum_{k=0}^mq^{\binom{k}{2}}\binom{m}{k}_q (qx)^k\tag{4.3}\\ &=[x^p]\sum_{k=0}^mq^{\binom{k+1}{2}}\binom{m}{k}_q x^k\tag{4.4}\\ &\,\,\color{blue}{=q^{\binom{p+1}{2}}\binom{m}{p}_q}\tag{4.5} \end{align*}

Comment:

• In (4.1) we write $q^k=q^{k-1}q$.

• In (4.2) we shift the index to start with $k=0$ and are now able to apply (2).

• In (4.3) we apply (2), replacing $x$ with $qx$.

• In (4.4) we use $\binom{q}{2}+q=\frac{1}{2}q(q-1)+q=\frac{1}{2}q(q+1)=\binom{q+1}{2}$.

• In (4.5) we select the coefficient of $x^p$.

Example $m=5, p=3$: Let's calculate a small example. We obtain with $m=5$ and $p=3$: \begin{align*} \color{blue}{[}&\color{blue}{x^3]\prod_{k=1}^5\left(1+q^kx\right)}=q^{\binom{4}{2}}\binom{5}{2}_q\tag{$\rightarrow 4.1, 4.5$}\\ &=q^6\left(q^2\binom{4}{2}_q+\binom{4}{1}_q\right)\tag{$\rightarrow 3.1$}\\ &=q^6\left(q^2\left(q^2\binom{3}{2}_q+\binom{3}{1}_q\right)+\binom{4}{1}_q\right)\tag{$\rightarrow 3.1$}\\ &=q^6\left(q^4\binom{3}{1}_q+q^2\binom{3}{1}_q+\binom{4}{1}_q\right)\tag{$\rightarrow 3.3$}\\ &=q^6\left(q^4\left(1+q+q^2\right)+q^2\left(1+q+q^2\right)+\left(1+q+q^2+q^3\right)\right)\\ &\,\,\color{blue}{=q^6\left(1+q+2q^2+2q^3+2q^4+q^5+q^6\right)} \end{align*} in accordance with a plausibility check by WolframAlpha.