Seeking a combinatorial proof $\sum\limits _{k=0}^n (n-2k)^2\binom{n}{k}=n\times 2^n$

Question

I would appreciate if somebody could help me with the following problem

Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$

$$\sum _{k=0}^n (n-2 k)^2 \binom{n}{k}=n\times 2^n$$

Answer 1

Consider all subsets of a set of $n$ elements, along with their complements; count $+1$ for each ordered pair of (possibly identical) elements that are in the same set (i.e. both in the subset or both in its complement) and $-1$ for each ordered pair of elements that aren't. Then for a subset of size $k$, of which there are $\binom nk$, the sum is $((n-k) - (k))^2=(n-2k)^2$. A pair of different elements doesn't contribute to the sum over all subsets, since they are in the same set just as often as they are in different sets. A pair of identical elements contributes $+1$ for each of the $2^n$ subsets, and there are $n$ such pairs.

Answer 2

Here's a proof using generating functions. (What could be more combinatorial?)

Let $s_n$ be the sum in question and $f$ the exponential generating function of the sequence of $s_n$'s. Algebra-wise, $(n-2k)^2=(n-k)^2-2k(n-k)+k^2$, so $s_n=2\sum_k\binom nk(k^2-k(n-k))$. Then, the product rule for exponential generating functions applies. The egf of the sequence $\langle n:n\ge0\rangle$ is $xe^x$ and the egf of $\langle n^2:n\ge0\rangle$ is $x(x+1)e^x$. Two applications of the product rule give $f(x)=2(x(x+1)e^x\cdot e^x-(xe^x)^2)$. This simplifies to $f(x)=2xe^{2x}$. Extracting the coefficient of $x^n$, we get $s_n=n!2[x^n]xe^{2x}=n2^n$.