Coefficients of polynomial $f_n(q)=\prod_{k=1}^{n}(1+q^k)$

Question

What is the general formula for the coefficient $c_n(k)$ where $$f_n(q)=\prod_{j=1}^{n}(1+q^j)=\sum_{k=0}^{n(n+1)/2}c_n(k)q^k?$$

I came across this problem while researching $q$-analogs. Indeed, the polynomial in question is trivially given by $$f_n(q)=(-q;q)_n$$ where $(a;q)_n=\prod_{k=0}^{n-1}(1-aq^k)$ is the $q$-Pochhammer symbol. From Wikipedia, I read that $$f_n(q)=\sum_{j=0}^{n}\left[{{n}\atop{j}}\right]_{q^2}q^j\tag{1}$$ where $$\left[{{n}\atop{j}}\right]_{q}=\frac{(q;q)_n}{(q;q)_j(q;q)_{n-j}}.$$ While $(1)$ is a cool identity nonetheless, it does not provide me with what I'm looking for, as $\left[{{n}\atop{j}}\right]_{q^2}$ is still dependent on $q$.

I worked out the first few polynomials by hand: $$\begin{align} f_1(q)&=1+q\\ f_2(q)&=1+q+q^2+q^3\\ f_3(q)&=1+q+q^2+2q^3+q^4+q^5+q^6\\ f_4(q)&=1+q+q^2+2q^3+2q^4+2q^5+2q^6+2q^7+q^8+q^9+q^{10}\\ f_5(q)&=1+q+q^2+2q^3+2q^4+3q^5+3q^6+3q^7+3q^8+3q^9+3q^{10}+2q^{11}+2q^{12}\\ &+q^{13}+q^{14}+q^{15}. \end{align}$$

It seems as if, in general, $$c_n(k)=c_n(n(n+1)/2-k).$$

I started trying to find recurrence relations. I saw that $$c_3(k)=\begin{cases} c_2(k) & 0\le k\le 2 \\ c_2(k)+c_2(k-3) & k=3 \\ c_2(k-3) & 4\le k \le 6 \end{cases}$$ and similarly $$c_4(k)=\begin{cases} c_3(k) & 0\le k\le 3 \\ c_3(k)+c_3(k-4) & 4\le k\le 6 \\ c_3(k-4) & 7\le k\le 10 \end{cases}$$ as well as $$c_5(k)=\begin{cases} c_4(k) & 0\le k\le 4 \\ c_4(k)+c_4(k-5) & 5\le k\le 10 \\ c_4(k-5) & 11\le k\le 15 \end{cases}$$ which hints at the general expression $$c_n(k)=\begin{cases} c_{n-1}(k) & 0\le k\le n-1 \\ c_{n-1}(k)+c_{n-1}(k-n) & n\le k\le n(n-1)/2 \\ c_{n-1}(k-n) & 1+n(n-1)/2\le k\le n(n+1)/2 \end{cases} .\tag{2}$$

This looks promising, but I am not sure if it is correct, because I just found it from basically guessing/recognizing a pattern which is not the most rigorous approach. Could someone verify $(2)$ and/or provide a simpler form of it? I ask this because I want to eventually find the coefficients $C(k)$ in $$(-q;q)_\infty=\sum_{k\ge0}C(k)q^k$$ by taking $\lim_{n\to\infty}c_n(k)$.

---

Edit:

It may or may not help to note that, since $f_n(1)=\prod_{k=1}^{n}2=2^n$, we have the interesting identity $$\sum_{k=0}^{n}c_n(k)=2^n.$$

Answer 1

Too long for a comments.

Openning the brackets, you get $q^k$ exactly when you can write $$k=i_1+i_2+....+i_j$$ for $1\leq i_1< i_2< .... < u_j \leq n$

Therefore $c_n(k)=$ is the number of ways $k$ can be written as a sum of distinct integers in $\{1,2,3,.., n\}$.

Alternately, if for each $ A \subset \{ 1,2,3,..,n \}$ you define $f(A)=\sum_{k \in A} k$, then $c_n(k)$ is simply the number of subset $A \subset \{ 1,2,3,..,n \}$ for each $f(A)=k$.

Now, the relation $$c_n(k)=c_n(n(n+1)/2-k) \,.$$ becomes obvious: If $f(A)=k$ then $f(\{ 1,2,..., n\} \backslash A)= n(n+1)/2-k$. In other words, the complement is a bijection between the number of subset $A \subset \{ 1,2,3,..,n \}$ such that $f(A)=k$ and the number of subset $A \subset \{ 1,2,3,..,n \}$ such that $f(A)=n(n+1)/2-k$.

