Proving that $\sum_{k=0}^{k=n} \binom{2n}{k} \cdot k = 2^{2n -1} \cdot n$

Question

I have to show that $\sum_{k=0}^{k=n} \binom{2n}{k} \cdot k = 2^{2n -1} \cdot n$.

What I know is that $\sum_{k=0}^{k=n} \binom{n}{k} \cdot k = 2^{n -1} \cdot n$.

How do I proceed from there?

Answer 1

\begin{align} \sum_{k=0}^n k\binom{2n}{k} &= \sum_{k=1}^n k\binom{2n}{k} \\ &= \sum_{k=1}^n 2n\binom{2n-1}{k-1} \\ &= n \sum_{k=1}^n \left(\binom{2n-1}{k-1} + \binom{2n-1}{k-1}\right) \\ &= n \sum_{k=1}^n \left(\binom{2n-1}{k-1} + \binom{2n-1}{2n-k}\right) \\ &= n \sum_{j=0}^{2n-1} \binom{2n-1}{j} \\ &= n \cdot 2^{2n-1} \end{align}

---

Alternatively, a combinatorial proof is to count the number of committees of size at most $n$ with one chairperson from $2n$ people. The LHS conditions on the size $k$ of the committee. The RHS selects the chairperson (in $2n$ ways) and then any subset of size at most $n-1$ from the remaining $2n-1$ people (to see that there are $2^{2n-1}/2$ of these, consider complementary pairs).

Answer 2

$$\dbinom{2n}{0}+\dbinom{2n}{1}+\dbinom{2n}{2}+...+\dbinom{2n}{2n-1}+\dbinom{2n}{2n}=2^{2n}$$

$$\dbinom{2n}{0}+\dbinom{2n}{1}+\dbinom{2n}{2}+...+\dbinom{2n}{n-1}+\dbinom{2n}{n}=2^{2n-1}$$

$$\dbinom{n}{k}=\dbinom{n}{n-k}$$

$$k\dbinom{n}{k}+(n-k)\dbinom{n}{n-k}=n\dbinom{n}{k}$$

$$0\dbinom{2n}{0}+1\dbinom{2n}{1}+2\dbinom{2n}{2}+...+(2n-1)\dbinom{2n}{2n-1}+2n\dbinom{2n}{2n}=2n\dbinom{2n}{0}+2n\dbinom{2n}{1}+2n\dbinom{2n}{2}+...+2n\dbinom{2n}{n-1}+2n\dbinom{2n}{n}=2n(\dbinom{2n}{0}+\dbinom{2n}{1}+\dbinom{2n}{2}+...+\dbinom{2n}{n-1}+\dbinom{2n}{n})=2n\times 2^{2n-1}$$

Hence

$$n\dbinom{2n}{0}+n\dbinom{2n}{1}+n\dbinom{2n}{2}+...+n\dbinom{2n}{n-1}+n\dbinom{2n}{n}=n\times2^{2n-1}$$

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $\ds{\bbox[5px,#ffd]{\sum_{k = 0}^{n}{2n \choose k}k = 2^{2n -1}\,\,n}:\ {\Large ?}}$.

---

\begin{align} &\bbox[5px,#ffd]{\sum_{k = 0}^{n}{2n \choose k}k} = \sum_{k = 1}^{n} {\pars{2n}! \over \pars{k - 1}!\pars{2n - k}!} \\[5mm] = &\ \sum_{k = 0}^{n - 1} {\pars{2n}! \over k!\pars{2n - k - 1}!} = \color{red}{2n\sum_{k = 0}^{n - 1}{2n - 1 \choose k}} \\[5mm] = &\ 2n\ \underbrace{\sum_{k = 0}^{2n - 1}{2n - 1 \choose k}} _{\ds{2^{2n - 1}}}\ -\ 2n\sum_{k = n}^{2n - 1}{2n - 1 \choose k} \\[5mm] = &\ 2^{2n}\,n - 2n\sum_{k = 0}^{n - 1}{2n - 1 \choose k + n} = 2^{2n}\,n - 2n\sum_{k = 0}^{n - 1}{2n - 1 \choose n - 1 - k} \\[5mm] = &\ 2^{2n}\,n - \color{red}{2n\sum_{k = 0}^{n - 1} {2n - 1 \choose k}} \end{align}

---

\begin{align} &\bbox[5px,#ffd]{\sum_{k = 0}^{n}{2n \choose k}k} = \color{red}{2n\sum_{k = 0}^{n - 1} {2n - 1 \choose k}} = {2^{2n}\,n \over 2} = \bbx{2^{2n - 1}\,n} \\ & \end{align}