Compute the sum
$$\sum_{k\ge0}{k \choose n-k}(-1)^k.$$
At this point I have tried many binomial theorem identities to try and get something to happen with the $n-k$, but couldn't seem to make sense of it. I also tried to form a recursive relation, but also couldn't seem to get it in the right form to where I could solve the relation.
This is only a partial answer (in that it is more of an evidence based conjecture than a proof).
I wrote a python script to calculate the sum for values of $m$ in the range $m=1..1000$ and the following is always true:
$$\sum_{k\geq 0}\binom{k}{m-k}(-1)^{k} = \begin{cases} 1 & \text{ if }m\equiv 0 \pmod 3 \\ -1 & \text{ if }m\equiv 1 \pmod 3 \\ 0 & \text{ if }m\equiv 2 \pmod 3\end{cases}$$
At the moment I am at a loss to prove this, but perhaps, knowing the answer will allow a proof to be made.
This of course uses the conventions that $\binom{0}{0}=1$ and $\binom{a}{b}=0$ if $b>a$ or if $b<0$. Because of all the "zero" cases, it only makes sense to sum values of $k$ for which $k\leq m\leq 2k$. This allows you to make the sum from $k=\lceil\frac{m}{2}\rceil$ to $k=m$.