Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

Using Binomial Theorem for positive integer exponent $n$

$$(a+b)^n=\sum_{0\le r\le n}\binom nr a^{n-r}b^r$$

Set $\displaystyle a=1,b=-1$ in the above identity

I think the easiest way to prove it is to think of a finite set of $n$ elements,

If you think of it that way, it's the number of even sized ($(-1)^k = 1$) subsets of $\{1,\,\dotsc,\,n\}$ minus the number of odd-sized ($(-1)^k = -1$) subsets.

The map

$$\varphi \colon S \mapsto \begin{cases} S\cup \{1\} &, 1 \notin S\\ S \setminus \{1\} &, 1 \in S \end{cases}$$

that "flips $1$", i.e. adds $1$ to $S$ if $1\notin S$ and removes it if $1\in S$, is a bijection between the set of even-sized and the set of odd-sized subsets. Thus $\{1,\, \dotsc,\,n\}$ has as many even-sized subsets as odd-sized, i.e.

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

for all $n \geqslant 1$.

Please allow me to give a less direct proof. Let $p$ be the product of $n$ different primes $q_1,\ldots,q_n$.

We know $$\sum_{d \mid p}\mu(d)=0,$$ where $\mu$ is the Möbius function.

Each divisor $d$ of $p$ is the product of primes from the set $\{q_1,\ldots,q_n\}$, and will satisfy $\mu(d)=1$ or $\mu(d)=-1$, depending on the parity of the number of primes dividing $d$.

It follows that there as many ways to choose an odd number of primes as ways to choose an even number of primes.

Equivalently, $$\sum_{0\leq 2k \leq n}\binom{n}{2k}=\sum_{0\leq 2k+1 \leq n}\binom{n}{2k+1},$$ it follows that $$\sum_{k=0}^n\binom{n}{k}(-1)^k=0.$$

Even though this question is pretty old, and the OP probably will not see the answer, I think it's worthwhile to provide a proof by induction, which the OP (and maybe others) had problems with and surprisingly no one has posted yet.

Since the statement is true for $n=1$, suppose it holds for $n=m$. Then the statement for $n=m+1$ follows from $$\require\cancel \sum_{k=0}^{m+1} (-1)^k {m+1 \choose k} =\sum_{k=0}^{m} (-1)^k {m \choose k} \\ \cancel{{m \choose 0}-{m+1 \choose 0}}+\sum_{k=1}^{m} (-1)^k {m \choose k}-(-1)^k{m+1 \choose k}-(-1)^{m+1}{m+1 \choose m+1}=0 \\ \sum_{k=1}^m (-1)^{k+1}\left({m+1 \choose k}-{m \choose k}\right)+(-1)^{m+2}{m+1 \choose m+1}=0,$$ which, recalling the property $\displaystyle {a \choose b}+{a \choose b+1}={a+1 \choose b+1},$ is equivalent to $$\sum_{k=1}^m (-1)^{k+1} {m \choose k-1}+(-1)^{m+2}{m+1 \choose m+1}=0 \\ \sum_{k=0}^{m-1} (-1)^{k} {m \choose k}+(-1)^{m}{m \choose m}=0 \\ \sum_{k=0}^{m} (-1)^k {m \choose k}=0,$$ and this is is precisely our inductive hypothesis.

As this question just got revived, I thought I'd add another bijective proof. Namely, we are trying to show that the number of subsets of $\{1,2,\dots,n\}$ with an odd number of elements is equal to the number of subsets with an even number of elements. To that end, given any subset $S$, just take the symmetric difference with $\{1\}$, i.e. $S\to S\triangle \{1\}$.