How to expand a summation of "n choose k" into a polynomial?

Question

I wish to expand

$$\sum\limits_{k = 0}^{i - 1} {n \choose k}$$

where $i \leq n$ into a polynomial. However I am uncertain about the coefficients of each term. I have consulted https://en.wikipedia.org/wiki/Binomial_coefficient but could not find this particular result.

Example: let $i = 3$, then $\sum\limits_{k = 0}^{i - 1} {n \choose k} = \frac{n^2}{2} + n - 1/2$. Both the leading coefficient and the constant term seems to be pretty arbitrary.

Is there a way to generalize?

Answer 1

You can define it as follows:

$${x \choose k }:=\frac{x(x-1)\cdots (x-k+1)}{k!}$$

where the following is called the falling factorial polynomial:

$$ (x)_k := x(x-1)\cdots (x-k+1)$$

and then use that the Stirling numbers of the first kind will satisfy:

$$ (x)_k = \sum_{j=0}^{k}s(k,j)x^{j} $$

So

$$ \sum_{k=0}^{i-1}{n\choose k}=\sum_{k=0}^{i-1}\frac{1}{k!}\sum_{j=0}^{n}s(k,j)n^{j}= \sum_{j=0}^{n}\left(\sum_{k=0}^{i-1}\frac{s(k,j)}{k!}\right)n^{j} $$