sum of binomial coefficient approximation by geometric series

Question

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

Answer 1

$\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$:

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

---

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.