ErdösによるSylvester-Schurの定理の証明とBertrand-Chebyshevの定理

　$\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$だから，Legendreの定理より
$$a = \sum_{i=1}^{\infty} \left( \left\lfloor \frac{n}{p^i} \right\rfloor - \left\lfloor \frac{k}{p^i} \right\rfloor - \left\lfloor \frac{n-k}{p^i} \right\rfloor \right)$$
が従う．ここで，任意の$i$について$\left\lfloor \dfrac{n}{p^i} \right\rfloor - \left\lfloor \dfrac{k}{p^i} \right\rfloor - \left\lfloor \dfrac{n-k}{p^i} \right\rfloor$は$0$か$1$のいずれかをとり，$p^i>n \iff i > \log_p n$のときは常に$\left\lfloor \dfrac{n}{p^i} \right\rfloor - \left\lfloor \dfrac{k}{p^i} \right\rfloor - \left\lfloor \dfrac{n-k}{p^i} \right\rfloor = 0$となるから，
$$a \leq \sum_{i=1}^{\log_p n}1 = \log_p n$$
となり補題は成立する．

　素数$p$に対して$\lfloor\sqrt[l]{n}\rfloor < p \leq \lfloor\sqrt[l]{2n}\rfloor$，つまり$\sqrt[l]{n} < p \leq \sqrt[l]{2n}$を満たす正整数$l$が存在するとき，$n< p^l \leq 2n$である．ここで，Legendreの定理より
\begin{align*} v_p\left(\dbinom{2n}{n}\right) &= \left( \left\lfloor \frac{2n}{p} \right\rfloor + \cdots + \left\lfloor \frac{2n}{p^{l-1}} \right\rfloor + \left\lfloor \frac{2n}{p^l} \right\rfloor \right) - 2\left( \left\lfloor \frac{n}{p} \right\rfloor + \cdots + \left\lfloor \frac{n}{p^{l-1}} \right\rfloor \right) \\ &= \left( \left\lfloor \frac{2n}{p}\right\rfloor - 2\left\lfloor \frac{n}{p}\right\rfloor \right) + \cdots + \left( \left\lfloor \frac{2n}{p^{l-1}}\right\rfloor - 2\left\lfloor \frac{n}{p^{l-1}}\right\rfloor \right) + \left\lfloor \frac{2n}{p^l} \right\rfloor \end{align*}
が成立する．
　このとき，任意の$1 \leq i \leq k-1$に対して$\left\lfloor \dfrac{2n}{p^{i}}\right\rfloor \geq 2\left\lfloor \dfrac{n}{p^{i}}\right\rfloor$であり，$\left\lfloor \dfrac{2n}{p^l} \right\rfloor = 1$だから$ v_p\left(\dbinom{2n}{n}\right) \geq 1$．よって$\dbinom{2n}{n}$は$p$で割り切れる．

　数列$\{a_i\}$は広義単調減少だから，$\{\lfloor \sqrt[l]{a_i} \rfloor\}$,$\{\lfloor \sqrt[l]{2a_i} \rfloor\}$も広義単調減少である．
　ここで，$\lfloor \sqrt[l]{a_m} \rfloor = 1$であり，$2a_1 = 2\left\lceil \dfrac{n}{2} \right\rceil \geq n$より$ \lfloor \sqrt[l]{2a_1} \rfloor \geq \lfloor \sqrt[l]{n} \rfloor$である．
　また，任意の$1< i< m$に対して$ \left\lceil \dfrac{n}{2^i} \right\rceil \leq 2\left\lceil \dfrac{n}{2^{i+1}} \right\rceil$，すなわち$a_i \leq 2a_{i+1}$が成立するから$\lfloor \sqrt[l]{a_i} \rfloor \leq \lfloor \sqrt[l]{2a_{i+1}} \rfloor$が従う．
　よって
$$\bigcup_{i=1}^m \left(\lfloor \sqrt[l]{a_i} \rfloor, \lfloor \sqrt[l]{2a_i} \rfloor \right] \supseteq \left(1,\lfloor \sqrt[l]{n} \rfloor \right]$$
が示された．

