LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-13

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.

$1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$

Statement

For every real $x$ , $1 + x \leq \exp (x) .$ Consequently, if $0 \leq p \leq 1$ and $m \in N$ , then $(1 - p)^{m} \leq \exp (- m p) .$

Facts & Assumptions

Given: A real $x$ , a real $p \in [0, 1]$ , and a natural $m$ .

[L1]

$\exp (0) = 1$ (The real exponential function and the number $e$ by a power series).

[L2]

The derivative of the exponential is the exponential (The exponential function is smooth and $(\exp)^{'} = \exp$ ).

[L3]

The exponential is strictly increasing (The exponential function is strictly increasing).

[L4]

The exponential is positive at every real argument (The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ ).

[L5]

If a function is continuous on $[a, b]$ and differentiable on $(a, b)$ , then its endpoint difference equals its derivative at an intermediate point times $b - a$ (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[L6]

Natural powers are defined recursively, and preserve order on nonnegative bases (Integer powers $a^{m}$ , Monotonicity of $x \mapsto x^{n}$ and of $n \mapsto a^{n}$ ).

[L7]

For all real $u, v$ , $\exp (u + v) = \exp (u) \exp (v)$ (The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ ).

Proof

technique · cases

1.1assume-case zeroL1

If $x = 0$ , then $1 + x = 1 = \exp (x)$ .

1.2assume-case positiveL1L2L3L5choose

If $x > 0$ , [L5] and [L2] give $\exp (x) - 1 = \exp (c) x$ for some $0 < c < x$ ; [L3] gives $\exp (c) > 1$ , hence $\exp (x) > 1 + x$ .

1.3assume-case negativeL1L2L3L4L5choose

If $x < 0$ , apply [L5] on $[x, 0]$ : $1 - \exp (x) = \exp (c) (- x)$ for some $x < c < 0$ . Now $0 < \exp (c) < 1$ by [L3] and [L4], so $1 - \exp (x) < - x$ and $1 + x < \exp (x)$ .

2.1step 1.1step 1.2step 1.3cases-exhaustive

The three cases prove $1 + x \leq \exp (x)$ for every real $x$ .

3.1step 2.1L6L7algebra∎

Apply step 2.1 to $x = - p$ to get $0 \leq 1 - p \leq \exp (- p)$ , then raise both sides to the natural power $m$ and use [L7] repeatedly to obtain $(1 - p)^{m} \leq \exp (- m p)$ . The case $m = 0$ is equality, including $p = 1$ .

Depends on

Dependency tree · 2 levels

Sources

J. Matousek and J. Vondrak, The Probabilistic Method, Chapter 4

1+x≤exp⁡(x)1+x≤exp(x) for every real xx, hence (1−p)m≤exp⁡(−mp)(1−p)m≤exp(−mp)