Evaluation of $\sum\limits_{k=1}^n\left(x^{k}+\frac{1}{x^k}\right)^k$

Question

Can anyone find a simplified expression for the sum $\displaystyle \sum_{k=1}^n\left(x^{k}+\frac{1}{x^k}\right)^k$? I have tried expanding the first few terms but it gets a little messy with no clear leads. I suspect formulae for geometric series may come into it somehow, but at the moment it isn't clear how to start.

Answer 1

Let $S(n)$ be your sum. For $1 \le m \le n^2$, the coefficient of $x^m$ (and of $x^{-m}$, by symmetry) in $S(n)$ is $$ [x^m]\; S(n) = \sum_k {k \choose \frac{m}{2k}+\frac{k}{2}}$$ where the sum is over all divisors $k$ of $m$ such that $m \le k^2 \le n^2$ and $\frac{m}{k} \equiv k \mod 2$. In particular this is $0$ if $m \equiv 2 \mod 4$.

The coefficient of $x^0$ in $S(n)$ is $$ [x^0] \; S(n) = \sum_{j=1}^{\lfloor n/2 \rfloor} {2j \choose j}$$