Prove this sum equal to an expression. QUESTION: 
Prove that for all positive integers 
$k\leq n$:
$\sum_{i=0}^{k}{n \choose i} (-1)^i = {n-1 \choose k}(-1)^k$
MY THOUGHTS:
INDUCTION : (assuming k even) - We assume:
${n \choose 0} - {n \choose 1} + ... + {n \choose k-2} - {n \choose k-1} = {n-1 \choose k-1}$
We need to show:
${n \choose 0} - {n \choose 1} + ...-{n \choose k-1} + {n \choose k} = {n-1 \choose k-1}$
My issue here is that we can say LHS equals ${n-1 \choose k-1} + {n \choose k}$, which is close, but not quite Pascal's Rule. 
Another way:
I thought looking to find some bijection that can be applied. 
Let's assume n is even. Writing out the left and sum and moving all the odd (negative) terms to the RHS gives (note that the last term on the RHS is simply the original RHS:
${n \choose 0} + {n \choose 2} + ... + {n \choose k} = {n \choose 1} + {n \choose 3} + ... + {n \choose k-1} + {n-1 \choose k}$  
I am stuck here, but how I worked out in my mind was that:
$\bigg\{$set of even sized groups of 
$\leq$
n people$\bigg\}$ --> 
$\bigg\{$set of odd sized groups of 
$\leq$
n-1 people$\bigg\}$ + ${n-1 \choose k}$
Then possibly, it would have something to do with adding or removing person n. Let me know your thoughts or suggestions.
 A: There is really nothing to worry about the left hand side only really contains two variables $k$ & $n$. The variable $i$ is referred to as a dummy variable & could have been anything.
Now you are happy that 
\begin{eqnarray*}
\binom{n-1}{k}+\binom{n-1}{k+1}=\binom{n}{k+1}.
\end{eqnarray*}
Rearrange this to 
\begin{eqnarray*}
\binom{n-1}{k}-\binom{n}{k+1}=\binom{n-1}{k+1}
\end{eqnarray*}
& now the induction is easy ...
\begin{eqnarray*}
\sum_{i=0}^{k+1} (-1)^k \binom{n}{k}=(\sum_{i=0}^{k} (-1)^k \binom{n}{k})+ (-1)^{k+1}\binom{n}{k+1}
\end{eqnarray*}
Now use the inductive hypothesis on the sum in the bracket & then use the equation rearranged above & you are there.
A: This problem is worked in as equation (5.15) in Concrete Mathematics.
The idea is to use the formula for negating the upper index in a binomial coefficient:
$$
\binom{i-r-1}{i} = (-1)^i\binom{r}{i}
$$
To prove this, some notation will be useful: Let $r^\underline{i}$, with $i$ a non-negative integer and $r$ any real number, stand for the descending product of $i$ terms
$$
r^\underline{0}=1\\
r^\underline{i} = r(r-1)r-2)\cdots (r-i+1)\\
\binom{r}{i} = \frac{r^\underline{i}}{i!}
$$
Then by negating each of the $i$ terms in the product that makes up $r^\underline{i}$ we obtain
$$
r^\underline{i} = (-1)^i (-r) (1-r) (2-r) \cdots (i-1-r) =
(-1)^i (i-1-r)^\underline{i}
$$
and so
$$
(-1)^i\binom{r}{i} = (-1)^i\frac{r^\underline{i}}{i!}=  (-1)^i (-1)^i\frac{(i-1-r)^\underline{i}}{i!} = \binom{i-r-1}{i}
$$
We also will use the formula that for non-negative integer $k$ (and integer summation index $i$) 
$$
\sum_{i\leq k} \binom{r+i}{i} = \binom{r+k+1}{k}
$$
This has (at least for integer $r$) a simple combinatorial interpretation:  
If I want to choose $b$ items from a collection of $k+(r+1)$ items, I can choose all $r$ from the first $k+r$ items (and not select the last item, or I can choose the last item and $r-1$ out of the first  $k+r-1$ items, or I can choose the last two items and $r-1$ out of the first  $k+r-2$ items, and so forth.
So we have 
$$\sum_{i\leq k} (-1)^i\binom{r}{i}
=\sum_{i\leq k} \binom{i-r-1}{r} 
=\sum_{i\leq k} \binom{(-r-1)+i}{i}
= \binom{(-r-1)+k+1}{k} = \binom{k-r}{k}\\ 
\binom{k-(r-1)-1}{k}=(-1)^k \binom{r-1}{k}
$$
Replacing $r$ by $n$ we have the desired relation.
A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With $\ds{\verts{z} < 1}$:

\begin{align}
\sum_{i = 0}^{k}{n \choose i}\pars{-1}^{\,i} & =
\bracks{z^{k}}\sum_{\ell = 0}^{\infty}z^{\ell}
\bracks{\sum_{i = 0}^{\ell}{n \choose i}\pars{-1}^{\,i}} =
\bracks{z^{k}}\sum_{i = 0}^{\infty}{n \choose i}\pars{-1}^{\,i}
\sum_{\ell = i}^{\infty}z^{\ell}
\\[5mm] & =
\bracks{z^{k}}\sum_{i = 0}^{\infty}{n \choose i}\pars{-1}^{\,i}\,
\pars{z^{i} \over 1 - z} =
\bracks{z^{k}}{1 \over 1 - z}\sum_{i = 0}^{\infty}{n \choose i}\pars{-z}^{\,i}
\\[5mm] & =
\bracks{z^{k}}{1 \over 1 - z}\bracks{\pars{1 - z}^{n}} =
\bracks{z^{k}}\pars{1 - z}^{n - 1} =
\bracks{z^{k}}\sum_{i = 0}^{\infty}{n - 1 \choose i}\pars{-z}^{\,i}
\\[5mm] & =
\bbx{\ds{{n - 1 \choose k}\pars{-1}^{\,k}}}
\end{align}
