# How to find the coefficient of $x^k$ in the expression $\prod_{p=1}^n (x^p+1)^p$?

I tried to find the indefinite integral $$f_n(x)=\int \prod_{k=1}^n \cos^k(kx) \, dx$$ by using Euler's formula and put $$x=\frac{\ln y}{2i}$$ I got $$f_n(x)=-i2^{-\frac{n(n+1)}{2}-1}\int y^{-\frac{n(n+1)(2n+1)}{12}-1} \prod_{k=1}^n (y^k+1)^k \, dy$$ now lets define $$a(n,k)$$ as the coefficient of $$x^k$$ in the expression $$\prod_{p=1}^n (x^p+1)^p$$ then $$\prod_{k=1}^n (y^k+1)^k =\sum_{k=0}^{\frac{n(n+1)(2n+1)}{6}} a(n,k) y^k$$

So $$f_n(x)=2^{-\frac{n(n+1)}{2}-1} \sum_{k=0}^{\frac{n(n+1)(2n+1)}{6}} \frac{a(n,k)}{k-\frac{n(n+1)(2n+1)}{12}} (-i) \exp\left(2x\left(k-\frac{n(n+1)(2n+1)}{12} \right) i\right) + c$$ and where $$f_n(x)$$ is real So we will take the real part of the result and get $$f_n(x)=2^{-\frac{n(n+1)}{2}-1} \sum_{k=0}^{\frac{n(n+1)(2n+1)}{6}} \frac{a(n,k)}{k-\frac{n(n+1)(2n+1)}{12}}\sin\left(2x\left(k-\frac{n(n+1)(2n+1)}{12}\right)\right)+c$$ and if $$k=\frac{n(n+1)(2n+1)}{12}$$ then take limit to get $$\frac{\sin(2ax)}{a}=2x , a\to0$$

finally if we know $$a(n,k)=a\left(n,\frac{n(n+1)(2n+1)}{6}-k \right)$$ then $$f_n(x)=2^{-\frac{n(n+1)}{2}} a\left(n,\frac{N}{2}\right) x+2^{-\frac{n(n+1)}{2}-1} \sum_{k=1}^{\frac{N}{2}} \frac{a\left(n,\frac{N}{2}-k\right)}{k} \sin\left(2kx\right)+c,\text{ if } N \text{ is even}$$ and $$f_n(x)=2^{-\frac{n(n+1)}{2}+1}a\left(n,\frac{N-1}{2}\right) \sin(x) + 2^{-\frac{n(n+1)}{2}} \sum_{k=1}^{\frac{N-1}{2}} \frac{a\left(n,\frac{N-1}{2}-k\right)}{2k+1} \sin\left((2k+1)x\right)+c,\text{ if } N \text{ is odd}$$ where $$N=\frac{n(n+1)(2n+1)}{6}$$

now my QUESTIONS

How to calculate $$a(n,k)$$ or even what is the recurrence relation?

also How to prove that $$a(n,k)=a\left(n,\frac{n(n+1)(2n+1)}{6}-k \right)$$?

and when we took the real part if we took the imaginary part it will be zero So How to prove $$\sum_{k=0}^{\frac{n(n+1)(2n+1)}{6}} \frac{a(n,k)}{k-\frac{n(n+1)(2n+1)}{12}} \cos\left(2x\left(k-\frac{n(n+1)(2n+1)}{12} \right) \right)=c$$ this question asked also on MSE

• Just to confirm, are you interested in how to compute it for specific values of n,k, or looking for a general formula? You can obviously use Fast Fourier Transform to extract the coefficients for fixed $n,k$. Commented Feb 13 at 18:43
• @AspiringMat how we can get it ? show me please maybe it will help me to understand how to find a recurrence relation Commented Feb 13 at 19:44
• For $n\to\infty$, the coefficients $a(\infty,k)=(1,1,2,5,8,16,28,49,83,142,\ldots)$ are given by oeis.org/A026007, see more details there. The terms of $a(n,k)$ for $k\leq n$ are the same as in $a(\infty,k).$ Commented Feb 13 at 21:04
• @GerryMyerson of course the second one..its just a typo I will fix it sorry for that Commented Feb 14 at 5:32
• Direct calculation shows that the function $f(x) := \prod_{p=1}^n (x^p+1)^p$ obeys the functional equation $f(1/x) = x^{-\sum_{p=1}^n p^2} f(x)$, which explains the coefficient symmetry $a(n,k) = a(n,\frac{n(n+1)(2n+1)}{6}-x)$. Commented Feb 18 at 19:57

I got it ...

