Proving that ${n \choose 1} - 2{n \choose 2} + 3{n \choose 3} + \dots + (-1)^{n - 1}n{n \choose n} = 0$

Question

I want to prove the following equality: $${n \choose 1} - 2{n \choose 2} + 3{n \choose 3} + \dots + (-1)^{n - 1}n{n \choose n} = 0$$ I tried taking the negative terms to the right hand side. The term $k{n \choose k}$ is equal to the number of teams of $k$ members with a captain. Then, proving this equality is equivalent to proving that the number of even teams with a captain is equal to the number of odd teams with a captain. However, I'm pretty stuck here. I know that the number of odd subsets is equal to the number of even subsets. But I don't know how to approach this specific problem. I tried defining a bijection between the even teams and the odd teams but I didn't get anywhere.

Hints would be appreciated. Thanks in advance.

Answer 1

Notice that this is not true for $n=1$.

Following your attempt, picking a team with captain is just picking a captain, and then adding players from the remaining $n-1$ players (this is a combinatorial proof of the equality $k{n\choose k} = n {n-1\choose k-1}$ mentioned in ZAF's answer).

The parity of the team is determined by the parity of the team without the captain. Then use what you already know.

Answer 2

Note that $k{n \choose k} = n {n-1 \choose k-1}$

Then you have $$\sum_{k = 1}^{n}(-1)^{k-1} k{n \choose k} =\sum_{k = 1}^{n} (-1)^{k-1}n {n-1 \choose k-1} = n\sum_{k = 1}^{n} (-1)^{k-1} {n-1 \choose k-1}= n\sum_{k = 0}^{n-1} (-1)^{k}{n-1 \choose k}= $$

$$n\sum_{k = 0}^{n-1} (-1)^{k}1^{n-1-k }{n-1 \choose k} = n(1-1)^{n-1} = 0$$

Answer 3

The sum you want to find is: $$S=\sum_{i=1}^{n}\binom{n}{i}\cdot r\cdot(-1)^{i+1}$$

Use the identy $\binom{n}{r}=\binom{n-1}{r-1}\cdot\frac{n}{r}$ to get $r\cdot\binom{n}{r}=n\cdot\binom{n-1}{r-1}$ and the sum becomes

$$\sum_{i=1}^{n}n\cdot\binom{n-1}{i-1}(-1)^{i+1}=n\left(\sum_{i=1}^{n}\binom{n-1}{i-1}(-1)^{i+1}\right)$$

Make change of index as $j=i-1$ to get

$$S=n\left(\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^j\right)=n\left(\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^j(1)^{n-1-j}\right)$$

Use the sum is as the binomial expanssion of $(x+a)^m$ with $x=1,a=-1,m=n-1$ so we get

$$S=n(1+(-1))^{n-1}=n(1-1)^{n-1}=0^{n-1}$$

for $n\geq2, 0^{n-1} = 0$

therefore for $n\geq2, S = 0$ and for $n=1$ it will be just the first term i.e. 1. $$S=\begin{cases} 0 & n\geq 2 \\ 1 & n=1 \end{cases}$$