<s>[INST] Formula for $\sum_{k=0}^n k^d {n \choose 2k}$ If $d \geq 1$ is an integer, is there a general formula for $$\sum_{k=0}^n k^d {n \choose 2k}\,?$$
We know that $\sum_{k=0}^n k {n \choose 2k} = \frac{n2^n}{8}$ and $\sum_{k=0}^n k^2 {n \choose 2k} = \frac{n(n+1)2^n}{32}$.
Note that ${n \choose 2k} = 0$ when $2k > n$.
 [/INST] This is an half-answer. We have
$$(1+x)^{n}=x^{0}\binom{n}{0}+x^{1}\binom{n}{1}....+x^{n}\binom{n}{n}$$
If we take derivative of this with respect to x.
$$n(1+x)^{n-1}=1x^{0}\binom{n}{1}+2x^{1}\binom{n}{1}....+nx^{n-1}\binom{n}{n}$$
For $x=1$ we have $$n2^{n-1}=1\binom{n}{1}+2\binom{n}{2}....+n\binom{n}{n}$$
Now if we multiply the equation before this one with x and take derivative again.
$$n(1+x)^{n-1}+n(n-1)(1+x)^{n-2}=1^2x^{0}\binom{n}{1}+2^2x^{1}\binom{n}{1}....+n^2x^{n-1}\binom{n}{n}$$
For $x=1$ $$n2^{n-1}+n(n-1)2^{n-2}=1^2\binom{n}{1}+2^2\binom{n}{2}....+n^2\binom{n}{n}$$
We conclude by induction that
$$n2^{n-1}+n(n-1)2^{n-2}..+n(n-1)(n-2)...(n-d+1)2^{n-d}=1^d\binom{n}{1}+2^d\binom{n}{2}....+n^d\binom{n}{n}$$
I don't know what to do next.
</s>