firstly the degree of $$(x^p+1)^p$$ is $$p^2$$ So the degree of $$\prod_{p=1}^n (x^p+1)^p$$ is $$N=1+2^2+3^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$ now we have $$\prod_{p=1}^n (x^p+1)^p=\sum_{p=1}^N a(n,p)x^p$$ by taking kth derivative and put $$x\to0$$ we get $$\lim_{x\to0} \frac{d^k}{dx^k} \prod_{p=1}^n (x^p+1)^p=\lim_{x\to0} \frac{d^k}{dx^k}\sum_{p=1}^N a(n,p)x^p$$ But for natural $$k,p$$ $$\lim_{x\to0} \frac{d^k}{dx^k} x^p=0 ,p\ne k$$ So $$\lim_{x\to0} \frac{d^k}{dx^k} a(n,k)x^k=\lim_{x\to0} \frac{d^k}{dx^k} \prod_{p=1}^n (x^p+1)^p$$ then $$a(n,k)=\frac{1}{k!}\lim_{x\to0} \frac{d^k}{dx^k} \prod_{p=1}^n (x^p+1)^p$$ now to find the kth derivative we need to use General Leibniz rule and get $$\frac{1}{k!}\lim_{x\to0} \frac{d^k}{dx^k} \prod_{p=1}^n (x^p+1)^p=\frac{1}{k!}\sum_{k_1+k_2+...+k_n=k} \binom{k}{k_1,k_2,...,k_n} \prod_{j=1}^n \lim_{x\to0} \frac{d^{k_j}}{dx^{k_j}} (x^j+1)^j$$ where $$\lim_{x\to0} \frac{d^{k_j}}{dx^{k_j}} (x^j+1)^j=\sum_{p=0}^j \binom{j}{p} \lim_{x\to0} \frac{d^{k_j}}{dx^{k_j}} x^{pj}$$ So it must be $$k_j=pj$$ which mean $$\frac{k_j}{j}\in N$$ or its value is zero then $$\lim_{x\to0} \frac{d^{k_j}}{dx^{k_j}} (x^j+1)^j=\binom{j}{\frac{k_j}{j}} k_j!f\left(\frac{k_j}{j}\right) , 0 \leq\frac{k_j}{j}\leq j$$ where $$f(x)=1$$ if $$x\in N$$ and $$f(x)=0$$ if $$x \notin N$$

back to the formula we have $$a(n,k)=\frac{1}{k!}\sum_{k_1+k_2+...+k_n=k} \binom{k}{k_1,k_2,...,k_n} \prod_{j=1}^n \lim_{x\to0} \frac{d^{k_j}}{dx^{k_j}} (x^j+1)^j$$ $$=\sum_{k_1+k_2+...+k_n=k} \frac{1}{k_1!k_2!...k_n!} \prod_{j=1}^n \binom{j}{\frac{k_j}{j}} k_j!f\left(\frac{k_j}{j}\right)$$ So $$a(n,k)=\sum_{k_1+k_2+...+k_n=k}\prod_{j=1}^n \binom{j}{\frac{k_j}{j}} f\left(\frac{k_j}{j}\right)$$ now put $$g_j=\frac{k_j}{j}$$ So $$a(n,k)=\sum_{g_1+2g_2+...+ng_n=k}\prod_{j=1}^n \binom{j}{g_j} f\left(g_j\right)$$ where $$g_1+2g_2+...+ng_n=k$$ with $$0\leq g_j \leq j$$ which mean $$g_j\in\{0,1,2,...,j\}$$ So $$f(g_j)=1$$

finally I got $$a(n,k)=\sum_{\substack{\sum_{j=1}^n j g_j=k \\ g_j\in\{0,1,..,j\}}}\prod_{j=1}^n \binom{j}{g_j}$$

and because of $$g_j\in\{0,1,..,j\}$$ then we can put $$g_j\to j-g_j$$ then $$\sum_{j=1}^n j (j-g_j)=k \to \sum_{j=1}^n j g_j=N-k$$ which mean $$a(n,k)=a(n,N-k)$$

and for the last question to prove the given series is constant function for $$x$$ lets define $$f(x)$$ and rewrite $$\cos x$$ as real part of $$e^{ix}$$ So $$f(x)=\Re\left(\sum_{\substack{k=0 \\ k\ne \frac{N}{2}}}^N \frac{a(n,k)}{k-\frac{N}{2}} \exp\left(2ix\left(k-\frac{N}{2} \right) \right) \right)$$ note that the case $$k=\frac{N}{2}$$ is real valued by using limit : $$\frac{\sin(ax)}{a} , a\to 0$$ , then by derivative $$f'(x)=\Re\left(2i\sum_{\substack{k=0 \\ k\ne \frac{N}{2}}}^N a(n,k) \exp\left(2ix\left(k-\frac{N}{2} \right) \right) \right)$$ $$=-2\Im\left(e^{-iNx}\sum_{k=0}^N a(n,k) e^{2ikx}-a\left(n,\frac{N}{2}\right) \right)=-2\Im\left(e^{-iNx}\prod_{k=1}^n \left(e^{2ikx}+1\right)^k\right)$$ $$=-2\Im\left(\prod_{k=1}^n e^{-ik^2x} \left(e^{2ikx}+1\right)^k\right)=-\Im\left(\prod_{k=1}^n \left(2 \cos (kx)\right)^k \right)=0$$ therefore $$f'(x)=0$$ which mean $$f(x)$$ is constant for $$x$$

