0

I know there's no closed form for the following but I need an approximation (preferably, an upper bound). $$\sum_{i=1}^k \left( \begin{array}{c} n\\ i \end{array} \right) $$

Any help will be appreciated. Regards.

Husam
  • 9
  • 1
    $2^n$? Might be too trivial? –  Mar 25 '15 at 07:02
  • 1
    @John, $2^n$ will not be a tight upper bound since the value is less than that. If the summation was from $i=1$ to $i=n$, then it would have worked. – Prasun Biswas Mar 25 '15 at 07:04
  • 1
    $2^n -1$ then? But still might be too trivial... –  Mar 25 '15 at 07:06
  • 1
    @John, the sum ends at $i=k~,~k\leq n$ , not at $i=n$. You need to remove the cases of $i=k+1$ to $i=n$ too. – Prasun Biswas Mar 25 '15 at 07:09
  • $\displaystyle\sum_{i=1}^n \dbinom{n}{i}=2^n-1\neq \sum_{i=1}^k \dbinom{n}{i}$ in general. – Prasun Biswas Mar 25 '15 at 07:10
  • 3
    @PrasunBiswas: I understand what you are saying. That's why I keep saying that my upper bound is too trivial. But the OP is asking for an approximate upper bound..... So at least $2^n - 1$ is a correct one (just might not be the best) –  Mar 25 '15 at 07:11
  • Well, in that case, it works. It isn't a good upper bound, but nonetheless, it works. – Prasun Biswas Mar 25 '15 at 07:12

3 Answers3

2

Assuming you want upper bounds when $n$ is large, you can always use the Stirling approximation given here : $$ \sum_{i=1}^k \binom ni = \sum_{i=1}^k \frac{n!}{i! (n-i)!} \\ \le \sum_{i=1}^k \frac 1{i!} \left( \frac{n^{n+\frac 12} e^{-n+1}}{\sqrt{2\pi} (n-i)^{(n-i)+\frac 12} e^{-(n-i)}} \right) \\ = \frac e{\sqrt{2\pi}} \sum_{i=1}^k \frac {(n/e)^i}{i!} \frac{n^{n-i+\frac 12}}{(n-i)^{n-i+\frac 12}} \\ = \frac e{\sqrt{2\pi}} \sum_{i=1}^k \frac {(n/e)^i}{i!} \left( 1- \frac i{n-i} \right)^{n-i+\frac 12} \\ \le \frac e{\sqrt{2\pi}} \sum_{i=1}^k \frac {(n/e)^i}{i!} \\ \le \frac {e}{\sqrt{2\pi}} (e^{n/e}-1). $$ That last bound seems pretty horrible, but I just wanted to give some ideas. Perhaps you could stop before that (or instead of bounding the $(1-x)^r$ factor by $1$, using Bernoulli's inequality) ; I don't know for what purposes you need this bound so I don't know if it is enough.

Hope that helps,

Patrick Da Silva
  • 41,413
1

What about this for even $n$ (source: Discrete Math by J. Gallier, proposition 4.16)?

$$\sum_{i=0}^k {n \choose i} < 2^{n-1} \frac{{n \choose k+1}}{{n \choose n/2}}$$

0

From binomial theorem,

$$(x+y)^n = \displaystyle\sum_{k=0}^n {n\choose k}x^{n-k}y^k$$

Set $x=y=1$. So you have $2^n = \displaystyle\sum_{k=0}^n {n\choose k}$. But notice your requirement is that the sum starts from $k=1$, not $k=1$. So we take the case when $k=0$, and that is just 1. So the result of your question is $2^n-1$.

cgo
  • 1,810