Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$

$O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?

share|improve this question
2  
Do you mean $\sum_{i=1}^k {n \choose i}$? –  Robert Israel Sep 13 '11 at 20:13
1  
Assuming $n$ grows while $k$ is a fixed constant, the given sum is $\frac{n^k}{k!}+ O(n^{k-1})$. This is tight up to the constant in the $O$ notation. –  Srivatsan Sep 13 '11 at 20:14
1  
@Srivatsan, if $k$ is a fixed number, then the constant factor $\frac{1}{k!}$ is irrelevant for the growth rate. –  Henning Makholm Sep 13 '11 at 20:16
    
@Hen Thanks. Fixed now :-). –  Srivatsan Sep 13 '11 at 20:17
    
@Robert - yes, of course, sorry. Fixed. –  Anton Belov Sep 13 '11 at 20:19

2 Answers 2

up vote 10 down vote accepted

We are interested in the sum $$V(n,k) := \sum\limits_{i=0}^k \binom{n}{i}.$$ (Notice that I have added $i=0$ for convenience. This affects the sum only by an additive $1$.) Indeed, this quantity has a combinatorial significance: it is the volume of a "Hamming ball" of radius $k$ in the Hamming space (the $n$-dimensional hypercube). It is quite difficult to say anything precise without information about the relative sizes of $k$ and $n$. I will therefore address some common regimes of interest in the answer. Without loss of generality, we will take $k \leq n/2$, since for $k > n/2$, we can write $V(n, k)$ as $2^n - V(n, n-k+1)$.

First, suppose that $n$ grows while $k$ is a fixed constant independent of $n$. Then the lower order terms (terms corresponding to $i < k$) are all $O(n^{k-1})$. Since there are just $k$ of them, we can absorb all of them into a single $O(n^{k-1})$. The remaining term $\binom{n}{k}$ is a polynomial in $n$ of degree $k$ and leading coefficient $\frac{1}{k!}$. Therefore, this term is $\frac{n^{k}}{k!}+O(n^{k-1})$. Combining these two observations, $$ V(n,k) = \frac{n^{k}}{k!} + O(n^{k-1}). $$


Another regime of interest is when $k$ is large. Specifically, suppose $k = \alpha n$ where $\alpha \in (0, 1/2)$. In this case, by Stirling approximation and a lot of calculations, we can show that $$ V(n, \alpha n) = 2^{n H(\alpha) - \frac{1}{2} \log_2 n + O(1)}, $$ where the exponent $H(\alpha)$ is the Shannon entropy or the binary entropy given by: $$ H(\alpha) = - \alpha \log_2 \alpha - (1-\alpha) \log_2 (1-\alpha). $$ For $\alpha \in (0, 1/2)$, $H(\alpha)$ is strictly increasing and is strictly positive. I want to point out that when $k$ is so large, the $n^k$ upper bound is quite crummy: $n^k = 2^{k \log n} = 2^{\alpha n \log n}$. This is a useless upper bound because we already know a much better upper bound of $2^n$. (For a reference to this estimate of $V(n, \alpha n)$, check Problem 9.42 in Concrete Mathematics. In many common cases, one is however content with a less precise form, such as $2^{n H(\alpha)+o(n)}$.)

There are, of course, more things that one can ask: generalization to the $q$-ary hypercube, intermediate values of $k$ (e.g., $k = O(\log n)$), values of $k$ close to $n/2$ (e.g., $\frac{n}{2} - c \sqrt{n}$) and so on. Each of these is a fruitful direction of study, but I cannot touch upon any of them here.

EDIT: The precise estimate is taken from Mike's comment. (Thanks, Mike!)

share|improve this answer
    
I was about to post this as an answer, but it's so close to yours that I'll leave it as a comment: Problem 9.42 in Concrete Mathematics has a slightly more precise expression for $V(n,\alpha n): 2^{n H(\alpha) - \frac{1}{2}\log_2 n + O(1)}$. There's an outline of their derivation in the answer section of the book. –  Mike Spivey Sep 13 '11 at 20:37
    
Thank you for such an informative answer -- I was just about to ask for $k = \alpha n$ ;-) –  Anton Belov Sep 13 '11 at 20:38
    
@Mike I will edit my answer (sometime later) to include this reference. Hope it's ok with you! :-) Thanks. –  Srivatsan Sep 13 '11 at 20:39
    
Certainly. I think it's fairly common practice to incorporate others' comments into our answers if we find them sufficiently helpful. –  Mike Spivey Sep 13 '11 at 20:46

Let $k$ be fixed. Then, in the "big Oh" sense, the bound is tight.

For example, let $\epsilon$ be a very small positive number. It is easy to verify that $$\lim_{n \to \infty} \frac{n^{k-\epsilon}}{\binom{n}{k}}=0.$$ So we cannot replace $n^{k}$ by $n^{k-\epsilon}$. We cannot even replace $n^k$ by something that grows almost as fast as $n^k$, such as $n^k/(\log(\log n))$.

So for fixed $k$, we will not find a "cheaper" upper bound in the "big Oh" sense. Of course, we can improve the implicit constant, by dividing by $k!$ (the terms $\binom{n}{i}$ with $i<k$ make negligible relative contribution when $n$ is large).

share|improve this answer
    
great point; i would up-vote if i could; thank you –  Anton Belov Sep 13 '11 at 20:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.