3
$\begingroup$

Show that $$ \sum_{m=0}^n (-1)^m \binom{n}{m} = 0$$

I have first difficulty understanding the summation notation: For example what $ \sum_{m=0}^3 (-1)^m \binom{n}{m}$ would mean? I suppose that it means: $$ \sum_{m=0}^2 (-1)^m \binom{n}{m} = (-1)^0 \binom{2}{0} + (-1)^1 \binom{2}{1} + (-1)^2 \binom{2}{2} $$

$$ \sum_{m=0}^2 (-1)^m \binom{n}{m} = + 1 - 2 + 1 =0 $$

If it is such case, it shows that the value of $(-1)^m$ alternate positive when $m$ is even and negative when $m$ is odd.

Therefore the sum when $m$ is even $+$ the sum when $m$ is odd $= 0$ and we can then factor out the constant $+1$ from the first sum and $-1$ from the second sum and then QED.

Is this approach correct? How to write this using sum notation when $m$ even and when $m$ is odd?
Is there a better approach?

Much appreciated.

$\endgroup$
3
$\begingroup$

the expansion of $(1+(-1))^n=\sum _0 ^n (-1)^m .(1)^{n-m} {n \choose m}$

$\endgroup$
  • 1
    $\begingroup$ Use ${n\choose m} = {n-1\choose m}+{n-1\choose m-1}$ to see that most of the binomial coefficients cancel. For the rest, use the boundaries ${n\choose 0}= 1={n\choose n}$. $\endgroup$ – Wuestenfux May 27 '17 at 6:42
1
$\begingroup$

This is Newton's Binomial Series:

$$\sum_{m=0}^n\binom{n}{m}(-1)^m = \sum_{m=0}^n\binom{n}{m}(-1)^m1^{n-m} = (-1 + 1)^n = 0^n = 0$$

$\endgroup$
1
$\begingroup$

We have, $$(a+b)^n=\sum\limits_{m=0}^n {n \choose m}a^{n-m}b^m$$

Now, put $a=1, b=-1$

$\sum\limits_{m=0}^n {n \choose m}(-1)^m=(1-1)^n=0$

$\endgroup$
  • $\begingroup$ Thx for the input, How do you demonstrate $(a+b)^n=\sum\limits_{m=0}^n {n \choose m}a^{n-m}b^m$? $\endgroup$ – gegu May 27 '17 at 7:08
  • $\begingroup$ That is known as Binomial Expansion. en.wikipedia.org/wiki/Binomial_theorem $\endgroup$ – Dharmaraj Deka May 27 '17 at 7:11
1
$\begingroup$

There is a combinatorial proof of this fact too. Suppose $n\geq 1$ (otherwise it is trivial). Let $N$ be a set of $n$ elements. Let $S_0=\{A\subseteq N\colon |A|\,\text{even}\}$ and $S_1=\{A\subseteq N\colon |A|\,\text{odd}\}$. The identity in question is equivalent to $|S_0|=|S_1|$. Fix an element $a\in N$. Define the map $\varphi\colon S_0\to S_1$ by $$ \varphi(A)= \begin{cases} A\cup\{a\}&\text{if $a\notin A$}\\ A\setminus\{a\}&\text{if $a\in A$}. \end{cases} $$ It is easy to see that the map $\varphi$ is a bijection (easy to write down an inverse) and hence $|S_0|=|S_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.