Alternating hockey stick sum $\sum_{m=k}^M (-1)^m \binom{m}{k}$

Question

I'd like to calculate the following sum efficiently

$$S(k, M) = \sum_{m=k}^M (-1)^m \binom{m}{k}$$

I've tried to use generating functions and write

$$ S(k,M) = \sum_{m=k}^M [x^k] (-1-x)^m = [x^k] \frac{(-1-x)^{k+1}-(-1-x)^{M+1}}{2+x} $$

But because there's $2+x$ in the denominator, it will still be a sum and not just coefficient extraction from the numerator as happens in the usual hockey stick formula.

Another thing I tried is to write $\binom{m}{k} = \binom{m+1}{k+1} - \binom{m}{k+1} $, so we have

$$ S(k,M) = \sum_{m=k}^M (-1)^m \binom{m+1}{k+1} - \sum_{m=k}^M (-1)^m \binom{m}{k+1} = \dots $$

Oh, and just noticed: up to sign these are A108561. (The columns or something maybe some sort of diagonals.) There's the formula $T(n,k) = T(n-1,k) + T(n-2,k-1) + T(n-2,k-2)$ there. Could that be helpful, or do we end up generating the whole triangle? That would be too big, I have $M=10^7$. Although, I am calculating this for all $k=1,\dots, M$ so if we can calculate these numbers along as we go that would be great!

Answer 1

You have $$\eqalign{S(k,M) - S(k,M-1) &= (-1)^M {M \choose k} = (-1)^M \left({M-1 \choose k-1} + {M-1 \choose k}\right)\cr &= -S(k-1,M-1) + S(k-1,M-2) - S(k,M-1) + S(k,M-2))} $$ so $$ S(k,M) = -S(k-1,M-1) + S(k-1,M-2) + S(k,M-2) $$ with $S(k,M) = 0$ if $k > M$ or $k = 0$ and $(-1)^M$ if $k=M$.

Note that to compute $S(k,M)$ for all $k = 1, \ldots, M$ you will need $S(\ldots,M-1)$ and $S(\ldots, M-2)$. So you don't need to keep the whole triangle in memory, just the last two $M$'s in addition to the one you're doing now.

Answer 2

Disclaimer

Since you have accepted an answer, I presume you have obtained the answer you wanted. Therefore, I will only post a concise alternative, in case you're interested to explore further.

Combinatorial Argument

Select a subset of $k+1$ numbers from the set $\{1,2,...,M+1\}$. Let $n_{o}$ be the number of subsets in which the largest element is odd and $n_{e}$ be the number of subsets in which the largest element is even. We have the following relation:

$$ S(k,M) = n_{o}-n_{e} $$

Using this argument, we can obtain various recursive relations in the form of:

$$ S(k,M)=\left(-1\right)^{n}\sum_{j=0}^{n}\binom{n}{j}\cdot S(k-j,M-n) $$

where $n<\min(k,M)$. One example is the following relation, when $n=1$:

$$ S(k,M)=-S(k,M-1) -S(k-1,M-1) $$

Remarks

By selecting $n>1$, it's possible to skip some values of $M$. However, you will not get the complete values of $k=1,...,M$. So I leave that choice to you.