I'm working in a project about sequences and found a problem trying to proof the following equality for any $k$:
Let $0 \leq m \leq k$ $$\sum_{i = m}^{k} (-1)^{i+m}\binom{k+1}{i}\binom{i}{m} = (-1)^{k+m}\binom{k+1}{m}$$
I tried with induction, but I'm not able to continue after some point:
Base case: $k=0$ ($m$ must be $0$) $$\sum_{i=0}^{0}(-1)^{i+0}\binom{1}{i}\binom{i}{0} = 1 = (-1)^{0 + 0}\binom{1}{0}$$
Induction step: supose $\sum_{i = m}^{k} (-1)^{i+m}\binom{k+1}{i}\binom{i}{m} = (-1)^{k+m}\binom{k+1}{m}$
$$ \begin{align*} \sum_{i=m}^{k+1}(-1)^{i+m}\binom{k+2}{i}\binom{i}{m} &= (-1)^{k+1+m}\binom{k+2}{k+1}\binom{k+1}{m} + \sum_{i=m}^{k}(-1)^{i+m}\binom{k+2}{i}\binom{i}{m}\\[10pt] &= -(k+2)\sum_{i=m}^{k}(-1)^{i+m}\binom{k+1}{i}\binom{i}{m} + \sum_{i=m}^{k}(-1)^{i+m}\binom{k+2}{i}\binom{i}{m}\\[10pt] & = \sum_{i=m}^{k}(-1)^{i+m}\binom{i}{m}\left(\binom{k+2}{i} - (k+2)\binom{k+1}{i}\right)\\[10pt] &= \sum_{i=m}^{k}(-1)^{i+m}\binom{i}{m}\binom{k+2}{i}(i-k-1) \end{align*} $$
In trying to prove
$$\sum_{q=m}^k (-1)^q {k+1\choose q} {q\choose m} = (-1)^k {k+1\choose m}$$
we observe that
$${k+1\choose q} {q\choose m} = \frac{(k+1)!}{(k+1-q)! \times m! \times (q-m)!} = {k+1\choose m} {k+1-m\choose q-m}$$
and we get for the LHS
$${k+1\choose m} \sum_{q=m}^k (-1)^q {k+1-m\choose q-m} = {k+1\choose m} \sum_{q=0}^{k-m} (-1)^{q+m} {k+1-m\choose q} \\ = (-1)^m {k+1\choose m} \sum_{q=0}^{k-m} (-1)^q {k+1-m\choose q} \\ = (-1)^m {k+1\choose m} ((1-1)^{k-m+1}-(-1)^{k+1-m}) = (-1)^k {k+1\choose m}.$$