PropositionStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Elementary binomial probability envelopes

Statement

Let $N \geq k \geq 1$ be integers and $0 < p < 1$ . A $Bin (N, p)$ count is the sum of $N$ mutually independent Bernoulli real random variables on a common probability space $(Ω, F, P)$ , each equal to $1$ with probability $p$ and $0$ otherwise. Then

$P (Bin (N, p) = k) \leq \frac{(N p)^{k} e^{- p (N - k)}}{k!} \leq \exp {k \log (N p / k) + k - p (N - k)} .$

Here $k! = 1 \cdot 2 \dots k$ , $e = \exp (1)$ , and $\log$ is the inverse of the real exponential. In particular $k! \geq (k / e)^{k}$ , $(\binom{N}{k}) \leq N^{k} / k!$ , and $1 - p \leq e^{- p}$ . Separately, for $N \geq 0$ and $0 < p < 1$ , $P (Bin (N, p) = 0) = (1 - p)^{N} \leq e^{- N p}$ ; no logarithm of zero is used.

Facts & Assumptions

[F1]

A binomial count is the sum described above, and its mass at $k \in {0, \dots, N}$ is $(\binom{N}{k}) p^{k} (1 - p)^{N - k}$ . The coefficient $(\binom{N}{k})$ counts $k$ -element subsets of an $N$ -element set (Probability measures and probability spaces, Random elements and real random variables, Pairwise and mutual independence of finite-valued random variables, Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials, The Binomial count has its usual probability mass function, The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|).

[F2]

For $0 \leq k \leq N$ , $(\binom{N}{k}) k! = N (N - 1) \dots (N - k + 1)$ , with the empty product equal to $1$ ; factorials are positive and $0! = 1$ (C(n, k) k! (n-k)! = n! for k ≤ n; hence C(n, k) k! = n^k̲, the quotient n!/(k!(n-k)!) is a natural number, and C(n, k) = C(n, n-k), The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F3]

On $(0, \infty)$ , $\log$ is continuously differentiable with derivative $1 / x$ , is strictly increasing, and takes products to sums, with $\log 1 = 0$ (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F4]

A continuous function bounded above by $M$ on $[a, b]$ has integral at most $M (b - a)$ ; the fundamental theorem evaluates the integral of a continuously differentiable function's derivative, and the product rule differentiates products (If m ≤ f ≤ M on [a,b] then m(b-a) ≤ L(f,P) ≤ ∫ₐᵇ f ≤ ∫ₐᵇ f ≤ U(f,P) ≤ M(b-a) for every partition P; in particular every constant function is integrable, with ∫ₐᵇ c = c(b-a), The fundamental theorem of calculus and integration by parts, Sum, product, quotient, and chain rules from difference quotients).

[F5]

The real exponential is strictly increasing, $\log$ is its inverse, $e = \exp (1)$ , and $\exp (u + v) = \exp (u) \exp (v)$ (The natural logarithm as the inverse of the exponential function, The real exponential function and the number e by a power series, The exponential function is strictly increasing, The exponential addition formula exp(x+y)=exp(x)exp(y)).

[F6]

If $0 \leq p \leq 1$ and $m$ is a nonnegative integer, then $(1 - p)^{m} \leq \exp (- m p)$ ; also $1 + x \leq \exp (x)$ for every real $x$ (1+x≤exp(x) for every real x, hence (1-p)ᵐ≤exp(-mp)).

Proof

Given: Integers $N \geq k \geq 1$ and $0 < p < 1$ ; for the final case, an integer $N \geq 0$ and $k = 0$ .

Goal: Prove both positive-count bounds, their stated elementary ingredients, and the zero-count bound.

1.1F3F4algebra

For each integer $j \geq 1$ , [F3] gives $\log t \leq \log (j + 1)$ on $[j, j + 1]$ . By [F4], $\int_{j}^{j + 1} \log t d t \leq \log (j + 1)$ . The product rule and [F3] show that $t \log t - t$ is a continuously differentiable antiderivative of $\log t$ on $(0, \infty)$ , so the same integral equals $(j + 1) \log (j + 1) - (j + 1) - j \log j + j$ .

1.2F1F2F6algebra

Each of the $k$ positive factors in the falling factorial in [F2] is at most $N$ , so $(\binom{N}{k}) \leq N^{k} / k!$ . With $m = N - k$ , [F6] gives $(1 - p)^{N - k} \leq e^{- p (N - k)}$ and, at $x = - p$ , $1 - p \leq e^{- p}$ . Substituting these bounds into [F1] proves the first displayed inequality.

2.1step 1.1F2F3F5algebra

Sum the inequalities of step 1.1 for $j = 1, \dots, k - 1$ . The left sides telescope to $k \log k - k + 1$ , and the right side is $\sum_{i = 2}^{k} \log i = \log (k!)$ by [F2] and [F3]. For $k = 1$ the same inequality holds directly. Thus $\log (k!) \geq k \log k - k$ . Applying the increasing exponential and [F5] yields $k! \geq (k / e)^{k}$ .

3.1step 2.1F5algebra

By step 2.1 and positivity, $1 / k! \leq (e / k)^{k}$ . Multiplying by the nonnegative remaining factors and using the logarithm inverse and exponential addition laws in [F5] gives $\frac{(N p)^{k} e^{- p (N - k)}}{k!} \leq \exp {k \log (N p / k) + k - p (N - k)}$ .

4.1F1F6algebra∎

For $k = 0$ , [F1] and the boundary value $(\binom{N}{0}) = 1$ give probability $(1 - p)^{N}$ ; [F6] bounds it by $e^{- N p}$ . This also holds for $N = 0$ , when both sides equal $1$ . The stated bounds follow.

Remarks

The displayed inequalities are finite bounds. Any later asymptotic replacement of $N = n - 1$ or of an integer $k$ by a real threshold requires its own explicit error estimate.

Depends on

Used by · 4

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.