5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

$$(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}$$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.