Deriving an equation for the Sum of Alternating Combinations

Question

Consider the equation $$A(n,m) = \sum_{i = 0}^m (-1)^i {n \choose i}$$

To get a feel for it, I let $n=5$ and $m \in \{1,2,...,5\}$

for $m=1$ $$A(5,1) = (-1)^0 {5 \choose 0} - {5 \choose 1} = 1 - 5 = -4$$

for $m=2$, $$A(5,2) = A(5,1) + {5 \choose 2} = -4 + 10 = 6$$

for $m=3$, $$A(5,3) = A(5,2) - {5 \choose 3} = 6 - 10 = -4$$

for $m=4$, $$A(5,4) = A(5,3) + {5 \choose 4} = -4 + 5 = 1$$

for $m=5$, $$A(5,5) = A(5,4) + {5 \choose 5} = 1 - 1 = 0$$

Now This pattern also suggests that for any $k \geq 1$ then we have $A(k,k)= 0$

Now I am required to find a simpler equation for $A(n,m)$, But I am not able to come up with it , Any suggestions ?

Answer 1

You’ve come up with the correct conjecture that

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

Proving it by induction on $m$ is a pretty straightforward application of Pascal’s identity. Alternatively, you could start with the given summation and tinker with it by applying Pascal’s identity to see what happens:

$$\begin{align*} \sum_{i=0}^m(-1)^i\binom{n}i&=\sum_{i=0}^m(-1)^i\left(\binom{n-1}i+\binom{n-1}{i-1}\right)\\ &=\sum_{i=0}^m(-1)^i\binom{n-1}i+\sum_{i=0}^m(-1)^i\binom{n-1}{i-1}\;. \end{align*}$$

At this point the natural thing to do is to adjust the index of summation in the second sum so that both binomial coefficients are $\binom{n-1}i$; if you do that correctly, you’ll find that everything cancels out except one term in one of the sums.

Answer 2

Using the binomial identities: Negating the upper index $\binom{n}{i}=(-)^i\binom{i-n-1}{i}$ and parallel sumation $\sum_{k=0}^{n}\binom{m+k}{k}=\binom{n+m+1}{n}$ we get : $$ \eqalign{ \sum_{i=0}^{m}(-)^i\binom{n}{i} &= \sum_{i=0}^{m}(-)^i(-)^i\binom{i-n-1}{i} \cr &= \sum_{i=0}^{m}\binom{i-n-1}{i} = \binom{m-n}{m} \cr &= (-)^m\binom{m-m+n-1}{m} = (-)^m\binom{n-1}{m} \cr } $$