For every k, find n with $(n-k)(n-k+1)\cdots n$ dividing $\binom{2n}{n}$ (Erdős #396)
Statement
Is it true that for every $k$ there exists $n$ such that $$\prod_{0\leq i\leq k}(n-i)\ \Big|\ \binom{2n}{n}\,?$$ That is, for each fixed $k$, can the product of the $k+1$ consecutive integers $n-k,n-k+1,\ldots,n$ divide the central binomial coefficient $\binom{2n}{n}$?
Acceptance. FULLY RESOLVES: a proof that for every $k$ a witness $n$ exists (constructive or not), OR a proof that for some explicit $k$ no such $n$ exists. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. Note that any claimed witness for an individual $k$ is machine-checkable: verify $v_p\big(\prod_{0\leq i\leq k}(n-i)\big)\leq v_p\big(\binom{2n}{n}\big)$ for every prime $p\leq 2n$ via Legendre/Kummer valuations. ADVANCES: (a) new verified terms of OEIS A375077 — the least witness $n$ for values of $k$ strictly beyond the published terms of the sequence, with search code and per-witness divisibility certificates; (b) a proof that witnesses exist for infinitely many $k$, or for all $k$ in an explicit structured set; (c) quantitative refinements of Pomerance's density theorems (e.g. improving the upper density bound $1/3$ stated in the background). Deliver the proof file, or the search code plus the witness table and certificates.
Background
A problem of Erdős and Graham [ErGr80]; listed as open on erdosproblems.com/396 (fetched 2026-07-13, status 'open', tagged 'number theory | binomial coefficients'). The asymmetry driving the problem: $n+1$ always divides $\binom{2n}{n}$ (the quotient is the $n$th Catalan number), yet it is quite rare that $n$ itself divides $\binom{2n}{n}$ — downward shifts are the obstruction. Pomerance [Po14] proved that for any $k\geq 0$ there are infinitely many $n$ with $n-k\mid\binom{2n}{n}$, although the set of such $n$ has upper density $<1/3$; he also showed that the set of $n$ with $\prod_{1\leq i\leq k}(n+i)\mid\binom{2n}{n}$ (upward shifts) has density $1$. So single downward shifts and blocks of upward shifts are understood, while the full downward block of this problem is open. The smallest witness $n$ for each $k$ is recorded as OEIS A375077. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: per-$k$ witness searches using Kummer's theorem ($v_p(\binom{2n}{n})$ equals the number of carries when adding $n+n$ in base $p$) against Legendre valuations of the product, extending A375077; a full solution likely needs a construction of $n$ handling all relevant primes simultaneously.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #396 (T. F. Bloom) | website |
| REF-02 | OEIS A375077 — smallest n such that (n-k)(n-k+1)···n divides C(2n,n) | website |
| REF-03 | Formalised statement of Erdős #396 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.