1
$\begingroup$

I follow a subject almost like this link: Sum of 'the first k' binomial coefficients for fixed $N$ $$ f(N,k) = \sum^{k}_{i=0} \binom{N}{i} . $$ Michael Lugo suggest a way with geometric series : $$\sum^{k}_{i=0} \binom{N}{i} \leqslant \binom{N}{i} \cdot \frac{ n-k+1 }{(n-2\cdot k+1)}\label{1}\tag{ML} $$

Using Pascal's rule , $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} $ , I compress the terms to obtain others series $$ \begin{split} \sum^{k}_{i=0} \binom{N}{i} & = \binom{n}{k} + \binom{n}{k-1} + \binom{n}{k-2} + \binom{n}{k-3} + \ldots \\ &= \binom{n+1}{k} + \binom{n+1}{k-2}+\dots\;. \end{split}$$ This implies $$ \begin{split} \dfrac{ \sum^{k}_{i=0} \binom{N}{i} }{ \binom{n+1}{k} } & = 1 + \frac{(k-1) \cdot k}{(n-k+2) \cdot (n-k+3)} \\ & \quad + \frac{(k-3) \cdot (k-2) \cdot (k-1) \cdot k}{(n-k+2) \cdot (n-k+3) \cdot (n-k+4) \cdot (n-k+5)}\\ & \quad + \frac{(k-5) \cdot (k-4) \cdot (k-3) \cdot (k-2) \cdot (k-1) \cdot k}{(n-k+2) \cdot (n-k+3) \cdot (n-k+4) \cdot (n-k+5) \cdot (n-k+6) \cdot (n-k+7)} + \ldots\\ &\approx \frac{ (n-k+2) \cdot (n-k+3)}{(n+2) \cdot (n-2\cdot k+3)} \end{split} $$ the term of the series is $((k-1)\cdot k)/((n-k+2)\cdot(n-k+3)))$ so: $$ \sum^{k}_{i=0} \binom{N}{i} \approx \binom{n+1}{k} \cdot\frac{ (n-k+2) \cdot (n-k+3)}{(n+2) \cdot (n-2\cdot k+3)} \label{2}\tag{F1} $$ If we start at the third terms we have: $$ \begin{split} \frac{ \sum^{k}_{i=0} \binom{N}{i} }{ \binom{n+1}{k} } & = 1+ \frac{(k-1) \cdot k}{(n-k+2) \cdot (n-k+3)} \cdot \Bigg( 1 + \frac{(k-3) \cdot (k-2)}{(n-k+4) \cdot (n-k+5)} \\ &\quad+ \frac{(k-5) \cdot (k-4) \cdot (k-3) \cdot (k-2)}{(n-k+4) \cdot (n-k+5) \cdot (n-k+6) \cdot (n-k+7)} + \ldots \Bigg )\\ & \approx 1 + \frac{(k-1) \cdot k}{(n-k+2) \cdot (n-k+3)} \cdot \frac{(n-k+4) \cdot (n-k+5)}{(n+2) \cdot (n-2 \cdot k+7)} \end{split} \label{3}\tag{F2} $$
We can separate the series into 2 series, by taking only one terms on two which give: $$ \begin{split} & \frac{1 }{\binom{n+1}{k}} \cdot\Bigg( \binom{n+1}{k} + \binom{n+1}{k-4} + \binom{n+1}{k-8} + \ldots \Bigg) \\ & = 1+ \frac{(k-3)\cdot(k-2)\cdot(k-1)\cdot k}{(n-k+2)\cdot(n-k+3)\cdot(n-k+4)\cdot(n-k+5)} \\ &\quad + \frac{(k-7)\cdot(k-6)\cdot(k-5)\cdot(k-4)\cdot(k-3)\cdot(k-2)\cdot(k-1)\cdot k}{[(n-k+2)\cdot(n-k+3)\cdot(n-k+4)\cdot(n-k+5)\cdot(n-k+6)\cdot(n-k+7)\cdot(n-k+8)\cdot(n-k+9)]} \\ &\approx \frac{(n-k+2)\cdot(n-k+3)\cdot(n-k+4)\cdot(n-k+5)}{(n+2)\cdot(n-2\cdot k+5)\cdot(n^2-2\cdot k\cdot n+7\cdot n+2\cdot k^2-10\cdot k+12)} \end{split}$$ thus $$ \begin{split} & \frac{1 }{\binom{n+1}{k}} \cdot\Bigg( \binom{n+1}{k-2} + \binom{n+1}{k-6} + \binom{n+1}{k-10} + \ldots\bigg) \\ & = \frac{(k-1)\cdot k}{(n-k+2)\cdot(n-k+3)} \\ & \quad \cdot \Bigg( 1 + \frac{(k-5)\cdot(k-4)\cdot (k-3)\cdot(k-2)}{(n-k+4)\cdot(n-k+5)\cdot(n-k+6)\cdot(n-k+7)} \\ & \quad + \frac{(k-9)\cdot(k-8)\cdot(k-7)\cdot(k-6)}{(n-k+4)\cdot(n-k+5)\cdot(n-k+6)} \\ & \quad\cdot\frac{(k-5)\cdot(k-4)\cdot(k-3)\cdot(k-2)}{(n-k+7)\cdot(n-k+8)\cdot(n-k+9)\cdot(n-k+10)\cdot(n-k+11)} + \ldots \Bigg) \\ & \approx \frac{(k-1)\cdot k}{(n-k+2)\cdot(n-k+3)} \\ & \quad \cdot \frac{(n-k+4)\cdot(n-k+5)\cdot(n-k+6)\cdot(n-k+7)}{(n+2)\cdot(n-2\cdot k+9)\cdot(n^2-2\cdot k\cdot n+11\cdot n+2\cdot k^2-18\cdot k+40)} \end{split} $$ and this implies $$ \begin{split} f(N,k) & \approx \binom{n+1}{k} \\ & \quad \cdot \Bigg( \frac{(n-k+2)\cdot (n-k+3)\cdot(n-k+4)\cdot(n-k+5)}{(n+2)\cdot(n-2\cdot k+5)\cdot (n^2-2\cdot k\cdot n+7\cdot n+2\cdot k^2-10\cdot k+12)}\\ & \quad + \frac{(k-1)\cdot k}{(n-k+2)\cdot (n-k+3)}\\ & \quad \cdot \frac{(n-k+4)\cdot (n-k+5)\cdot (n-k+6)\cdot(n-k+7)}{(n+2)\cdot(n-2\cdot k+9)\cdot(n^2-2\cdot k\cdot n+11\cdot n+2\cdot k^2-18\cdot k+40)} \Bigg) \end{split}\label{4}\tag{F3} $$ This series are sharper, using the calculator PARI/GP , i found the following relative errors:

