Bertrandの仮説

$v_p(n!)=\sum_{j=1}^nv_p(j)$ であり、$v_p(j)$ は $p^k\mid j$ となる $k\geq1$ の個数に等しい。よって
$$ v_p(n!)=\sum_{j=1}^n\#\{k\geq1: p^k\mid j\}=\sum_{k\geq1}\#\{1\leq j\leq n: p^k\mid j\} $$
である。$1$ 以上 $n$ 以下の $p^k$ の倍数は $p^k,2p^k,\dots,\lfloor n/p^k\rfloor p^k$ の $\lfloor n/p^k\rfloor$ 個なので、主張を得る。$\square$

1：$\binom{2n}{n}=\dfrac{(2n)!}{(n!)^2}$ なので、lem-bertrand-postulate-legendre により $v=v_p((2n)!)-2v_p(n!)$ は式のとおりである。実数 $y\geq0$ について、$y=\lfloor y\rfloor+t$（$0\leq t<1$）と書くと $\lfloor2y\rfloor=2\lfloor y\rfloor+\lfloor2t\rfloor$ であり、$0\leq2t<2$ から $\lfloor2t\rfloor\in\{0,1\}$ である。$y=n/p^k$ とすれば各項が $0$ または $1$ であることが分かる。$p^k>2n$ なら $\lfloor2n/p^k\rfloor=\lfloor n/p^k\rfloor=0$ である。
2：$p^K\leq2n< p^{K+1}$ となる整数 $K\geq0$ をとると、1 により $0$ でない項は $k=1,\dots,K$ の高々 $K$ 個なので $v\leq K$ であり、$p^v\leq p^K\leq2n$ である。
3：$p>\sqrt{2n}$ なら $p^2>2n$ なので、1 により $k\geq2$ の項は $0$ であり、$v$ は $k=1$ の項だけで $v\leq1$ である。
4：3 により $v=\lfloor2n/p\rfloor-2\lfloor n/p\rfloor$ である。$\tfrac{2n}3< p\leq n$ から $1\leq n/p<\tfrac32$、$2\leq 2n/p<3$ なので、$\lfloor n/p\rfloor=1$、$\lfloor2n/p\rfloor=2$ であり、$v=2-2=0$ である。
5：$p>n\geq1$ と $p\geq2$ から $p^2>pn\geq2n$ なので、3 と同様に $v=\lfloor2n/p\rfloor-2\lfloor n/p\rfloor$ である。$n< p\leq2n$ から $\lfloor n/p\rfloor=0$、$1\leq2n/p<2$ から $\lfloor2n/p\rfloor=1$ なので $v=1$ である。$\square$

$0\leq j<2n$ について $\binom{2n}{j+1}\Big/\binom{2n}{j}=\dfrac{2n-j}{j+1}$ は $j\leq n-1$ のとき $1$ より大きく、$j\geq n$ のとき $1$ より小さい。よって $\binom{2n}{j}$（$0\leq j\leq2n$）の最大値は $\binom{2n}{n}$ である。また $n\geq1$ なら $\binom{2n}{0}+\binom{2n}{2n}=2\leq\binom{2n}{n}$ である（$\binom{2n}{n}\geq\binom{2n}{1}=2n\geq2$）。二項定理により
$$ 4^n=(1+1)^{2n}=\left(\binom{2n}{0}+\binom{2n}{2n}\right)+\sum_{j=1}^{2n-1}\binom{2n}{j}\leq\binom{2n}{n}+(2n-1)\binom{2n}{n}=2n\binom{2n}{n} $$
である。$\square$

