MHB Prove sum of (-1)^i times n choose i equals 0

[Jameson]

Problem: Prove that for $n>0$, [math]\sum_{i=0}^{n} (-1)^i \binom{n}{i}=0[/math]

Attempt: This seems clearly like a proof based on induction.

1) Base case: for $n=1$, [math]\sum_{i=0}^{1}(-1)^i \binom{1}{i}=(-1)^0 \binom{1}{0}+(-1)^1 \binom{1}{1}=1-1=0[/math]

2) Show that $n=k$ being valid implies $n=k+1$ is valid. Assume that [math]\sum_{i=0}^{k} (-1)^i \binom{k}{i}=0[/math]. Now I need to show that [math]\sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i}=0[/math]?

Am I right so far? The hint I'm given is to use the binomial theorem but there is something I'm missing about showing this is true. Can someone give me a small push (not the full proof please)?

 

[MarkFL]

I would in fact use the binomial theorem here.

$\displaystyle 0=(1-1)^n=?$

 

[chisigma]

Problem: Prove that for $n>0$, [math]\sum_{i=0}^{n} (-1)^i \binom{n}{i}=0[/math]

Attempt: This seems clearly like a proof based on induction.

1) Base case: for $n=1$, [math]\sum_{i=0}^{1}(-1)^i \binom{1}{i}=(-1)^0 \binom{1}{0}+(-1)^1 \binom{1}{1}=1-1=0[/math]

2) Show that $n=k$ being valid implies $n=k+1$ is valid. Assume that [math]\sum_{i=0}^{k} (-1)^i \binom{k}{i}=0[/math]. Now I need to show that [math]\sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i}=0[/math]?

Am I right so far? The hint I'm given is to use the binomial theorem but there is something I'm missing about showing this is true. Can someone give me a small push (not the full proof please)?

I'm not sure to have correctly undestood the question but the identity $\displaystyle \sum_{i=0}^{k+1} (-1)^i \binom{k+1}{i}=0$ can be easily verified remembering the binomial sum...

$\displaystyle (1+x)^{n} = \sum_{i=0}^{n} \binom{n}{i}\ x^{i}$ (1)

... and setting in (1) x=-1 and n=k+1...

Kind regards

$\chi$ $\sigma$

 

[Jameson]

I would in fact use the binomial theorem here.

$\displaystyle 0=(1-1)^n=?$

The $(-1)^i$ term is the one that is throwing me off. You stated looking at 0, so maybe I can rewrite 0 in terms of the binomial theorem and show that's it's equal to the left hand side?

I'll write the expansion of $(1-1)^n$ by the binomial theorem.

[math](1-1)^n=\sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^k=\binom{n}{0}1^{1}(-1)^0+\binom{n}{1}(1)^2 (-1)^1+...[/math]

Ok, I didn't finish writing out the expansion but it looks like the terms will all cancel by symmetry. The first term is 1 and the second term is $n$, so I believe the last term will be -1 and the second to last will be $-n$.

EDIT: Ok, I think I see it now. $1^{n-k}=1$ for all $k$ and $n$, so it's not necessary to write that at all any more and what's left is [math]\binom{n}{k}(-1)^k[/math].

Now the only question remains is how to apply the same argument to when we are looking $k+1$.

 

[MarkFL]

I wouldn't use induction at all here, I would simply write:

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

 

[Jameson]

I think that will suffice as well, however I wonder if it's "rigorous" enough. The class I'm taking is not proof based at all but I want to get on his good side by going above and beyond. I think this is the proof he's looking for. Perhaps not every proof that can be done through induction needs to be.

 

[Fantini]

I'd say this is rigorous enough. There is no handwaving at any point of the argument, therefore you look good to go. (Yes)

 

[Sherlock1]

Call our sum $S$. Pascal's rule states that $\displaystyle {k\choose i} = {k-1\choose i} + {k-1\choose i-1}$, therefore

$\displaystyle S = \sum_{i=0}^{k}{k-1\choose i}(-1)^i + \sum_{i=0}^{k} {k-1\choose i-1} (-1)^i$, putting $i \mapsto i-1$ for the first one:

$$\begin{aligned} S & = \sum_{i=1}^{k+1}{k-1\choose i-1}(-1)^{i-1} + \sum_{i=0}^{k} {k-1\choose i-1} (-1)^i \\& =- \sum_{i=0}^{k}{k-1\choose i-1}(-1)^i + \sum_{i=0}^{k} {k-1\choose i-1} (-1)^i \\& = 0. \end{aligned}$$.

 

[Deveno]

