proving $ \binom{n}{0}-\binom{n}{1}+\binom{n}{2}+\cdots \cdots +(-1)^{n-1}\binom{n}{m-1}=(-1)^{m-1}\binom{n-1}{m-1}$

114 Views Asked by At

proving $\displaystyle \binom{n}{0}-\binom{n}{1}+\binom{n}{2}+\cdots \cdots +(-1)^{\color{red}{m}-1}\binom{n}{m-1}=(-1)^{m-1}\binom{n-1}{m-1}.$

$\displaystyle \Rightarrow 1-n+\frac{n(n-1)}{2}+\cdots \cdots (-1)^{n-1}\frac{n.(n-1)\cdot (n-2)\cdots(n-m+2)}{(m-1)!}$

Added

writting LHS as $\displaystyle \binom{n}{0}-\left(\binom{n-1}{0}+\binom{n-1}{1}\right)+\left(\binom{n-1}{1}+\binom{n-1}{2}\right)+\cdots \cdots +(-1)^{n-1}\left(\binom{n-1}{m-2}+\binom{n-1}{m-1}\right)=(-1)^{m-1}\binom{n-1}{m-1}.$

$\displaystyle \binom{n}{0}-\binom{n-1}{0}+\binom{n-1}{1}-\cdots +(-1)^{n-1}\binom{n-1}{m-2}-\left(\binom{n-1}{1}-\binom{n-1}{2}+\cdots +(-1)^n\binom{m-1}{m-1}\right)$

wan,t be able to solve after that, help me to solve it

2

There are 2 best solutions below

3
On BEST ANSWER

Extended HINT: The result is incorrect as originally stated; it should read

$$\binom{n}0-\binom{n}1+\binom{n}2-\ldots+(-1)^{\color{crimson}m-1}\binom{n}{m-1}=(-1)^{m-1}\binom{n-1}{m-1}\;,$$

or, more compactly,

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

Fix $n\in\Bbb N$. For $m=1$ the desired result is

$$\binom{n}0=(-1)^0\binom{n-1}0\;,$$

which is indeed true, since both sides are equal to $1$. Suppose as an induction hypothesis that $(1)$ holds for some $m$; for the induction step we want to prove that

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

Using the induction hypothesis we can rewrite the lefthand side of $(2)$:

$$\sum_{k=0}^m(-1)^k\binom{n}k=(-1)^m\binom{n}m+\sum_{k=0}^{m-1}(-1)^k\binom{n}k=(-1)^m\binom{n}m+(-1)^{m-1}\binom{n-1}{m-1}\;,$$

so to complete the induction step we need only show that

$$(-1)^m\binom{n}m+(-1)^{m-1}\binom{n-1}{m-1}=(-1)^m\binom{n-1}m\;.$$

This is easily done using one of the most basic identities involving binomial coefficients.

Added: After some thought I realize that $(1)$ can be proved by direct calculation:

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

0
On

HINT: Fix a random $n$ and do induction on $m$.