$P(m):=\prod_{p\leq m}p$ とおき、$m$ に関する強い帰納法で示す。$m=1$ では $P(1)=1=4^0$、$m=2$ では $P(2)=2\leq4$ である。
$m\geq3$ とし、$m$ 未満では主張が成り立つとする。$m$ が偶数なら $m$ は素数でないので $P(m)=P(m-1)\leq4^{m-2}<4^{m-1}$ である。
$m=2r+1$（$r\geq1$）が奇数の場合を考える。$B:=\binom{2r+1}{r}=\dfrac{(2r+1)!}{r!\,(r+1)!}$ とおく。$r+2\leq p\leq2r+1$ を満たす素数 $p$ は、分子 $(2r+1)!$ を割るが、分母 $r!\,(r+1)!$ の因子はすべて $r+1$ 以下で $p$ より小さいので分母を割らない（素数 の記事の補題「Euclidの補題」）。よって $p\mid B$ であり、相異なる素数の積 $\prod_{r+2\leq p\leq2r+1}p$ も $B$ を割るので、その値は $B$ 以下である。一方 $\binom{2r+1}{r}=\binom{2r+1}{r+1}$ はどちらも $(1+1)^{2r+1}=2^{2r+1}$ の展開に現れる項なので $2B\leq2^{2r+1}$、すなわち $B\leq4^r$ である。帰納法の仮定を $r+1< m$ に使うと
$$ P(2r+1)=P(r+1)\prod_{r+2\leq p\leq2r+1}p\leq4^{r}\cdot4^{r}=4^{2r}=4^{m-1} $$
となる。$\square$

次の 11 個の数
$$ q_0=2,\ q_1=3,\ q_2=5,\ q_3=7,\ q_4=13,\ q_5=23,\ q_6=43,\ q_7=83,\ q_8=163,\ q_9=317,\ q_{10}=631 $$
はすべて素数であり（それぞれ平方根以下の素数で割り切れないことを確かめればよい。たとえば $631$ は $2,3,5,7,11,13,17,19,23$ のいずれでも割り切れず、$29^2=841>631$ である）、各 $i$ について $q_{i+1}<2q_i$ である（$3<4$、$5<6$、$7<10$、$13<14$、$23<26$、$43<46$、$83<86$、$163<166$、$317<326$、$631<634$）。
$n=1$ なら $p=q_0=2$ が $1<2\leq2$ を満たす。$2\leq n\leq511$ なら、$q_0=2\leq n<631=q_{10}$ なので、$q_i\leq n< q_{i+1}$ を満たす $i$（$0\leq i\leq9$）がただ 1 つある。このとき $p:=q_{i+1}$ について
$$ n< q_{i+1}<2q_i\leq2n $$
であり、$p$ は求める素数である。$\square$

$n\geq512$ とし、$n< p\leq2n$ を満たす素数がないと仮定する。
$\binom{2n}{n}$ は $(2n)!$ を割るので、その素因数はすべて $2n$ 以下である。$2n$ 以下の素数 $p$ を次の 4 つの組に分ける。

• (A) $p\leq\sqrt{2n}$
• (B) $\sqrt{2n}< p\leq\tfrac{2n}3$
• (C) $p>\sqrt{2n}$ かつ $\tfrac{2n}3< p\leq n$
• (D) $n< p\leq2n$
  各素数はちょうど 1 つの組に属する。lem-bertrand-postulate-central-exponent の 2、3、4 により、(A) の素数 $p$ では $p^{v_p}\leq2n$、(B) の素数では $v_p\leq1$、(C) の素数では $v_p=0$ である。仮定により (D) の素数はない。(A) の素数は $\sqrt{2n}$ 以下の正の整数なので高々 $\sqrt{2n}$ 個である。(B) の素数の積は $\lfloor 2n/3\rfloor$ 以下の素数の積以下なので、lem-bertrand-postulate-primorial により $4^{\lfloor2n/3\rfloor-1}\leq4^{2n/3}$ 以下である。したがって
  $$ \binom{2n}{n}=\prod_{p\leq2n}p^{v_p}\leq(2n)^{\sqrt{2n}}\cdot4^{2n/3} $$
  である。これと lem-bertrand-postulate-lower-bound を合わせると $4^n/(2n)\leq(2n)^{\sqrt{2n}}4^{2n/3}$、すなわち
  $$ 4^{n/3}\leq(2n)^{\sqrt{2n}+1} $$
  を得る。両辺の自然対数を取ると、実数 $x>0$ の関数
  $$ f(x):=\frac{x}{3}\log4-\left(\sqrt{2x}+1\right)\log(2x) $$
  について $f(n)\leq0$ となる。
  一方、$x\geq512$ で $f(x)>0$ であることを示す。$x=512$ では $2x=1024=2^{10}$、$\sqrt{2x}=32$ なので
  $$ f(512)=\frac{512}{3}\cdot2\log2-33\cdot10\log2=\left(\frac{1024}3-330\right)\log2=\frac{34}3\log2>0 $$
  である。また
  $$ f'(x)=\frac{\log4}3-\frac{\log(2x)}{\sqrt{2x}}-\frac{\sqrt{2x}+1}{x}=\frac{2\log2}3-\frac{\log(2x)+2}{\sqrt{2x}}-\frac1x $$
  である（$\sqrt{2x}/x=2/\sqrt{2x}$ を使った）。$g(t):=(\log t+2)/\sqrt t$ は $g'(t)=-\log t/(2t^{3/2})<0$（$t>1$）なので $t>1$ で減少し、$x\geq512$ では $g(2x)\leq g(1024)=(10\log2+2)/32$、$1/x\leq1/512$ である。よって $x\geq512$ で
  $$ f'(x)\geq\frac{2\log2}3-\frac{10\log2+2}{32}-\frac1{512}=\frac{17}{48}\log2-\frac{33}{512} $$
  であり、$\log2>0.69$ から右辺は $0.244-0.065>0$ である。したがって $f$ は $x\geq512$ で増加し、$f(x)\geq f(512)>0$ である。
  これは $f(n)\leq0$ に矛盾する。よって $n< p\leq2n$ を満たす素数が存在する。$\square$

