I'm trying to calculate the $[x^n]F(x)$ from a generating function $F(x) = \frac{1}{(1-2x^2)^2}$ and I came across with this expression involving a sum:
$$2^n\sum_{k=0}^n k^k (n-k)^{n-k}$$
What I did so far was calculate the $[x^n]\frac{1}{1-2x^2}$, witch is $(2n)^n$ if I'm not wrong, and then making a convolution $\frac{1}{1-2x^2} . \frac{1}{1-2x^2}$ to find $[x^n]$.
My question is, how can I obtain a closed-form for the sum above?
It would seem that based on the series $$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$$ that $$\frac{1}{1- 2 \, x^2} = \sum_{n=0}^{\infty} 2^{n} \, x^{2n} = \sum_{n=0}^{\infty} 2^{n/2} \, \left(\frac{1+(-1)^{n}}{2}\right) \, x^n.$$
From this then: \begin{align} \frac{1}{(1- 2 x^2)^2} &= \sum_{r=0}^{\infty} \sum_{s=0}^{\infty} 2^{(r+s)/2} \, \left(\frac{1+(-1)^{r}}{2}\right)\left(\frac{1+(-1)^{s}}{2}\right) \, x^{r+s} \\ &= \sum_{n=0}^{\infty} \sum_{s=0}^{n} 2^{n/2 -2} \, (1+(-1)^{n-s})(1+(-1)^{s}) \, x^{n} \\ &= \sum_{n=0}^{\infty} 2^{n/2 - 2} \, (1 + (-1)^n) \, \sum_{s=0}^{n} (1 + (-1)^{s}) \, x^n \\ &= \sum_{n=0}^{\infty} 2^{n/2 -3} \, [2 (n+1) (1 + (-1)^n) + (1 + (-1)^n)^2] \, x^n \\ &= \sum_{n=0}^{\infty} \left( \frac{2^{n/2} \, (n + 2) \, (1 + (-1)^{n})}{4} \right) \, x^n. \end{align}
Alternatively using $$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} (n+1) \, x^{n}$$ then \begin{align} \frac{1}{(1- 2 x^2)^2} &= \sum_{n=0}^{\infty} 2^{n} \, (n+1) \, x^{2n} \\ &= \sum_{n=0}^{\infty} \left(\frac{2^{n/2} \, (n+2) \, (1 + (-1)^{n})}{4} \right) \, x^n. \end{align}