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} $


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

  • $\begingroup$ 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$. $\endgroup$ Commented Feb 13 at 18:43
  • $\begingroup$ @AspiringMat how we can get it ? show me please maybe it will help me to understand how to find a recurrence relation $\endgroup$
    – Faoler
    Commented Feb 13 at 19:44
  • 6
    $\begingroup$ 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).$ $\endgroup$
    – Fred Hucht
    Commented Feb 13 at 21:04
  • 1
    $\begingroup$ @GerryMyerson of course the second one..its just a typo I will fix it sorry for that $\endgroup$
    – Faoler
    Commented Feb 14 at 5:32
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Terry Tao
    Commented Feb 18 at 19:57

3 Answers 3


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$

  • $\begingroup$ Nice work Fao (+1) $\endgroup$ Commented Feb 18 at 14:24
  • $\begingroup$ @AliShadhar thanks $\endgroup$
    – Faoler
    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}$$


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

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)

def a(n, k):
    if k<0:
        return 0
    if n==1:
        if k==0 or k==1:
            return 1
            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)<a(\infty,k)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.