Prove the binomial identity ∑(-1)^j(n choose j)=0

[lfdahl]

Prove the binomial identity:

$$\sum_{j=0}^{n}(-1)^j{n \choose j}=0$$

- in two different ways

 

[topsquark]

Prove the binomial identity:

$$\sum_{j=0}^{n}(-1)^j{n \choose j}=0$$

- in two different ways

The only way I can think of is to do an induction proof. I haven't sat down to do it but it shouldn't be too hard.

-Dan

(Ahem!) I thought you were asking for help. When I saw it was a challenge I couldn't edit it out. (I thought it was a rather easy problem for you to be asking for help on.) Anyway, if someone else doesn't post it I'll get back to it later.

 

[Olinguito]

Spoiler

First method.

When $n$ is odd, it’s easy. The coefficients $\displaystyle\binom nj$ and $\displaystyle\binom n{n-j}$ from $j=0$ to $j=n$ pair up nicely; also $(-1)^{n-j}=(-1)^n(-1)^j=-(-1)^j$ (as $n$ is odd). Thus
$$\sum_{j=0}^n(-1)^j\binom nj$$

$\displaystyle=\ \sum_{j=0}^{\frac{n-1}2}\left[(-1)^j\binom nj + (-1)^{n-j}\binom n{n-j}\right]$

$\displaystyle=\ \sum_{j=0}^{\frac{n-1}2}\left[(-1)^j\binom nj - (-1)^j\binom n{n-j}\right]$

$=\ 0$.

Suppose $n$ is even, so $(-1)^n=1$ and $(-1)^{n-1}=-1$. We use the well-known identity
$$\binom nj\ =\ \binom{n-1}{j-1}+\binom{n-1}j$$
(which is simply saying that a binomial coefficient is the sum of the two coefficients above it in Pascal’s triangle). Then
$$\sum_{j=0}^n(-1)^j\binom nj$$

$\displaystyle=\ 1\,+\,\sum_{j=1}^{n-1}\left[(-1)^j\binom{n-1}{j-1} + (-1)^j\binom {n-1}j\right]\,+\,(-1)^n$

$\displaystyle=\ 1\,+\,\sum_{j=1}^{n-1}\left[-(-1)^{j-1}\binom{n-1}{j-1} + (-1)^j\binom {n-1}j\right]\,+\,1$

$\displaystyle=\ 1\,+\,\left[-(-1)^0\binom{n-1}0+(-1)^{n-1}\binom{n-1}{n-1}\right]\,+\,1$ (by telescoping)

$=\ 1+[(-1)+(-1)]+1$

$=\ 0$.Second method.

Expand $0=[1+(-1)]^n$ binomially.

 

[lfdahl]

Thankyou very much, Olinguito, for your participation and two nice approaches! (Yes)