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

Question

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

Answer 1

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$

Answer 2

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))

Answer 3

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)<a(\infty,k)$.