Proving a formula with binomial coefficient

Question

Is this formula true? How can I prove it? $$\sum_{s=0}^{n-1}\binom{n-1}{s}2s =2^{n-1}(n-1)$$

Thanks!

Answer 1

Hint: $\binom {n-1}{s}\frac{s}{n-1} = \binom{n-2}{s-1} $.

Answer 2

Hint. Consider $$f(x) = (1+x)^{n-1} = \sum_{s=0}^{n-1} \begin{pmatrix}n-1\\s\end{pmatrix}x^s. $$ Your sum is related to $f'(1)$.

Answer 3

There's no reason to use $n-1$ as the upper limit. Let me recast it with $m=n-1$. I'll also divide both sides by $2$. Then you have

$\sum_{s=0}^m s \binom{m}{s}$ on the left and $m2^{m-1}$ on the right.

Let's see what is being counted on the left. Consider a set of $m$ objects. Each term on the left is the total number of subsets of size s times the number of things in the size s subsets.

You may be aware that there are $2^m$ total subsets of $m$ objects. If I divide by $2^m$, then the left hand side is the expected number of elements in a random subset of $m$. The right hand side is $m/2$. Does the average subset have size $m/2$? There's an elegant way to pair up subsets to show this.

Answer 4

$$\begin{align} \sum_{s=0}^{n-1}\binom{n-1}{s}2s &=2\sum_{s=1}^{n-1}\binom{n-1}{s}\binom s1\\ &=2\sum_{s=1}^{n-1}\binom{n-1}{1}\binom {n-2}{s-1}\qquad \text{(subset of a subset)}\\ &=2\binom{n-1}1\sum_{s=1}^{n-1}\binom{n-2}{s-1}\\ &=2(n-1)\sum_{s=0}^{n-2} \binom{n-2}{s}\\ &=2(n-1)\cdot 2^{n-2}\\\\ &=2^{n-1}(n-1)\qquad \blacksquare \end{align}$$