pascal's triangle is symmetric. this takes care of the odd (that is for odd n) rows (which have an even number of entries).

for the even rows, note that each "middle" descendant is the result of the sum of a pair of the odd row above, that is:

$\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

so:

$\displaystyle -\binom{n}{k} + \binom{n}{k+1} = -\binom{n-1}{k-1} - \binom{n-1}{k} + \binom{n-1}{k} + \binom{n-1}{k+1} = -\binom{n-1}{k-1} + \binom{n-1}{k+1}$

and:

$\displaystyle -\binom{n}{k} + \binom{n}{k+1} - \binom{n}{k+2} = -\binom{n-1}{k-1} - \binom{n-1}{k+2}$

if we go "one more term" (assuming we have that many), we have:

$\displaystyle -\binom{n}{k} + \binom{n}{k+1} - \binom{n}{k+2} + \binom{n}{k+3} =$

$\displaystyle -\binom{n-1}{k-1} + \binom{n-1}{k+3}$

where i am going with this is:

$\displaystyle \sum_{i = 1}^{j+1} (-1)^i \binom{n}{k+i-1} = -\binom{n-1}{k-1} + (-1)^{j+1} \binom{n-1}{k+j}$

(this is sort of like a telescoping sum).

if we change this around a bit, and let k = 1, and j = n-2, we get:

$\displaystyle \sum_{i=1}^{n-1} (-1)^i \binom{n}{i} = -\binom{n-1}{0} - \binom{n-1}{n-1} = -1 -1 = -2$.

thus:

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

(this may well be what Sherlock had in mind, but i think he wasn't careful with his indices...on the row above we don't have as many "terms" as we do on the row below).

(EDIT: if one looks closely, you can see how there's an induction proof concealed in this, based on 2 cases: even n, and odd n).

(EDIT #2: i have to say that MarkFL's and chisigma's proofs are very elegant. my proof is by comparison, "uglier", but has the advantage of using no other results ("elementary" proofs are often more difficult to understand than 'high-level ones"), except the recursive definition of the binomial coefficient (one does not even need to know that:

$\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$

just how to make a pascal's triangle, by summing two adjacent row-elements and putting the result "in-between" on the next row...everything "outside the triangle" is all 0's). so in that sense my proof is "stronger" since it assumes less. on a deeper level, pascal's triangle encodes the distributive law of the natural numbers, and the symmetry across the center encodes the commutativity of multiplication. it never ceases to amaze me how algebraic rules have such elegant expression as geometric patterns. i suspect much of what we think of as "modern" was actually known in antiquity, just understood differently).

 

[Jameson]

Thank you MarkFL, chisigma, Fantini, Sherlock and Deveno!

I will have to take some time to read and process the last two posts, but I am very interested to see all the ways this can be approached. :)

 

[Sherlock1]

(this may well be what Sherlock had in mind, but i think he wasn't careful with his indices...on the row above we don't have as many "terms" as we do on the row below).

I've rechecked my steps and what I've written seems perfectly fine.

Can you please point to where you exactly think there's a problem? :)

 

[awkward]

You have already seen some good proofs, but here is a different approach just for the sake of variety.

$$ \sum_{i=0}^n (-1)^i \binom{n}{i} = \sum_{i \; even} \binom{n}{i} - \sum_{i \; odd} \binom{n}{i} $$

so the desired result is equivalent to showing that the number of subsets of $\{1, 2, 3, \dots ,n\}$ with an even number of elements is equal to the number of subsets with an odd number of elements. We will show this by establishing a bijection between the subsets of even and odd size.

Suppose $E$ is a subset of $\{1, 2, 3, \dots ,n\}$. If 1 is an element of $E$, we pair $E$ with $E \setminus \{1\}$; if 1 is not an element of $E$, we pair E with $E \cup \{1\}$. In either case, one of the pair has an even number of elements and the other has an odd number of elements. This establishes the desired bijection, so there are equal numbers of even-sized and odd-sized subsets.

 

[Sherlock1]

I need to learn combinatorics. Combinatorial proofs come off as elegant and more informative than algebraic ones.

 

[Deveno]

I've rechecked my steps and what I've written seems perfectly fine.

Can you please point to where you exactly think there's a problem? :)

i've high-lighted what i think are troublesome parts in red.

Call our sum $S$. Pascal's rule states that $\displaystyle {k\choose i} = {k-1\choose i} + {k-1\choose i-1}$, therefore

