How to compute the summation of a binomial coefficient/ show the following is true

Question

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

Answer 1

For $k-1\ge0\iff k\ge1$

$$(2k+1)\binom nk=2k\cdot\frac{n\cdot(n-1)!}{k\cdot(k-1)!\cdot\{n-1-(k-1)\}!}+\binom nk$$

$$=2n\binom{n-1}{k-1}+\binom nk$$

For $k=0,$ $$(2k+1)\binom nk=\binom n0$$

Now use $\displaystyle(1+1)^m=\sum_{r=0}^m\binom mr$

Answer 2

Consider $$f(x)=(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k$$ so $$f'(x)=\sum_{k=1}^{n}k\binom{n}{k}x^{k-1}$$ Hence $$f'(1)=\sum_{k=1}^{n}k\binom{n}{k}=\sum_{k=0}^{n}k\binom{n}{k}$$ On the other hand $$f'(x)=n(1+x)^{n-1}\Rightarrow f'(1)=n2^{n-1}$$ It follows that $$\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}$$ Similarly we have $$\sum_{k=0}^n\binom{n}{k}=f(1)=2^n$$ Put all stuff together gives $$\sum_{k=0}^n(2k+1)\binom{n}{k}=2^n(n+1)$$

Answer 3

Let $X$ be the number of heads in $n$ flips of a fair coin (i.e. a random variable with $\text{Binomial}(n,1/2)$ distribution). Then $$\sum_{k=0}^ n {n \choose k} 2^{-n} (2k+1) = \mathbb E[2X+1] = 2 \mathbb E[X] + 1 = n + 1$$

Answer 4

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