TITLE: How to compute the summation of a binomial coefficient/ show the following is true
QUESTION [2 upvotes]: $\sum\limits_{k=0}^n \left(2k+1\right) \dbinom{n}{k} = 2^n\left(n+1\right)$.
I know that you have to use the binomial coefficient, but I'm not sure how to manipulate the original summation to make the binomial coefficient useful.

REPLY [2 votes]: The Binomial Theorem states that $$(x + y)^n = \sum_{k = 0}^{n} x^{n - k}y^k$$ If we set $x = y = 1$, we obtain
$$2^n = (1 + 1)^n = \sum_{k = 0}^n \binom{n}{k}1^{m - k}1^k = \sum_{k = 0}^{n} \binom{n}{k}$$
We will also make use of Pascal's Identity $$\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}$$
Here is a proof by induction.
Let $P(n)$ be the statement $$\sum_{k = 0}^n (2k + 1)\binom{n}{k} = 2^n(n + 1)$$
Let $n = 0$. Then 
$$\sum_{k = 0}^{0} (2k + 1)\binom{0}{k} = (2 \cdot 0 + 1)\binom{0}{0} = 1 \cdot 1 = 1 = 1(0 + 1) = 2^0(0 + 1)$$
so $P(0)$ holds.  
Hence, we may assume $P(m)$ holds for some non-negative integer $m$.  Let $n = m + 1$.  Then
\begin{align*}
\sum_{k = 0}^{m + 1}(2k + 1)\binom{m + 1}{k} & = 1 + \sum_{k = 1}^{m} (2k + 1)\color{red}{\binom{m + 1}{k}} + 2m + 3\\
& = 2m + 4 + \sum_{k = 1}^{m} (2k + 1)\color{red}{\left[\binom{m}{k} + \binom{m}{k - 1}\right]}\\
& = 2m + 4 + \sum_{k = 1}^{m} (2k + 1)\binom{m}{k} + \sum_{k = 1}^{m} (2k + 1)\binom{m}{k - 1}\\
& = 2m + 4 - 1 + \sum_{k = 0}^{m} (2k + 1)\binom{m}{k} + \sum_{k = 1}^{m} [2(k - 1) + 3]\binom{m}{k - 1}\\
& = 2m + 3 + \sum_{k = 0}^{m} (2k + 1)\binom{m}{k} + \sum_{k = 0}^{m - 1} (2k + 3)\binom{m}{k}\\
& = 2m + 3 + \sum_{k = 0}^{m} (2k + 1)\binom{m}{k} + \sum_{k = 0}^{m} (2k + 3)\binom{m}{k} - (2m + 3)\\
& = \sum_{k = 0}^{m} (2k + 1)\binom{m}{k} + \sum_{k = 0}^{m} (2k + 1)\binom{m}{k} + \sum_{k = 0}^{m} 2\binom{m}{k}\\
& = 2\color{blue}{\sum_{k = 0}^{m} (2k + 1)\binom{m}{k}} + 2\color{green}{\sum_{k = 0}^m \binom{m}{k}}\\
& = 2 \cdot \color{blue}{2^m(m + 1)} + 2 \cdot \color{green}{2^m}\\
& = 2^{m + 1}(m + 1) + 2^{m + 1}\\
& = 2^{m + 1}[(m + 1) + 1]
\end{align*}
where I have used red to highlight Pascal's Identity, blue to highlight the induction hypothesis, and green to highlight the use of the fact that $$2^m = \sum_{k = 0}^{m} \binom{m}{k}$$
Since $P(0)$ holds and $P(m) \Rightarrow P(m + 1)$ for each non-negative integer $m$, $P(n)$ holds for each non-negative integer $n$.
{"set_name": "stack_exchange", "score": 2, "question_id": 1164366}