# Proof by induction that alternating sum of binomial coefficients is $0$ [duplicate]

$\forall n \in \mathbb N :$ $A(n): \sum_{k=0}^n \binom{n}{k} \cdot(-1)^k = 0$

Initial step: $A(1): \binom{1}{0}\cdot(-1)^0 \binom{1}{1}\cdot(-1)^1 = 0$ $\iff 1 = 1$ $\iff 0 = 0$

The initial step turned out to be correct.

Induction hypothesis: So, if I pick an arbitrary natural number number l, and if I assume that A(l) is valid, then A(l+1) have to be likewise valid:

$A(l): \sum_{k=0}^l \binom{l}{k}\cdot (-1)^k = 0$

Induction step: $A(l+1): \sum_{k=0}^{l+1} \binom{l+1}{k}\cdot(-1)^k = 0$

$\iff \binom{l+1}{0}\cdot(-1)^0+ \binom{l+1}{1}\cdot(-1)^1+...+ \binom{l+1}{l}\cdot(-1)^{l}+ \binom{l+1}{l+1}\cdot(-1)^{l+1}= 0$

My problem are these binomial coefficients. I also tried to replace every coefficient with its formula $n! \over {k!*(n-k)!}$ and tried to rearrange it, but I could not proof it yet.

• Why don't you use the binomial development of the sum $(1+(-1))^n =0$? Nov 5 '13 at 14:25

Since $${1\choose 0}(-1)^0+{1\choose 1}(-1)^1=0$$ the statement is true for $n=1$. Assume that $\sum_{k=0}^l {l\choose k}(-1)^k=0$ for an arbitrary positive integer $l$. We show that $$\sum_{k=0}^{l+1}{l+1\choose k}(-1)^k=0.$$ Consider $$\sum_{k=0}^{l+1}{l+1\choose k}(-1)^k.$$ We know that ${l+1\choose k}={l\choose k}+{l\choose k-1}$. So $$\sum_{k=0}^{l+1}{l+1\choose k}(-1)^k=\sum_{k=0}^{l+1}({l\choose k}+{l\choose k-1})(-1)^k.$$ Distributing the right-hand side we obtain $$\sum_{k+0}^{l+1}{l\choose k}(-1)^k+\sum_{k=0}^{l+1}{l\choose k-1}(-1)^k.$$ Rewriting the left side term and manipulating the index on the right side term we see that $$\sum_{k=0}^l{l\choose k}(-1)^k+{l\choose l+1}(-1)^{l+1}+\sum_{k=1}^{l+1}{l\choose k-1}(-1)^k.$$ Shift the index on the last term and notice that ${l\choose l+1}(-1)^{l+1}=0$ to obtain $$\sum_{k=0}^l{l\choose k}(-1)^k+\sum_{k=0}^{l}{l\choose k}(-1)^{k+1}.$$ So $$\sum_{k=0}^l{l\choose k}(-1)^k-\sum_{k=0}^{l}{l\choose k}(-1)^{k}=0$$ by the induction hypothesis. Thus by the Principle of Mathematical Induction $\sum_{k=0}^n{n\choose k}(-1)^k=0$ for all $n\in\mathbb{N}$.

$$A(n) = \sum_{k=0}^n \binom nk (-1)^k = \sum_{k=0}^n \binom nk (-1)^k (1)^{n-k} = (-1 + 1)^n = 0^n \stackrel{n>0}= 0$$ If you want to stick with induction, use $$\binom {n+1}k = \frac{(n+1)!}{(n+1-k)!k!} = \frac{n+1}{n-k+1} \frac{n!}{(n-k)!k!} = \frac{n+1}{n-k+1} \binom nk$$

• Not sure how your second equation leads to an inductive proof. The $n-k+1$ in the denominator doesn't easily go away, does it? Jul 26 '19 at 18:28

You don’t need induction to prove this, but induction is a perfectly feasible way to do so. For your induction step you’ll want the Pascal’s triangle identity,

$$\binom{n+1}k=\binom{n}k+\binom{n}{k-1}\;.$$

You’ll also want to remember that $\binom{n}k=0$ if $k>n$ or $k<0$. Your induction step can start like this:

\begin{align*} \sum_{k=0}^{n+1}\binom{n+1}k(-1)^k&=\sum_{k=0}^{n+1}\left(\binom{n}k+\binom{n}{k-1}\right)(-1)^k\\\\ &=\sum_{k=0}^{n+1}\binom{n}k(-1)^k+\sum_{k=0}^{n+1}\binom{n}{k-1}(-1)^k \end{align*}

Can you finish it from there?

Induction on $n$ turns out to be a rather inappropriate method for this problem. Why? For one thing because the statement is false for $n=0$, namely $\sum_{k=0}^0\binom0k(-1)^k=\binom00(-1)^0=1\neq0$, so $A(0)$ fails. Not a good start for induction, if you consider $0\in\Bbb N$ (as I do). But as you computed in the question $A(1)$ is true, so somehow you don't need to have $A(n)$ to get $A(n+1)$ when $n=0$. But this does not mean that induction cannot work, as it requires truth of a statement to be hereditary, not falsehood.

Let us try induction, can call $S(n)$ the sums for $n$, so the statement to prove is $S(n)=0$ for all $n\geq1$ (we better forget about the uncooperative $n=0$). Induction calls for Pascal's recurrence, so we compute \begin{align} S(n+1)=\sum_{k\geq0}\binom{n+1}k(-1)^k &=1+\sum_{k\geq1}(\tbinom nk+\tbinom n{k-1})(-1)^k\\ &=\sum_{k\geq0}\tbinom nk(-1)^k+\sum_{l\geq0}\tbinom nl(-1)^{l+1} =S(n)-S(n). \end{align} Now you can invoke the induction hypothesis $S(n)=0$ to show that the resulting value equals$~0$, but frankly there is no pressing need to do so other than the imperative in the title of this question. So we get $S(n+1)=0$ regardless of what $S(n)$ happened to be. This explains the recovery from a false start.

If you must prove this using induction, why not extend the statement to cover other partial sums? Experimenting a bit tells you that the statement to prove ought to be $\sum_{k=0}^m\binom nk(-1)^k=(-1)^m\binom{n-1}m$. The obvious induction to try is on $m$, and for $m=0$ one gets $\binom n0=\binom{n-1}0$ which is OK for all $n$ (even for $n=0$), so this time we are off with a good start. Assuming the result for $m$ one gets \begin{align} \sum_{k=0}^{m+1}\tbinom nk(-1)^k &=(-1)^m\tbinom{n-1}m+(-1)^{m+1}\tbinom n{m+1}\\ &=(-1)^{m+1}(\tbinom n{m+1}-\tbinom{n-1}m)=(-1)^{m+1}\tbinom{n-1}{m+1} \end{align} as desired. Since $\binom{n-1}n=0$ for $n>0$, you get your $A(n)$ for $n>0$ as the special case $m=n$.