Evaluation of $\sum\limits_{k=1}^n\left(x^{k}+\frac{1}{x^k}\right)^k$ 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. 
 A: 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}$$
A: Not an answer, just a long comment;
Not sure how to proceed, but one way to rewrite it is $x=e^{i\phi}$, getting
$$\sum_{k=1}^n (2\cos k\phi)^k=\sum_{k=1}^n 2^k T_k^k(\cos(\phi))$$
where $T$ is a Chebyshev polynomial of the first kind.
It seems to me that the expression is too convoluted to expect a nice solution. Another similar approach that might be considered is to express everything with $x+x^{-1}$. We have expressions of the type
$$(x+x^{-1})^2=2+(x^2+x^{-2})$$
$$(x+x^{-1})^3=3(x+x^{-1})+(x^3+x^{-3})$$
which could be solved for $x^k+x^{-k}$ but I can't see how to get a closed form for a general term. This solution does give you the constant term (reproduces result by @RobertIsrael) but the rest gets complicated due to $()^k$ - we get summations over very strange sets.
A reference that might be useful - it includes some very similar expressions.