　補題4より，右辺は$\lfloor \sqrt[l]{a_i} \rfloor < p \leq \lfloor \sqrt[l]{2a_i} \rfloor$($i,l$は正整数，$1 \leq i \leq m$)を満たす素数$p$で割り切れる．ここで，補題5より，右辺は$1 < p \leq \lfloor \sqrt[l]{n} \rfloor$，つまり$1 < p \leq \sqrt[l]{n}$($l$は正整数)を満たす素数$p$で割り切れる．
　ここで，$m_i$を$2^{m_i} \geq a_i$を満たす最小の自然数とすると，$1 \leq l < m_i$のとき$\sqrt[l+1]{2a_i} \leq \sqrt[l]{a_i}$となるから，$(\sqrt[l+1]{a_i},\sqrt[l+1]{2a_i}\,] \, \cap \, (\sqrt[l]{a_i},\sqrt[l]{2a_i}\,] = \varnothing$となる．また，$l \geq m_i$のとき$\lfloor \sqrt[l]{a_i} \rfloor < p \leq \lfloor \sqrt[l]{2a_i} \rfloor$を満たす素数$p$は存在しない．
　よって，右辺は$\prod_{\substack{p \leq n \\ p \in \P}}p$で割り切れ，右辺を$\prod_{\substack{p \leq n \\ p \in \P}}p$で割ったものは$\prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p$で割り切れ，右辺を$\prod_{\substack{p \leq n \\ p \in \P}}p \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p$で割ったものは$\prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p$で割り切れ，…となる．つまり右辺は$\prod_{\substack{p \leq n \\ p \in \P}}p \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots$で割り切れる．従って
$$\prod_{\substack{p \leq n \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m}$$
が成立する．

　$n < 10$のときは調べると分かる．
　$n \geq 10$のときを考える．$n$未満の任意の正整数で式(1)が成立すると仮定する．
　ここで，式(1)において$n = 2a_2 - 1$とすると
$$ \binom{2a'_1}{a'_1} \binom{2a'_2}{a'_2} \cdots \binom{2a'_{m'}}{a'_{m'}} \leq 4^{2a_2 - 1}$$
となる．ただし，$a'_i = \left\lceil \dfrac{2a_2 - 1}{2^i} \right\rceil$，$m'$を$2^{m'} \geq 2a_2-1$を満たす最小の正整数とおいた．このとき，
$$a'_i = \left\lceil \frac{2a_2 - 1}{2^i} \right\rceil = \left\lceil \frac{1}{2^{i-1}}\left\lceil \frac{n}{2^2} \right\rceil - \frac{1}{2^i}\right\rceil = \left\lceil \frac{n}{2^{i+1}} \right\rceil = a_{i+1}$$
であり，$m' = m-1$であるから，この式は
$$ \binom{2a_2}{a_2} \binom{2a_3}{a_3} \cdots \binom{2a_m}{a_m} \leq 4^{2a_2 - 1} \iff \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq \binom{2a_1}{a_1} 4^{2a_2 - 1}$$
と書ける．
　また，$n \geq 10$より$a_n \geq 5$であり，正整数$l \geq 5$に対して$\dbinom{2l}{l} < 4^{l-1}$が成立するから（これは数学的帰納法により示せる），この式は
$$ \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq 4^{a_1 + 2a_2 - 2}$$
と書ける．ここで，$2a_1 \leq n+1$，$2a_2 \leq a_1+1$より$a_1 + 2a_2 - 2 \leq 2a_1-1 \leq n$となるから
$$ \binom{2a_1}{a_1} \binom{2a_2}{a_2} \cdots \binom{2a_m}{a_m} \leq 4^n$$
が従う．よって，任意の$n$に対して式(1)が成立することが示された．

　補題6，補題7より従う．

　$N$以下の素数$p$を考える．$p^l \leq n < p^{l+1}$を満たす正整数$l$をとると，$\sqrt[l+1]{n} < p \leq \sqrt[l]{n}$が従うから
$$v_p \left( \prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \right) = l$$
となる．一方，$a = {v_p\left(\dbinom{n}{k}\right)}$ とおくと，命題3より$p^a \leq n$となるので$a \leq l$．
　つまり，任意の$N$以下の素数$p$に対して
$$ v_p\left(\dbinom{n}{k}\right) \leq v_p \left( \prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \right) $$
が成立するから補題は従う．

　$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定する．
　$k\ \geq 33$のとき$\pi(k) \leq \dfrac{1}{3}k$だから，命題3より
$$\binom{n}{k} = \prod_{\substack{p\leq k \\ p \in \P}} p^{v_p{(\binom{n}{k})}} \leq \prod_{\substack{p\leq k \\ p \in \P}} n = n^{\pi(k)} \leq n^{\frac{1}{3}k}$$
となる．
一方，
$$\binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \cdots \cdot \frac{n-k+1}{1} > \left( \frac{n}{k} \right)^{k}$$
が成立する．これより
$$\left( \frac{n}{k} \right)^{k} < n^{\frac{1}{3}k} \iff n^{\frac{2}{3}k} < k^k$$
が従うが，これは$k \leq n^{\frac{2}{3}}$に矛盾する．よって示された．

　命題8より
$$\prod_{\substack{p \leq N \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{N} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{N} \\ p \in \P}}p \cdot \cdots \leq 4^N\tag{2}$$
が成立する．
　式(2)に$N = \lfloor \sqrt{n} \rfloor$を代入して
$$\prod_{\substack{p \leq \lfloor \sqrt{n} \rfloor \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \lfloor \sqrt[4]{n} \rfloor \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \lfloor \sqrt[6]{n} \rfloor \\ p \in \P}}p \cdot \cdots \leq 4^{\lfloor \sqrt{n} \rfloor}$$
となる．ここで，$p$が素数のとき$p \leq \lfloor \sqrt[2l]{n} \rfloor \iff p \leq \sqrt[2l]{n}$であり，$4^{\lfloor \sqrt{n} \rfloor} \leq 4^\sqrt{n}$だから
$$\prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[4]{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[6]{k} \\ p \in \P}}p \cdot \cdots \leq 4^\sqrt{n}\tag{3}$$
となる．
　また，$k>n^\frac{2}{3}$のとき，任意の$l \geq 2$に対して$\sqrt[l]{k} \geq \sqrt[2l-1]{n}$となるから，式(2)より
$$\prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[5]{n} \\ p \in \P}}p \cdot \cdots \leq 4^k\tag{4}$$
となる．
　よって，式(3)と式(4)より
$$\prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots \leq 4^{k+\sqrt{n}}$$
が成立することが示された．