• Nice work Fao (+1) Commented Feb 18 at 14:24
• @AliShadhar thanks Commented Feb 18 at 16:35

Caveat: OP asked me in the comment section how he can calculate the coefficient explicitly. This answer is mainly algorithmic (dynamic programming) and straight forward with FFT/convolutions/dynamic programming for polynomial multiplications.

One way to calculate it:

Let $$a(n, k)$$ be the $$k$$th coefficient of $$\prod_{p=1}^n (1+x^p)^p$$. First, we expand $$(1+x^n)^n$$ by the binomial theorem to get

$$(1+x^n)^n = \sum_{i=0}^n {n \choose i}x^{i\cdot n}$$

Hence,

$$a(n, k) = [x^k]\left( \prod_{p=1}^n (1+x^p)^p \right) = \sum_{i=0}^n {n \choose i} [x^{k-i\cdot n}]\left( \prod_{p=1}^{n-1} (1+x^p)^p \right) = \sum_{i=0}^n {n \choose i}a(n-1, k-i\cdot n)$$

The base case is $$a(n, k)=0$$ for $$k<0$$ and $$a(1, k)=1$$ if $$k=0$$ or $$k=1$$ and $$0$$ otherwise.

You can precompute $${r \choose i}$$ in $$O(n^2)$$ time for all $$r,i = 0, ..., n$$, and then evaluate the recurrence for fixed $$n,k$$ in $$O(n^2)$$ time. I'm sure you can use divide and conquer or FFT to speed this up too, but this should be enough for reasonable $$n$$.

Python code

Here is the Python code for the above recurrence, whose values seem to agree with @Fred Hucht's answer for $$n\to \infty$$. Caveat: I am not a programmer, so code below is in no way optimized. Feel free to edit and optimize.

from functools import lru_cache
import sys
sys.setrecursionlimit(50000)

@lru_cache(maxsize=None)
def C(n, k):
if k==1 and n>=1:
return n
if n<k:
return 0
if k==0:
return 1
return C(n-1, k) + C(n-1, k-1)

@lru_cache(maxsize=None)
def a(n, k):
if k<0:
return 0
if n==1:
if k==0 or k==1:
return 1
else:
return 0

ans = 0
for i in range(n+1):
ans += C(n, i) * a(n-1, k-i*n)
return ans

n = 500
for k in range(10):
print(a(n, k))


As suggested by @StevenStadnicki above, I'll formulate my comment as an answer.

For $$n\to\infty$$, the coefficients of $$\tag{1}\label{eq:1} P_\infty(x) = \lim_{n\to\infty}P_n(x) = \prod_{k=1}^\infty (1+x^k)^k = \sum_{k=1}^\infty a(\infty,k) \, x^k$$ are $$\tag{2}\label{eq:2} a(\infty,k)=(1,1,2,5,8,16,28,49,83,142,235,385,627,1004,\ldots)$$ and are given by https://oeis.org/A026007. There seems to be no "closed-form" representation nor recurrence relation for $$a(\infty,k)$$. An $$n{+}1$$-step recurrence for $$a(n,k)$$ is given in the answer by @AspiringMat, which can be slightly simplified to the $$\lfloor k/n \rfloor{+}1$$-step recursion $$\tag{3}\label{eq:3} a(n,k) = \begin{cases} 1, & \text{if n=0 \wedge k\in\{0,1\} },\\ 0, & \text{if n=0 \wedge k>1 },\\ \sum_{j=0}^{\lfloor k/n \rfloor}\binom{n}{j} \, a(n{-}1,k{-}jn), & \text{otherwise.} \end{cases}$$

However, the terms of $$a(n,k)$$ for $$k\leq n$$ are the same as in $$a(\infty,k)$$, $$\tag{4}\label{eq:4} a(n,k)=a(\infty,k) \quad \forall \,\,\, k\leq n$$ because the first factor $$(1+x^{n+1})^{n+1}$$ in $$P_\infty(x)/P_n(x)$$ only contributes from order $$x^{n+1}$$ onwards.

For $$k>n$$, obviously $$a(n,k).