# $\sum\limits_{k=0}^{\frac{n}{2}} 2k\binom{n}{2k}=n\cdot2^{n-2}$

Let $n\geq 2$ be even. Show that $$\sum\limits_{k=0}^{\frac{n}{2}} 2k\binom{n}{2k}=n\cdot2^{n-2}$$ 1) In a combinatorial way. (hint: count pairs $(x,S)$ s.t. $x\in S\subset \{1,2,...,n\}$ where $|S|$ is even)

2) Using binomial theorem. (hint: derivate $(1+x)^n+(1-x)^n$ )

Progress:
1) From the hint I was able to derive that the LHS counts the number of subsets $S_i$ where $|S_i|$ is even for all $i$s, multiplied by its cardinality, though I'm not sure about that. How does one put it in a combinatorial proof?

2) I calculated the derivative, but nothing yet.

$$(1+x)^n+(1-x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k+\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}x^k$$

Using that since $n$ is even $(-1)^{n-k}=(-1)^k$. For even $k$ the terms cancel each other out so:

$$(1+x)^n+(1-x)^n=\sum_{k=0}^{n/2}2\binom{n}{2k}x^{2k}$$

Taking the derivative of both sides we get:

$$n(1+x)^{n-1}-n(1-x)^{n-1}=\sum_{k=0}^{n/2}4k\binom{n}{2k}x^{2k-1}$$

Plugging in $x=1$ yields $$n\cdot 2^{n-2}=\sum_{k=0}^{n/2}2k\binom{n}{2k}$$

Consider the set of pairs $(x,S)$ where $S$ is a subset of $[n]$ of even cardinality and $x$ is an element of S. If $S$ has cardinality $2k$ there are $\binom{n}{2k}$ choices and there are $2k$ ways to choose $x$ so we have \begin{eqnarray*} \sum\limits_{k=0}^{\frac{n}{2}} 2k\binom{n}{2k}. \end{eqnarray*} On the other hand we can choose $x$ in $n$ ways and then $S=\{x\} \cup S'$ where $S'$ is a subset of $[n] / \{x\}$, choose the first $n-2$ elements to be either in or not in $S'$ ($2^{n-2}$ ways) and then choose the final element to be in or not in $S'$ in order that the cardinality of $S'$ is odd, so that gives $n 2^{n-2}$.

For the second part, differentiate & set $x=1$.

For the second part consider $$\sum_{k=0}^{\frac {n}{2}} 2k. \binom {n}{2k}=n\sum_{k=1}^{\frac {n}{2}} \binom {n-1}{2k-1}$$ Let $n=2m$ Then our identity converts to $$2m\sum_{k=1}^{m} \binom {2m-1}{2k-1}$$

Now we have $$(1+x)^{2m-1}=\sum_{k=0}^{2m-1} \binom {2m-1}{k}.x^k$$ And $$(1-x)^{2m-1}=\sum_{k=0}^{2m-1} \binom {2m-1}{k}.(-x)^k$$

Hence we get $$(1+x)^{2m-1}- (1-x)^{2m-1}= 2\sum_{k=1}^{m} \binom {2m-1}{2k-1}x^k$$

Hence putting $x=1$ We have $$2^{2m-1}=2\sum_{k=1}^{m} \binom {2m-1}{2k-1}$$ Hence we get $$2^{2m-2}= \sum_{k=1}^{m} \binom {2m-1}{2k-1}$$

Thus the value of our identity becomes $$\sum_{k=0}^{\frac {n}{2}} 2k. \binom {n}{2k}=n. 2^{n-2}$$