1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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