LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

A binomial support-count bound

Statement

For $d, m \in N$ with $1 \leq m \leq d$ ,

$(\binom{d}{m}) \leq {(\frac{e d}{m})}^{m} .$

Here $(\binom{d}{m})$ is the number of $m$ -element subsets of a $d$ -element set, $m!$ is the factorial, $e = \exp (1)$ , and integer powers have the convention of Integer powers $a^{m}$ .

Facts & Assumptions

Given: Integers $d, m$ with $1 \leq m \leq d$ .

[F1]

For $m \leq d$ , $(\binom{d}{m}) m! (d - m)! = d!$ , equivalently $(\binom{d}{m}) = d^{\underline{m}} / m!$ , and $d^{\underline{m}} = d (d - 1) \dots (d - m + 1)$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ , The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[F2]

$m! = \prod_{j = 1}^{m} j > 0$ ; the real logarithm is continuous and strictly increasing, and obeys $\log (x y) = \log x + \log y$ for positive $x, y$ ; and $\log e = 1$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ , Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm as the inverse of the exponential function, The real exponential function and the number $e$ by a power series).

[F3]

$\log x = \int_{1}^{x} d t / t$ for $x > 0$ , $\log^{'} (x) = 1 / x$ , and the fundamental theorem of calculus applies to continuous integrands (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The second fundamental theorem: if $G$ is differentiable on $[a, b]$ with $G^{'} = f$ and $f$ is integrable, then $\int_{a}^{b} f = G (b) - G (a)$ ).

[F4]

Finite sums obey their recursive product convention (Finite sums and finite products, by recursion, Laws of finite sums and finite products), and the Riemann integral preserves pointwise inequalities between integrable functions (If $f \leq g$ on $[a, b]$ and both are integrable then $\int_{a}^{b} f \leq \int_{a}^{b} g$ ; and $m (b - a) \leq \int_{a}^{b} f \leq M (b - a)$ ). Continuous functions and constant functions on compact intervals are integrable (A continuous function on $[a, b]$ is Riemann integrable, by Heine-Cantor and Riemann's criterion, If $m \leq f \leq M$ on $[a, b]$ then $m (b - a) \leq L (f, P) \leq \underline{\int_{a}^{b}} f \leq \overline{\int_{a}^{b}} f \leq U (f, P) \leq M (b - a)$ for every partition $P$ ; in particular every constant function is integrable, with $\int_{a}^{b} c = c (b - a)$ ).

[F5]

The product rule for derivatives applies to $t \mapsto t \log t - t$ (Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ ).

Proof

1.1F1F2algebra

By [F1], $(\binom{d}{m}) = d^{\underline{m}} / m!$ . Every factor in $d^{\underline{m}} = \prod_{j = 0}^{m - 1} (d - j)$ lies between $0$ and $d$ , so $d^{\underline{m}} \leq d^{m}$ ; since $m! > 0$ by [F2], $(\binom{d}{m}) \leq d^{m} / m!$ .

1.2F2F3F4F5algebra

If $m = 1$ , then $\log (m!) = 0 \geq - 1 = m \log m - m$ by [F2]. If $m \geq 2$ , monotonicity of $\log$ in [F2] gives $\log t \leq \log (j + 1)$ on each interval $[j, j + 1]$ for $1 \leq j < m$ . The logarithm and each comparison constant are integrable there by [F2, F4], so monotonicity of the integral gives $\int_{1}^{m} \log t d t \leq \sum_{j = 2}^{m} \log j = \log (m!)$ . The antiderivative $t \log t - t$ has derivative $\log t$ by [F3, F5], so [F3] evaluates the integral as $m \log m - m + 1$ . Therefore $\log (m!) \geq m \log m - m + 1 \geq m \log m - m$ .

2.1F2step 1.1step 1.2algebra∎

By [F2], $\log ((m / e)^{m}) = m (\log m - \log e) = m \log m - m$ ; the power identity follows by induction from the logarithm product law. Step 1.2 and monotonicity of $\log$ therefore imply $(m / e)^{m} \leq m!$ . Combining this with step 1.1 gives $(\binom{d}{m}) \leq d^{m} (m / e)^{- m} = (e d / m)^{m}$ .

Depends on

Used by

BIC fitted-value risk bound Theorem
Sparse constrained least-squares risk bound Theorem

Dependency tree · two levels

103 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, Chapter 2, Lemma 2.7 (standard reference, not scraped)
Sylvain Arlot, Model/estimator selection, Lecture on model selection, §2 (standard reference, not scraped)