# what is some polynomial bound of the following expression?

I have the expression (for some $k$ and $r$ natural numbers):

$\sum_{l=0}^r {l \choose k}$.

Is there a way to bound this expression using a polynomial of degree which is linear in $k$ (or polynomial in $k$)?

I am pretty sure that each $l \choose k$ is a polynomial of the form $O(l^k)$.

-

You sum is same as

$$\sum_{l = k}^{r} \binom{l}{k}$$

(Note, from $k$ to $r$, assuming $\binom{a}{b} = 0$ if $a \lt b$).

This is actually equal to

$$\binom{r+1}{k+1}$$ by using

$$\binom{l+1}{k+1} - \binom{l}{k+1} = \binom{l}{k}$$

-

According to Wolfram Alpha, this is equivalent to $$\frac{(-k+r+1) \binom{r+1}{k}+k \binom{0}{k}}{k+1}$$

So perhaps it will be easier to bound that with a polynomial of degree $k$.

-
Mathematica needs to work on its binomial simplification method. Is that $k(0 \choose k)$ for non-integer $k$? –  Mitch Feb 4 '11 at 2:16