　任意の正整数$k$に対して$\dbinom{2k}{k} \geq \dfrac{4^k}{2k}$が成立することが数学的帰納法により分かる．
　ここで，
$$\dbinom{n}{k} \geq \dbinom{4k}{k} = \dbinom{2k}{k} \frac{4k}{2k} \frac{4k-1}{2k-1} \cdots \frac{3k+1}{k+1} \geq \frac{4^k}{2k} \cdot 2^k = \frac{8^k}{2k}$$
と評価できる．
　さて，$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定すると，命題9より
$$\dbinom{n}{k} \leq \prod_{\substack{p \leq k \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots$$
が成立する．これと補題11より$\dbinom{n}{k} \leq 4^{k+\sqrt{n}}$が従うから，
$$\frac{8^k}{2k} \leq 4^{k+\sqrt{n}} \iff \frac{2^k}{2k} \leq 4^\sqrt{n}$$
となる．ここで，$k \geq 33$で$2^{\frac{1}{3}k} > 2k$が従うから，$2^{\frac{2}{3}k} \geq 2^{2\sqrt{n}}$，つまり$k \geq 3\sqrt{n}$が成立する．一方，$k > n^\frac{2}{3}$であるから$n^\frac{2}{3} < 3\sqrt{n}$となる．
　しかし，これは$n \geq 900$では成立せず矛盾．よって示された．

$$\binom{n}{k} \geq \binom{\left\lfloor \frac{5}{2}k \right\rfloor}{k} = \binom{2k}{k} \frac{\left\lfloor \frac{5}{2}k \right\rfloor}{2k} \frac{\left\lfloor \frac{5}{2}k \right\rfloor -1}{2k-1} \cdots \frac{\left\lfloor \frac{5}{2}k \right\rfloor -k+1}{k+1} \geq \frac{4^k}{2k} \left( \frac{5}{4} \right)^k$$
と評価できる．
一方，$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定すると，命題12の証明と同様にして$\dbinom{n}{k} \leq 4^{k+\sqrt{n}}$が従う．これより
$$\frac{4^k}{2k} \left( \frac{5}{4} \right)^k \leq 4^{k+\sqrt{n}} \iff \left( \frac{5}{4} \right)^k \leq 2k \cdot 4^\sqrt{n}$$
となる．ここで，$n < 4k$より$\left( \dfrac{5}{4} \right)^k < 2k \cdot 4^\sqrt{4k}$となり，これは$k<205$で成立する．しかし，これは$n \geq 900$に矛盾する．よって示された．

$$\dbinom{n}{k} \geq \dbinom{2k}{k} \geq \frac{4^k}{2k}$$
と評価できる．
　ここで，素数$p \leq k$が$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$を割り切るとすると，$v_p(k! \, (n-k)!) \geq 2$より$v_p(n!) \geq 3$である必要がある．だから$p \leq \dfrac{1}{3}n$となる（$p=2$のときも$n \geq 33$より従う）．
　これより，$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定すると，$\dbinom{n}{k}$の素因数は$\dfrac{1}{3}n$より大きな素因数をもたないから，命題9において$N = \left\lfloor \dfrac{1}{3}n \right\rfloor$とし，補題11も用いて
$$\dbinom{n}{k} \leq \prod_{\substack{p \leq \left\lfloor \frac{1}{3}n \right\rfloor \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots = \prod_{\substack{p \leq \frac{1}{3}n \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt{n} \\ p \in \P}}p \, \cdot \prod_{\substack{p \leq \sqrt[3]{n} \\ p \in \P}}p \cdot \cdots < 4^{\frac{1}{3}n + \sqrt{n}} \leq 4^{\frac{5}{6}k + \sqrt{n}}$$
が成立する．これより
$$\frac{4^k}{2k} < 4^{\frac{5}{6}k + \sqrt{n}} \iff 4^{\frac{1}{6}k} < 2k \cdot 4^\sqrt{n}$$
となる．ここで，$2k \leq n < 4^\sqrt{n}$，$k \geq \dfrac{2}{5}n$だから
$$4^{\frac{1}{15}n} < 4^{2\sqrt{n}} \iff n< 30\sqrt{n}$$
となるが，これは$n \geq 900$では成立せず矛盾．よって示された．

　今$k \geq 33$を仮定しているので，$66 \leq n < 900$について考えればよいが，この範囲に連続$33$数が合成数となる区間は存在しないので（これは素数表を見れば分かる），連続する$k$数を選べば常に素数が含まれる．よって示された．

　$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定する．
　$k \geq 8$のとき$\pi(k) \leq \dfrac{1}{2}k$だから，命題3より
$$\binom{n}{k} = \prod_{\substack{p\leq k \\ p \in \P}} p^{v_p{(\binom{n}{k})}} \leq \prod_{\substack{p\leq k \\ p \in \P}} n = n^{\pi(k)} \leq n^{\frac{1}{2}k}$$
となる．一方，
$$\binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \cdots \cdot \frac{n-k+1}{1} > \left( \frac{n}{k} \right)^{k}$$
が成立する．これより
$$\left( \frac{n}{k} \right)^{k} < n^{\frac{1}{2}k} \iff n^{\frac{1}{2}k} < k^k$$
が従うが，これは$k \leq \sqrt{n}$に矛盾する．よって示された．

　$k > \sqrt{n}$のとき，$n < k^2 \leq 32^2 = 1024$である．これと$n \geq 2k$より$16 \leq n <1024$について考えればよい．
　ここで，この範囲における素数または$37$以上の素因数をもつ整数の列を考えると，隣り合う$2$数の差が$8$以上になるものが存在しないことが分かる．よって示された．

• $k=1$のときは自明に成立する．
• $k=2$のとき
  　$4$以上の正整数$n,n-1$のうちいずれか$1$つは$3$以上の奇数だから示された．
• $k=3$のとき
  　$6$以上の正整数$n$に対して$n,n-1,n-2$が$2,3$以外の素因数をもたないと仮定する．
  　$n$が奇数のとき，$n$は$3^i$の形で表せる必要があるが，このとき，$n-2$は$3$で割り切れない奇数となるので矛盾．
  　$n$が偶数のとき，$n-1$は奇数だから$n-1$は$3^i$の形で表せる必要がある．このとき，$n,n-2$は$3$を素因数にもたないのでともに$2^i$の形で表せる必要があるが，これを満たす$n \geq 6$は存在しないので矛盾．よって示された．
• $k=4$のとき
  　$8$以上の正整数$n$に対して$n,n-1,n-2,n-3$が$2,3$以外の素因数をもたないと仮定する．
  　このとき，いずれか$2$つは奇数であり，それらは$3^i$の形で表せる必要があるが，ともに$3$の倍数になることはないので矛盾．よって示された．
• $k=5$のとき
  　$10$以上の正整数$n$に対して$n,n-1,n-2,n-3,n-4$が$2,3,5$以外の素因数をもたないと仮定する．
  　$n,n-2,n-4$が奇数のとき，この中で$3$の倍数と$5$の倍数はそれぞれ高々$1$つだから，いずれか$1$つは$3$の倍数でも$5$の倍数でもない奇数となる．これは矛盾．
  　$n-1,n-3$が奇数のとき，一方は$3^i$の形で，もう一方は$5^i$の形で表される必要がある．このとき，$n,n-2,n-4$は$3,5$を素因数にもたないので全て$2^i$の形で表せる必要があるが，このような$n$は存在せず矛盾．よって示された．

　$\dbinom{n}{k}$の素因数が全て$k$以下であると仮定する．
　$k =6,7$のとき$\pi(k) \leq \dfrac{4}{7}k$だから，命題3より
$$\binom{n}{k} = \prod_{\substack{p\leq k \\ p \in \P}} p^{v_p{(\binom{n}{k})}} \leq \prod_{\substack{p\leq k \\ p \in \P}} n = n^{\pi(k)} \leq n^{\frac{4}{7}k}$$
となる．一方，
$$\binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \cdots \cdot \frac{n-k+1}{1} > \left( \frac{n}{k} \right)^{k}$$
が成立する．これより
$$\left( \frac{n}{k} \right)^{k} < n^{\frac{4}{7}k} \iff n^{\frac{3}{7}k} < k^k$$
が従うが，これは$k \leq \sqrt{n}$に矛盾する．よって示された．

　$k > n^\frac{3}{7}$のとき，$n < k^\frac{7}{3} \leq 7^\frac{7}{3} < 94$である．これと$n \geq 2k$より$12 \leq n <94$について考えればよい．このとき，この範囲に連続$6$数が合成数となる区間は存在しないので（これも素数表を見れば分かる），連続する$k$数を選べば常に素数が含まれる．よって示された．

　定理1において$n = 2k$とし，$k$を$n$に替えると，$2n,2n-1,\ldots,n+1$の中で$n$より大きな素因数$p$をもつものが存在することが分かる．これを$N$とする．
　ここで，$N \neq p$とすると，$N$は$p$の倍数だから$N \geq 2p \geq 2(n+1)$となるが，これは$N$が$2n,2n-1,\ldots,n+1$のうちのいずれかであることに矛盾する．つまり$N=p$．これは$n < p \leq 2n$を満たす素数$p$が存在することに他ならない．