Binomial sum of $\sum\limits_{k=0}^{n} k \binom{n}{k} (-1)^{k-1} 2^{n-k}$

Question

Evaluate $\displaystyle{\sum_{k=0}^{n} k \binom{n}{k} (-1)^{k-1} 2^{n-k}}$

So if the $k$ wasn't here this binomial sum would be really easy to solve. How would you evaluate this then?

Answer 1

Let $n>1$ be an integer. There are $n$ people in a certain country, and we label them $1$, $2$, $\ldots$, $n$. The people want to form a parliament. Some of them are chosen to be in the house of representatives, and one of the representatives is elected to be the prime minister. Then, some of the remaining people that are not in the house of representatives are selected to in the senate. Let $R$ and $S$ denote the set of representatives and the set of senators, respectively. Write $\mathcal{T}$ for the set of all possible choices $(p,R,S)$, where $p\in R$ is the prime minister.

If $|R|=k$ for some $k=0,1,2,\ldots,n$, then clearly, there are $$k\,\binom{n}{k}\,2^{n-k}$$ possible triples $(p,R,S)$. Let $\Delta$ denote the symmetric difference operator. Define $f:\mathcal{T}\to\mathcal{T}$ as follows: $$f(p,R,S):=\begin{cases}(p,R,S)&\text{if }R\cup S=\{p\}\,, \\\big(p,R\triangle \{p+k\}, S\triangle\{p+k\}\big)&\text{else}\,,\end{cases}$$ for each $(p,R,S)\in\mathcal{T}$, where in the case $R\cup S$ contains more than one element, $k<n$ is the smallest positive integer such that $p+k$ is in $R\cup S$, and $p+k$ is considered modulo $n$. Observe that $f$ is an involution on $\mathcal{T}$ with $n$ fixed points of the form $\big(p,\{p\},\emptyset\big)$, where $p=1,2,\ldots,n$.

For $s\in \{0,1\}$, let $\mathcal{T}_s$ denote the subset of $\mathcal{T}$ consisting of $(p,R,S)$ in which $|R|\equiv s\pmod{2}$. Write also $\mathcal{A}:=\Big\{ \big(p,\{p\},\emptyset\big)\,\Big|\,p\in\{1,2,\ldots,n\}\Big\}$ for the set of all possible parliaments with a sole dictator. Then, $\mathcal{A}\subseteq \mathcal{T}_1$, and $$f|_{\mathcal{T}_0}:\mathcal{T}_0\to \left(\mathcal{T}_1\setminus\mathcal{A}\right)$$ is a bijection. Therefore, $$\left|\mathcal{T}_1\right|-n=\left|\mathcal{T}_1\right|-|\mathcal{A}|=\left|\mathcal{T}_1\setminus\mathcal{A}\right|=\left|\mathcal{T}_0\right|\,.$$ In other words, $$n=\left|\mathcal{T}_1\right|-\left|\mathcal{T}_0\right|=\sum_{k=0}^n\,(-1)^{k-1}\,k\,\binom{n}{k}\,2^{n-k}\,.$$

Answer 2

We have $$ \sum_{k=0}^n\binom{n}{k}z^k 2^{n-k}=(z+2)^n. $$ Differentiating with respect to $z$ gives $$ \sum_{k=0}^nk\binom{n}{k}z^{k-1}2^{n-k}=n(z+2)^{n-1} $$ and now substitute $z=-1$. Equivalently, you can use $\displaystyle k\binom{n}{k}=n\binom{n-1}{k-1}$ immediately inside the sum.