Compute telescopic sum of binomial coefficients

315 Views Asked by At

Is there a nice or simple form for a sum of the following form? $$ 1 + \sum_{i=1}^k \binom{n-1+i}{i} - \binom{n-1+i}{i-1}$$

Motivation: Due to a computation in the formalism of Schubert calculus the above sum with $k = \lceil n/2 \rceil -1$ is equal to the number of lines intersecting $2n-4$ general subspaces $H_j\subseteq \mathbb{P}^n$ of dimension $n-2$.

2

There are 2 best solutions below

4
On BEST ANSWER

No need for a power tool when a manual tool does the trick.

Hockey-stick identity:

$$ \sum_{i=0}^k \binom{n+i}{i} = \binom{n+k+1}{k} $$

Applying to our expression:

$$ 1 + \sum_{i=1}^k \binom{n-1+i}{i} - \binom{n-1+i}{i-1} \\ 1 + \sum_{i=1}^k \binom{n-1+i}{i} - \sum_{i=1}^k \binom{n-1+i}{i-1} \\ 1 - \binom{n-1}{0} + \sum_{i=0}^k \binom{n-1+i}{i} - \sum_{i=0}^k \binom{n+i}{i} \\ \sum_{i=0}^k \binom{n-1+i}{i} - \sum_{i=0}^k \binom{n+i}{i} \\ \binom{n+k}{k} - \binom{n+k+1}{k} \\ \binom{n+k}{k} - \left(\binom{n+k}{k-1}+\binom{n+k}{k}\right) \\ -\binom{n+k}{k-1} $$

2
On

Hint

The following method does not use telescopic series but it makes use of elementary binomial theorem along with some geometric progression to arrive at the answer.

$$\begin{aligned}S&=\sum_{i=1}^{k}{n-1+i\choose n-1}-\sum_{i=1}^{k}{n-1+i\choose n}\\&=\left(\text{coeff. of } x^{n-1} \text{ in } \sum_{i=1}^{k}(1+x)^{n-1+i}\right)-\left(\text{coeff. of } x^{n} \text{ in } \sum_{i=1}^{k}(1+x)^{n-1+i}\right)\end{aligned}$$