A proof in combinatorics (prove by any method)

Question

I came across the following proof in my textbook that was used as a end of chapter review. How can I prove the following by using any method?

$$\left( \begin{array}{c} n \\ 1\ \end{array} \right) + 3 \left( \begin{array}{c} n \\ 3\ \end{array} \right) +5 \left( \begin{array}{c} n \\ 5\ \end{array} \right) +... = 2 \left( \begin{array}{c} n \\ 2\ \end{array} \right) + 4 \left( \begin{array}{c} n \\ 4\ \end{array} \right)+... $$

Could use some help as I work through possible exam questions.

Answer 1

Putting the right-hand side to the left we have \begin{align*} \binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}-\cdots= \begin{cases} 1\qquad n=1\\ 0\qquad n>1 \end{cases} \end{align*} or in more compact notation using Iverson brackets: \begin{align*} \sum_{k=1}^n(-1)^{k+1}k\binom{n}{k}=[[n=1]] \end{align*}

We obtain for integer $n>0$ \begin{align*} \color{blue}{\sum_{k=1}^n(-1)^{k+1}k\binom{n}{k}} &=n\sum_{k=1}^n(-1)^{k+1}\binom{n-1}{k-1}\tag{1}\\ &=n\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}\tag{2}\\ &=n(1-1)^{n-1}\tag{3}\\ &\color{blue}{=[[n=1]]} \end{align*} and the claim follows.

Comment:

• In (1) we apply the binomial identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$.

• In (2) we shift the index $k$ to start with $k=0$.

• In (3) we apply the binomial theorem.

Answer 2

The way @EwanDelanoy has told in the comments is absolutely correct. I shall be using $C_0$, $C_1$ etc. for $\binom{n}{0}$, $\binom{n}{1}$ and so on.

Here's how the proof goes :

$$(1 - x)^n = C_0 - C_1x + C_2x^2 - C_3x^3 + ..... + (-1)^n.C_nx^n$$

Differentiating both sides with respect to $x$, $$-n(1 - x)^{n-1} = -C_1 + 2.C_2x - 3.C_3x^2 + 4.C_4x^3 - ....$$ (You can verify this by using the Chain Rule)

On putting $x = 1$, $$0 = -C_1 + 2.C_2 - 3.C_3 + 4.C_4 - ....$$ $$\implies C_1 + 3.C_3 + 5.C_5 + .... = 2.C_2 + 4.C_4 + 6.C_6 + ....$$ (Taking the negative terms to the L.H.S.)