thm-bertrand-postulate を $n=p_k$ に適用すると、$p_k< q\leq2p_k$ を満たす素数 $q$ がある。$2p_k$ は素数でないので $q<2p_k$ であり、$p_{k+1}$ は $p_k$ より大きい最小の素数なので $p_{k+1}\leq q<2p_k$ である。後半は $p_1=2$ から $k$ に関する帰納法で $p_{k+1}<2p_k\leq2^{k+1}$ として従う。$\square$

$m:=\lfloor n/2\rfloor\geq1$ に thm-bertrand-postulate を適用すると、$m< p\leq2m\leq n$ を満たす素数 $p$ がある。$p\geq m+1>n/2$ なので $2p>n$ であり、$1,\dots,n$ のうち $p$ の倍数は $p$ だけである。
$L$ を $1,2,\dots,n$ の最小公倍数とすると、$p\leq n$ なので $p\mid L$ であり、$p^2>p\cdot\tfrac n2\geq n$（$p\geq2$ による）なので $1,\dots,n$ のどれも $p^2$ で割り切れず、$v_p(L)=1$ である。$LH_n=\sum_{j=1}^nL/j$ を考えると、$j\neq p$ の項 $L/j$ は $p$ で割り切れ（$v_p(j)=0$ なので $v_p(L/j)=1$）、$j=p$ の項 $L/p$ は $p$ で割り切れない（$v_p(L/p)=0$）。よって $LH_n$ は $p$ で割り切れない。一方、$H_n$ が整数なら $LH_n$ は $L$ の倍数であり、$p$ で割り切れる。これは矛盾なので、$H_n$ は整数でない。$\square$

$h(x):=x/\log x$ とおくと、$x>1$ で
$$ \frac{h((1+\varepsilon)x)}{h(x)}=\frac{(1+\varepsilon)\log x}{\log x+\log(1+\varepsilon)}\to1+\varepsilon\quad(x\to\infty) $$
である。素数定理により $\pi(x)/h(x)\to1$、$\pi((1+\varepsilon)x)/h((1+\varepsilon)x)\to1$ なので
$$ \frac{\pi((1+\varepsilon)x)-\pi(x)}{h(x)}=\frac{\pi((1+\varepsilon)x)}{h((1+\varepsilon)x)}\cdot\frac{h((1+\varepsilon)x)}{h(x)}-\frac{\pi(x)}{h(x)}\to(1+\varepsilon)-1=\varepsilon>0 $$
である。よってある $x_0$ があって、$x\geq x_0$ では左辺が $\varepsilon/2$ 以上になり、$h(x)>0$ から $\pi((1+\varepsilon)x)-\pi(x)>0$、すなわち $(x,(1+\varepsilon)x]$ に素数がある。$\square$