$\displaystyle S = \sum_{i=0}^{\color{red}{k}}{k-1\choose i}(-1)^i + \sum_{i=\color{red}{0}}^{\color{red}{k}} {k-1\choose \color{red}{i-1}} (-1)^i$, putting $i \mapsto i-1$ for the first one:

$$\begin{aligned} S & = \sum_{i=1}^{\color{red}{k+1}}{k-1\choose i-1}(-1)^{i-1} + \sum_{i=\color{red}{0}}^{\color{red}{k}} {k-1\choose \color{red}{i-1}} (-1)^i \\& =- \sum_{i=\color{red}{0}}^{k}{k-1\choose \color{red}{i-1}}(-1)^i + \sum_{i=\color{red}{0}}^{k} {k-1\choose \color{red}{i-1}} (-1)^i \\& = 0. \end{aligned}$$.

i am having some trouble deciding what:

$\displaystyle \binom{k-1}{-1}$ and $\displaystyle \binom{k-1}{k}$ should be. care to elaborate?

 

[Sherlock1]

i've high-lighted what i think are troublesome parts in red.
i am having some trouble deciding what:

$\displaystyle \binom{k-1}{-1}$ and $\displaystyle \binom{k-1}{k}$ should be. care to elaborate?

$\displaystyle \binom{r}{k} = \left \{\begin{array}{cc} \frac{r(r-1)\cdots(r-k+1)}{k(k-1)\cdots 1} = \frac{r^{\underline{k}}}{k!}, &\mbox{ integer } & k \ge 0; \\0, & \mbox{integer} & k < 0\\
\end{array} \right.$

Where $r \in\mathbb{C}$. So $\displaystyle \binom{k-1}{-1} = 0$ and likewise $\displaystyle \binom{k-1}{k} = 0.$

 

[Deveno]

well, that clears that up a bit. it's a little unusual, because you are including terms outside the range of the given summation (of the next row up), but since these terms are zero, i don't see the harm. basically, "everything outside the triangle is 0" (ignoring, for the purposes of THIS discussion, the fact that we can define binomial coefficients for non-integers, since we don't need them for this problem).

i am still puzzled by one thing, however. in the penultimate line you have:

$$\begin{aligned} S & = \sum_{i=1}^{k+1}{k-1\choose i-1}(-1)^{i-1} + \sum_{i=0}^{k} {k-1\choose i-1} (-1)^i \\& =- \sum_{i=0}^{k}{k-1\choose i-1}(-1)^i + \sum_{i=0}^{k} {k-1\choose i-1} (-1)^i \\& = 0. \end{aligned}$$

i don't see how you get the first summation of the second line from the first line.

here is my thinking:

suppose we are just considering the alternating sum of the 2nd row of pascal's triangle, corresponding to the binomial expansion of a square, that is k = 2. explicitly, this is:

$\displaystyle 1 - 2 + 1 = (-1)^0\binom{2}{0} + (-1)^1\binom{2}{1} + (-1)^2\binom{2}{2}$.

now you're saying we can write:

$\displaystyle\binom{2}{0} = \binom{1}{0} + \binom{1}{-1}$
$\displaystyle\binom{2}{1} = \binom{1}{1} + \binom{1}{0}$
$\displaystyle\binom{2}{2} = \binom{1}{2} + \binom{1}{1}$

so far, so good, and i even agree that your change of index is kosher (the index is just a dummy variable, anyway).

so for $k = 2$, what you have above, translates to:

$\displaystyle S = \left[\binom{1}{0} - \binom{1}{1} + \binom{1}{2}\right] + \left[\binom{1}{-1} - \binom{1}{0} + \binom{1}{1}\right]$.

but we don't have the same terms in the different brackets (the cancellation isn't first-to-first, second-to-second, etc. but "book-matched" inside to out).

it seems like an index mis-match, but perhaps I'm just being dense.

EDIT: i think i see what you did, now...you took a 0-term "off the top" and "put it on the bottom". that makes sense.

 

[Sherlock1]

i think i see what you did, now...you took a 0-term "off the top" and "put it on the bottom".

Yes. (Rofl)

It can be motivated this way. Basically we want the indexes to match as the first ranges over $[1,~ k+1]$ but the second ranges over $[0, ~k]$. So we range the first over $[0, ~1]$ and subtract the term at $i = 0$ and add the term at $i = k+1$. The fact that in this case both of these terms happen to be zero makes it seem bit unintuitive, but usually when you use the shift $i \mapsto i-\ell$ the hanging terms aren't zero. For example, when deriving formulas for geometric and arithmetic series (both of which can be done with the same one-unit shift $i \mapsto i-1$ that we have used).