<s>[INST] Proving these binomial sums Need help proving with these two:
1)
$$\sum_{k=0}^m (-1)^k \binom{n}{k}= (-1)^m \binom{n - 1}{m}$$
2)
$$\sum_{k=0}^n \binom{n}{k} \binom{k}{m}= \binom{n}{m} 2^{n-m}$$
I tried using these two properties below, but got nowhere. $$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$$
$$ \sum_{k=0}^n \binom{n}{k} = 2^n$$
 [/INST] For the first equality, it can be easily proved by induction on $m$. When $m = 0$, the LHS is $1$ and the RHS is also $1$, thus the equality holds. For $m \geq 1$, we have
\begin{align}
\sum_{k=0}^m (-1)^k \binom{n}{k} &= \sum_{k=0}^{m-1}(-1)^k\binom{n}{k} + (-1)^m\binom{n}{m} \\
&= (-1)^{m-1}\binom{n-1}{m-1} + (-1)^{m}\binom{n}{m}\\
&= (-1)^m\left(\binom{n}{m} - \binom{n-1}{m-1}\right) \\
&= (-1)^m \binom{n-1}{m}
\end{align}
For the second equality, we have
\begin{align}
\sum_{k=0}^n \binom{n}{k}\binom{k}{m} &= \sum_{k=0}^n \binom{n}{m} \binom{n-m}{n-k} \\
&= \binom{n}{m} \sum_{k=0}^n \binom{n-m}{n-k} \\
&= \binom{n}{m} 2^{n-m}
\end{align}
</s>