How to prove that $\sum_{k=0}^{n}(-1)^k \binom {n}{k}=0 $

Question

Given a positive integer $n$. How to prove that $\sum\limits_{k=0}^{n}(-1)^k \dbinom{n}{k} = 0 $ ?

I've tried using mathematical induction, then:
$$p(1)=\sum_{k=0}^{1}(-1)^k \binom {1}{k}=0 $$
And my induction hypothesis is: $$p(n)=\sum_{k=0}^{n}(-1)^k \binom {n}{k}=0 $$ So, i need prove: $$p(n+1)=\sum_{k=0}^{n+1}(-1)^{k} \binom {n+1}{k}=0 $$ Let $\sum_{k=0}^{n+1}(-1)^{k} \binom {n+1}{k}$, $$\begin{align} \sum_{k=0}^{n+1}(-1)^{k} \binom {n+1}{k} &= \sum_{k=0}^{n}(-1)^{k} \binom {n}{k}+(-1)^{k} \binom {n+1}{n+1} \\ &=0 + (-1)^{k} \end{align}$$ What am i doing wrong?

Answer 1

The last passage should actually be $$ \begin{gathered} \sum\limits_{\left( {0\, \leqslant } \right)\,k\, \leqslant \,\left( {n + 1} \right)} {\left( \begin{gathered} n + 1 \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k} } = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k} } + \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k - 1 \\ \end{gathered} \right)\left( { - 1} \right)^{\,k} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k} } + \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k + 1} } = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k} } - \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)\left( { - 1} \right)^{\,k} } = 0 \hfill \\ \end{gathered} $$

Note that you can not take account of the bounds in the summation because they are implicit in the definition of the binomial.

Answer 2

In your last line I assume you are trying to split up the sum, that is, write the last term separately. However this does not change the terms inside the sum, so it should be $$\sum_{k=0}^{n+1}(-1)^k\binom{n+1}k =\left[\sum_{k=0}^n(-1)^k\binom{n+1}k\right]+(-1)^{n+1}\binom{n+1}{n+1}\ .$$ Unfortunately now the sum on the RHS does not fit your inductive hypothesis, so it is not going to work.

The easiest way is to expand $(1-1)^n$ as suggested by Lulu in comments. However if you want an induction proof, the following will work.

I omit the basis step as you have done this yourself.

Suppose that $$\sum_{k=0}^n(-1)^k\binom nk=0\ .$$ Using the Pascal's triangle recurrence, $$\eqalign{ \sum_{k=0}^{n+1}(-1)^k\binom{n+1}k &=\sum_{k=0}^{n+1}(-1)^k\left[\binom nk+\binom n{k-1}\right]\cr &=\sum_{k=0}^{n+1}(-1)^k\binom nk +\sum_{k=0}^{n+1}(-1)^k\binom n{k-1}\ .\cr}$$ In the first sum the $k=n+1$ term is zero, so drop it: $$\sum_{k=0}^{n+1}(-1)^k\binom nk=\sum_{k=0}^n(-1)^k\binom nk\ .$$ In the second sum the $k=0$ term is zero, so drop it; then substitute $m=k-1$: $$\sum_{k=0}^{n+1}(-1)^k\binom n{k-1} =\sum_{k=1}^{n+1}(-1)^k\binom n{k-1} =\sum_{m=0}^n(-1)^{m+1}\binom nm\ .$$ Thus $$\eqalign{ \sum_{k=0}^{n+1}(-1)^k\binom{n+1}k &=\sum_{k=0}^n(-1)^k\binom nk+\sum_{m=0}^n(-1)^{m+1}\binom nm\cr &=\sum_{k=0}^n(-1)^k\binom nk-\sum_{m=0}^n(-1)^m\binom nm\cr &=0-0\cr &=0\ .\cr}$$

Answer 3

There's an easier way without using induction. Note that the expansion of $(1+(-1))^n$ is $\sum_{k=0}^{n}1^{n-k}(-1)^k\binom{n}{k}=\sum_{k=0}^{n}(-1)^k\binom{n}{k}$.

Then very simply $(1+(-1))^n=0$

Answer 4

$p(n)$ is the difference between the number of subsets of $\{1,2,\ldots,n\}$ with an even number of elements and the number of subsets with an odd number of elements. Any subset of $\{1,2\ldots,n\}$ is either of the even ($E$) kind or of the odd ($O$) kind, hence in order to prove that $p(n)=0$ it is enough to show that there is a bijection between $O$ and $E$.

Given $A\subseteq\{1,2,\ldots,n\}$, let $\varphi(A)=A\cup\{1\}$ if $1\not\in A$, and let $\varphi(A)=A\setminus\{1\}$ if $1\in A$.

I leave to you to prove that $\varphi$ is a bijection between $O$ and $E$.