Proving $\sum_{i=1}^{n} {{n}\choose{i}} (-1)^i = -1$ by induction

Question

I would like to prove this $$\sum_{i=1}^{n} {{n}\choose{i}} (-1)^i = -1$$ for all $n \in \mathbb{N} $.

I started by replacing consecutively $n$ by $1, 2, 3$, one at a time, and verified that all of these indeed equal $-1$. However, I would like to prove it for all $i$, therefore I tried to do it by Mathematical Induction but failed somewhere. Below is my rationale.

$ n=1 \Rightarrow \sum_{i=1}^{n} {{n}\choose{i}} (-1)^i = \sum_{i=1}^{1} {{1}\choose{i}} (-1)^i = {{1}\choose{1}} (-1)^1 = 1 \times (-1) = -1$

$$\sum_{i=1}^{n+1} {{n+1}\choose{i}} (-1)^i \\= \sum_{i=1}^{n} {{n+1}\choose{i}} (-1)^i + \sum_{i=n+1}^{n+1} {{n+1}\choose{i}} (-1)^i \\ = \sum_{i=1}^{n} {{n+1}\choose{i}} (-1)^i + {{n+1}\choose{n+1}} (-1)^{n+1}\\ = \sum_{i=1}^{n} \space [{{n}\choose{i-1}} + {{n}\choose{i}}] (-1)^i + {{n+1}\choose{n+1}} (-1)^{n+1} \\ = \sum_{i=1}^{n} \space {{n}\choose{i-1}} (-1)^i + \sum_{i=1}^{n}{{n}\choose{i}} (-1)^i + {{n+1}\choose{n+1}} (-1)^{n+1} = $$

Given the induction hypothesis, $\sum_{i=1}^{n} {{n}\choose{i}} (-1)^i = -1 $, hence we have

$ \sum_{i=1}^{n} \space {{n}\choose{i-1}} (-1)^i - 1 + (-1)^{n+1} = $

Now the way I see this is that $\sum_{i=1}^{n} \space {{n}\choose{i-1}} (-1)^i$ is similar to $\sum_{i=1}^{n}{{n}\choose{i}} (-1)^i $, but instead of having all the Pascal triangle terms except the term in ${n}\choose{0}$, we end up having all elements except the term in ${n}\choose{n}$. This is why I wrote the previous equation as equal to

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

$ -1 + 1 - {{n}\choose{n}} (-1)^n - 1 + (-1)^{n+1} = - (-1)^n - 1 + (-1)^{n+1} = -1 + (-1)^{n+1} + (-1)^{n+1} = $

$ = -1 + 2 \times (-1)^{n+1} $

You see there is a problem in this resolution, because, depending on whether n is odd or even, the final result of this sum will differ. If $n$ is odd, $n+1$ is even, hence we have $-1 + 2 \times 1 = 1$. If $n$ is even, then $n+1$ is odd, hence we have $-1 + 2 \times (-1) = -3$ !

I did this resolution over and over, but I did not find the hole in my logic. Please help.

Thank you.

Answer 1

There's a slight mistake. Before talking about it, well done for your work! Also, as shown in another answer, there's a much easier way to prove this formula.

To answer your question, the problem is when you did this:

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

You're idea of changing how the sum looks is great! It's just that, one thing you missed, is that you kind of do a change of variable there $i-1\to i$. You see:

$$\sum_{i=1}^n\binom{n}{i-1}(-1)^i=\binom{n}{0}(-1)^1+\color{blue}{\binom{n}{1}(-1)^2}+\dots+\color{limegreen}{\binom{n}{n-1}(-1)^n}$$

whereas

$$\sum_{i=1}^n\binom{n}{i}(-1)^i=\color{blue}{\binom{n}{1}(-1)^1}+\dots+\color{limegreen}{\binom{n}{n-1}(-1)^{n-1}}+\binom{n}{n}(-1)^n.$$

You see that the terms that have the same binomial value do not have the same power for the $(-1)$. Here's a way to do things properly:

\begin{align*} \sum_{i=1}^n\binom{n}{i-1}(-1)^i&=\sum_{i=0}^{n-1}\binom{n}{i}(-1)^{i+1}&\text{(if you replace $i-1$ by $i$, you replace $i$ by $i+1$)}\\ &=\binom{n}{0}(-1)^1-\sum_{i=1}^{n-1}\binom{n}{i}(-1)^i&\text{(because $(-1)^{i+1}=-(-1)^i)$}\\ &=-1-\sum_{i=1}^n\binom{n}{i}(-1)^i+\binom{n}{n}(-1)^n. \end{align*}

Answer 2

If you just want to prove the equality, you have a much simpler proof :

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

Answer 3

Here is the very detailed solution: $$\sum_{i=1}^{n} \space {{n}\choose{i-1}} (-1)^i + \sum_{i=1}^{n}{{n}\choose{i}} (-1)^i + {{n+1}\choose{n+1}} (-1)^{n+1} =\\ \left[(-1)^1\sum_{i=1}^{n} \space {{n}\choose{i-1}} (-1)^{i-1}\right] + (-1) + (-1)^{n+1} =\\ \left[(-1)^1{n\choose 0}+(-1)^1\sum_{i=2}^{n} \space {{n}\choose{i-1}} (-1)^{i-1}\right] + (-1) + (-1)^{n+1} =\\ \left[-1+(-1)^1\sum_{i=2}^{n} \space {{n}\choose{i-1}} (-1)^{i-1}+(-1)^1{n\choose n}(-1)^n-(-1)^1{n\choose n}(-1)^n\right] + (-1) + (-1)^{n+1} =\\ \left[-1+(-1)^1\sum_{i=1}^{n} \space {{n}\choose{i}} (-1)^{i}-(-1)^1{n\choose n}(-1)^n\right] + (-1) + (-1)^{n+1} =\\ \left[-1+(-1)^1(-1)-(-1)^1{n\choose n}(-1)^n\right] + (-1) + (-1)^{n+1} =\\ [-1+1-(-1)^{n+1}]-1+(-1)^{n+1}=-1.$$

Answer 4

\begin{align} \sum_{i=1}^n\binom{n}i(-1)^i &=\sum_{i=1}^n\left[\binom{n-1}{i}+\binom{n-1}{i-1}\right](-1)^i \\&=\sum_{i=1}^n\left[\binom{n-1}{i}(-1)^i-\binom{n-1}{i-1}(-1)^{i-1} \right]\end{align} The last summation is telescoping. To see this, let $a_i=\binom{n-1}i(-1)^i$, and note the last sum is $\sum_{i=1}^n(a_i-a_{i-1}). $ The value of this sum is therefore $$a_n-a_0=\binom{n-1}n(-1)^n-\binom{n-1}0(-1)^0=0-1=-1.$$ More generally, $$ \sum_{i=p}^q\binom{n}i(-1)^i=\binom{n-1}q(-1)^q-\binom{n-1}{p-1}(-1)^{p-1}. $$