2
$\begingroup$

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)$.

2 Answers 2

2

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}$

0

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$.

  • 0
    Mathematica needs to work on its binomial simplification method. Is that $k(0 \choose k)$ for non-integer $k$?2011-02-04