(N,k) (100,20) (100,40) (100,50) (1000,200) (1000,400) (1000,500)
\ref{1} 0.00626 0.10740 6.51962 0.00069 0.01563 23.65358
\ref{2} 0.000784 0.05096 1.629873 0.000107 0.0096452 7.25888
\ref{3} 2.700 E-5 0.012036 0.371743 6.3169 E-6 0.0039623 2.623599
\ref{4} 3.810 E-6 0.0086979 0.41073 1.338 E-6 0.003315 2.913452

But my problem is that for any approximation when $k \to N/2$ the error is too large, as you can see, because the geometric term converge to one.

I am seeking for an approximate formulation of the sum of binomial coefficient for fixed $N$, with sharp bound, to be differentiable if needed. Can we transform the series to be valid when $k\to N/2 $?

Best regards

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Have you tried exploiting the known values $f(2N, N-1) = 2^{2N-1} - \frac{1}{2} \binom{2N}{N}$ and $f(2N + 1, N) = 2^{2N}$ and handling central ranges by subtracting from / adding to these offsets? $\endgroup$ Commented Sep 29, 2023 at 8:07
  • 3
    $\begingroup$ Essentially the same question as mathoverflow.net/questions/17202. $\endgroup$ Commented Sep 29, 2023 at 15:38
  • 1
    $\begingroup$ It may be worth it to check bounds from my answer: mathoverflow.net/q/422395 $\endgroup$ Commented Oct 1, 2023 at 13:02
  • $\begingroup$ Do you have a response to the answer below? $\endgroup$ Commented Oct 2, 2023 at 1:40
  • $\begingroup$ I'm looking for very sharp approximation. I check some bounds given in mathoverflow.net/questions/17202 . Jean Gallier and Lovasz bounds are low only when k $\approx$ N/2, Chernoff's bound is slightly badder. Do you want a table to compare the different bounds and see the evolution ? $\endgroup$ Commented Oct 2, 2023 at 20:43

