Intereting Posts

Noether normalization for $k_{x}$
convergence of a series involving $x^\sqrt{n}$
Finite groups of Möbius Transformations
How is second-order ZFC defined?
What is the limit of $H_n – H_{an}$ when $n\to\infty$, for some fixed $a$ in $(0,1)$, where $H_n$ is the $n$th harmonic number?
Definition of weak time derivative
linear least squares minimizing distance from points to rays – is it possible?
Prove that the product of four consecutive positive integers plus one is a perfect square
Bilateral Laplace transform
Why do we do mathematical induction only for positive whole numbers?
Rotation $x \to x+a \pmod 1$ of the circle is Ergodic if and only if $a$ is irrational
How to show that $p-$Laplacian operator is monotone?
Evaluation of $\prod_{n=1}^\infty e\left(\frac{n}{n+1}\right)^{n}\sqrt{\frac{n}{n+1}}$
Cardinality of a basis of an infinite-dimensional vector space
Combinatorics problem (Pigeonhole principle).

Good afternoon,

I would like to ask, if anyone knows how to evaluate a sum

$$\sum_{k=0}^{\lambda n}{n \choose k}$$

- A (non-artificial) example of a ring without maximal ideals
- Asymptotic integral expansion of $\int_0^{\infty} t^{3/4}e^{-x(t^2+2t^4)}dt$ for $x \to \infty$
- Asymptotic behaviour of a multiple integral on the unit hypercube
- An extrasensory perception strategy ðŸ™‚
- A recurrence that wiggles?
- Limit of $\sqrt{(x+1)…(x+n)} - x$ as $x \to +\infty$

for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better.

In Concrete Mathematics (Graham, Knuth, Patashnik), it is shown how to evaluate this sum with absolute error $O(1)$, but it is not clear to me, how to obtain better absolute error in a straightforward manner.

Thank you in advance.

- A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$
- Combinatorial Proof
- self similar solution for porous medium equation 2
- How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?
- Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?
- Generalized Case: Three Consecutive Binomial Coefficients in AP
- Show this equality (The factorial as an alternate sum with binomial coefficients).
- A proof of Wolstenholme's theorem
- Is the numerator of $\sum_{k=0}^n \frac{(-1)^k}{2k+1}\binom{n}{k}$ a power of $2$?
- If $p$ and $q$ are primes, which binomial coefficients $\binom{pq}{n}$ are divisible by $pq$?

This is more of an extended comment than an answer, but you may find it useful.

In Exercise 9.42 of *Concrete Mathematics* (page 492 in the second edition),

the authors establish the asymptotic formula

$$\sum_{k=0}^{\lambda n} {n\choose k}=2^{n H(\lambda)-\lg(n)/2+O(1)}$$

where $0<\lambda< 1/2$,

$H(\lambda)= \lambda \lg({1\over \lambda})+(1-\lambda)\lg({1\over 1-\lambda})$, and

$\lg$ is the binary logarithm.

The sum on the left is a small fraction of the full sum $2^n$.

Note that this is a multiplicative approximation, the **ratio** of the

sum and the approximation remains bounded as $n\to\infty$, not the difference.

Their result has an interpretation using probability.

Write

$$\sum_{k=0}^{\lambda n} {n\choose k} =2^n\,\mathbb{P}(X_n/n\leq \lambda)$$

where $X_n$ is a binomial$(n,1/2)$ random variable.

The theory of large deviations suggests an approximation

$$\mathbb{P}(X_n/n\leq \lambda)\approx \exp(-nI(\lambda))$$

where $I$ is the rate function $I(x)=x\log(x)+(1-x)\log(1-x)+\log(2)$.

This gives the leading factor in their approximation; they also divide by $\sqrt{n}$

for further accuracy.

If you are willing to use the standard normal distribution function

$\Phi(z)=\mathbb{P}(Z\leq z)$, then by the central limit theorem,

we have

$$ \mathbb{P}(X_n\leq \lambda n)

=\mathbb{P}\left({X_n-n/2\over\sqrt{n/4}}\leq {\lambda n-n/2\over\sqrt{n/4}} \right)

\approx\mathbb{P}\left(Z\leq \sqrt{n}(2\lambda-1) \right).$$

In other words, we have the approximation

$$ \sum_{k=0}^{\lambda n} {n\choose k} =2^n\, \Phi(\sqrt{n}(2\lambda-1)).$$

This seems to be at least as

accurate as the *Concrete Mathematics* approximation,

and you can get more accuracy by using the “continuity correction”.

More detailed asymptotic results for binomial tails can be found in this paper by

Andrew Carter and David Pollard. In particular, see Theorem 1. I hope you find what you want there; happy hunting!

- If $ad$ and $bc$ are odd and even, respectively, then prove that $ax^3+bx^2+cx+d$ has an irrational root.
- Let $\sum_{n=1}^\infty \frac{a_n}{3^n}.$ Determine (numerically or not) the limit of the infinite series by choosing $a_n=0$ or $2$ randomly.
- Does the statement “the $R$-algebra homomorphisms $A \rightarrow R$ are linearly independent whenever $R$ is a field” admit any generalizations?
- What's the value of this Viète-style product involving the golden ratio?
- The sequence of improper integrals of the form $\int\frac{dx}{1+x^{2n}}$
- The set of all nilpotent elements is an ideal
- Finding the integral $I=\int_0^1{x^{-2/3}(1-x)^{-1/3}}dx$
- $\alpha=(714)(3925)$ Find $\beta \in S_9$ so $\beta^5=\alpha$
- Natural isomorphisms and the axiom of choice
- Find volume between two spheres using cylindrical & spherical coordinates
- How to evaluate $\int_{0}^{1} \frac{\ln x}{x+1} dx$
- Is $ds$ a differential form?
- Proving $\int_{0}^{\infty}\frac{x}{(x^2+1)(e^{2\pi x}+1)} dx=1-\frac{\gamma}{2}-\ln2$
- Continuity of the basis of the null space
- What space to use?