How to simplify $\sum_{i=0}^{2n - d - 1} {n \choose i}$?

Question

Is it possible and how could I simplify this sum into a formula who's quantity of operations is independent of n?

$$ \sum_{i=0}^{2n - d - 1} {n \choose i} $$

i,n and d are natural numbers and d >= n.

Answer 1

As $d\geq n$, it would be easier to refer to how much bigger $d$ is from $n$, lets call it $\delta = d-n$.

So, $\sum\limits_{i=0}^{2n-d-1}\binom{n}{i} = \sum\limits_{i=0}^{n-(d-n)-1}\binom{n}{i} = \sum\limits_{i=0}^{n-\delta-1}\binom{n}{i}$

This should look familiar. $\sum\limits_{i=0}^{n}\binom{n}{i} = 2^n$, however in our case we stopped a bit early. In an attempt to make the sum we are working with look more like the complete sum:

$\sum\limits_{i=0}^{n-\delta-1}\binom{n}{i} = \sum\limits_{i=0}^{n-\delta-1}\binom{n}{i} + \sum\limits_{i=n-\delta}^{n}\binom{n}{i} - \sum\limits_{i=n-\delta}^{n}\binom{n}{i} = \sum\limits_{i=0}^{n}\binom{n}{i} - \sum\limits_{i=n-\delta}^{n}\binom{n}{i} = 2^n - \sum\limits_{i=n-\delta}^{n}\binom{n}{i}$

This can be simplified a little further if you prefer working with smaller indexes than larger due to the property that $\binom{n}{r} = \binom{n}{n-r}$

$=2^n - \sum\limits_{i=0}^\delta \binom{n}{i}$

Replacing $\delta$ back with $d-n$ if desired will complete the simplifications we can make without knowing what $n$ and $d$ actually are. Note, the number of iterations in the remaining sum, although potentially fewer, will still rely on the relationship between $n$ and $d$.