How can I prove that this sequence is correct?

Question

$$ \sum_{i=0}^n a_{i}\left(\begin{array}{c}k+n\\k+i\end{array}\right) = 1, \;\;\;\;\;\;\; n > 0, 1< k \leq n $$

and $$a_{i} = (-1)^i\left(\begin{array}{c}k+i-1\\ i\end{array}\right)$$

Answer 1

Week seek to evaluate

$$\sum_{q=0}^n (-1)^q {k+q-1\choose q} {k+n\choose k+q}.$$

This is

$$\sum_{q=0}^n (-1)^q {k+q-1\choose q} {k+n\choose n-q} \\ = \sum_{q=0}^n (-1)^q {k+q-1\choose q} [z^{n-q}] (1+z)^{k+n} \\ = [z^n] (1+z)^{k+n} \sum_{q=0}^n (-1)^q {k+q-1\choose q} z^q.$$

The coefficient extractor $[z^n]$ combined with the factor $z^q$ enforces the range (no contribution when $q\gt n$) and we find

$$[z^n] (1+z)^{k+n} \sum_{q\ge 0} (-1)^q {k+q-1\choose q} z^q \\ = [z^n] (1+z)^{k+n} \frac{1}{(1+z)^k} \\ = [z^n] (1+z)^n = 1.$$