1 Answer 1

Reset to default
2
$\begingroup$

$\newcommand\ep\varepsilon$According to the Theorem on p. 129 of Uspensky, for all $n\ge100$ and all integers $k$ we have $$f(n,k)=2^n(\Phi(z_{n,k})+\ep_{n,k}), \tag{10}\label{10}$$ where $\Phi$ is the standard normal cumulative distribution function, $$z_{n,k}:=\frac2{\sqrt n}\Big(k-\frac{n-1}2\Big),$$ and $$|\ep_{n,k}|<\frac{0.52}n+e^{-3\sqrt n/4}.$$

In particular, if $k\approx n/2$, then $\Phi(z_{n,k})\approx1/2$ and hence the relative error of the approximation of $f(n,k)$ by $2^n\Phi(z_{n,k})$ is no more than $\approx\frac{1.04}n+2e^{-3\sqrt n/4}$.

Here is the table of the actual values of the relative errors $$e_{n,k}:=\frac{f_{n,k}}{2^n\Phi(z_{n,k})}-1$$ of the approximation $2^n\Phi(z_{n,k})$ of $f_{n,k}$ provided by formula \eqref{10} for $n=100$ and $k=30,40,50,60,70$:

enter image description here

Here is also the graph $\{(k,e_{n,k})\colon30\le k\le70\}$ for $n=100$:

enter image description here

Approximations of $f(n,k)$ with relative errors $o(1/n^p)$ for (say) $k=n/2+O(\sqrt n)$ for arbitrary real $p>0$ follow immediately from asymptotic expansions of the probability $f(n,k)/2^n$ (that a binomial random variable with parameters $n,1/2$ takes a value $\le k$) such as Theorem 6, Ch. VI in Petrov's book; the original source of this theorem is the paper by Osipov.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think i will use this result. Could you elaborate on the last paragraph? Is it this theorem page 171 , books.google.fr/… ? $Ur(x) = \Phi(x) + \sum^{[r]-2}_{v=1} \frac{Q_v(x)}{n^{v/2}}$ ? $\endgroup$ Commented Oct 2, 2023 at 21:10
  • $\begingroup$ @tess35 : Yes, it is Theorem 6 on p. 171. $\endgroup$ Commented Oct 2, 2023 at 21:59
  • $\begingroup$ @tess35 : I have added a reference to the original source of that Theorem 6. $\endgroup$ Commented Oct 3, 2023 at 2:44
  • $\begingroup$ Could you explain what is the $ \alpha_v $ coefficient ? If I understand, for $\nu$ = 1 , k1 = 1 , k2 =0... so K=1, for $\nu$ =2 , (k1=2,k2=0, K=2), (k1=0,k2=1,K=1) . I work on thermodynamic, so i search something like $ \mid (f_{true}-f_{approx})/f_{true} \mid \leq 0.1 $. , to differentiate or transform. $\endgroup$ Commented Oct 4, 2023 at 21:08
  • $\begingroup$ @tess35 : Are you referring here to Osipov's paper? There $\alpha_l=EX_n^l$, as defined just before formula (2) in that paper. I gave you references to Petrov and Osipov only because you were talking about some "very sharp approximation". However, in your latter comment you seem to be talking about the relative error being just $\le0.1$. Then Uspensky's result, stated in the first paragraph of my answer, will be more than enough, as it gives you a simple approximation with a relative error $<0.012$ for $n\ge100$. $\endgroup$ Commented Oct 4, 2023 at 21:24

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.