You can also see $$\sum_{k=0}^{n}c_n(k)=2^n.$$ as a consequence that there are exatly $2^n$ subsets on $\{1,2,..,n\}$.

Answer 2

Okay, I've found a legit proof for $(2)$.

We see that $$\begin{align} f_n(q)&=(1+q^n)\sum_{k=0}^{n(n-1)/2}c_{n-1}(k)q^k\\ &=\sum_{k=0}^{n(n-1)/2}c_{n-1}(k)q^k+\sum_{k=0}^{n(n-1)/2}c_{n-1}(k)q^{k+n}\\ &=\sum_{k=0}^{n(n-1)/2}c_{n-1}(k)q^k+\sum_{k=n}^{n(n+1)/2}c_{n-1}(k-n)q^{k}\\ &=\sum_{k=0}^{n-1}c_{n-1}(k)q^k+\sum_{k=n}^{n(n-1)/2}(c_{n-1}(k)+c_{n-1}(k-n))q^k+\sum_{k=1+n(n-1)/2}^{n(n+1)/2}c_{n-1}(k-n)q^{k}\\ \sum_{k=0}^{n(n+1)/2}c_n(k)q^k&=\sum_{k=0}^{n-1}c_{n-1}(k)q^k+\sum_{k=n}^{n(n-1)/2}(c_{n-1}(k)+c_{n-1}(k-n))q^k+\sum_{k=1+n(n-1)/2}^{n(n+1)/2}c_{n-1}(k-n)q^{k}. \end{align}$$ Thus $$c_n(k)=\begin{cases} c_{n-1}(k) & 0\le k\le n-1 \\ c_{n-1}(k)+c_{n-1}(k-n) & n\le k\le n(n-1)/2 \\ c_{n-1}(k-n) & 1+n(n-1)/2\le k\le n(n+1)/2 \end{cases}$$ with the base case $c_1(0)=c_1(1)=1$.

In a nearly identical fashion, one can show that the coefficients $a_n(k)$ in $$\prod_{j=1}^{n}(1-q^j)=\sum_{k=0}^{n(n+1)/2}a_n(k)q^k$$ satisfy $$a_n(k)=\begin{cases} a_{n-1}(k) & 0\le k\le n-1 \\ a_{n-1}(k)-a_{n-1}(k-n) & n\le k\le n(n-1)/2 \\ -a_{n-1}(k-n) & 1+n(n-1)/2\le k\le n(n+1)/2 \end{cases}$$ with the base cases $a_1(0)=1$, $a_1(1)=-1$.

Answer 3

Another method. Let $S\subseteq\Bbb N$ and $A=(a_n)_{n\in S}$ be a sequence. Then define $$\Pi(q)=\Pi_{S,A}(q)=\prod_{n\in S}(1-a_nq^n), \qquad |q|<1.$$ Then define $c_n=c_{S,A}(n)$ as the coefficients $$\Pi(q)=\sum_{n\ge0}c_nq^n,\qquad c_0=1.\tag1$$ Then let $r_n=a_n\chi_S(n)$. Thus we have $$\Pi(q)=\prod_{n\ge1}(1-r_nq^n).$$ Then $$\begin{align} \ln\Pi(q)&=\sum_{n\ge1}\ln(1-r_nq^n)\\ &=-\sum_{n\ge1}\sum_{k\ge1}\frac{r_n^kq^{nk}}{k}. \end{align}$$ Taking the derivative and multiplying by $q$, we have $$\begin{align} \frac{q\Pi'(q)}{\Pi(q)}&=-\sum_{n\ge1}\sum_{k\ge1}nr_n^kq^{nk}\\ &=-\sum_{N\ge1}q^N\sum_{uv=N\\ u,v\ge1}ur_u^v\\ &=-\sum_{n\ge1}q^n\sum_{d|n}dr_d^{n/d}\\ \Rightarrow q\Pi'(q)&=\Pi(q)\sum_{n\ge1}R_nq^n.\tag2 \end{align}$$ We can then use $(1)$ and $(2)$ to multiply power series and compare coefficients to get the recurrence $$nc_{S,A}(n)=-\sum_{k=1}^{n}c_{S,A}(n-k)\sum_{d|k}\left(\chi_S(d)a_d\right)^{k/d}d.$$ Setting $S=\{1,...,m\}$ and $A=(1)_{n\in S}$, the coefficient $c_{S,A}(n)=\alpha_m(n)$ of $q^n$ in the expansion of $\prod_{i=1}^{m}(1+q^i)$ satisfies the recurrence $$n\alpha_m(n)=-\sum_{k=1}^{n}\alpha_m(n-k)\sum_{\,\, d|k\\ \, d\le N}d.$$