伯特蘭-切比雪夫定理

Template:Distinguish Template:NoteTA 伯特蘭-切比雪夫定理說明：若整數 $n > 3$ ，則至少存在一個質數 $p$ ，符合 $n < p < 2 n - 2$ 。另一個稍弱說法是：對於所有大於1的整數 $n$ ，存在一個質數 $p$ ，符合 $n < p < 2 n$ 。

1845年約瑟·伯特蘭提出這個猜想。伯特蘭檢查了2至3×10⁶之間的所有數。1850年切比雪夫證明了這個猜想。拉馬努金給出較簡單的證明，而艾狄胥則借二項式係數給出了另一個簡單的證明。

證明

證明的方法是运用反證法，反設定理不成立，然后用两种方法估计 $(\binom{2 n}{n})$ 的上下界，得出矛盾的不等式

註：下面的證明中，都假設 $p$ 屬於質數集。

不等式1

這條不等式是關於 $(\binom{2 n}{n})$ 的下界的。

對於正整數 $n$ ， $(\binom{2 n}{n}) \geq \frac{4^{n}}{2 n}$

證明：

對於

k \leq 2 n

，

(\binom{2 n}{n}) \geq (\binom{2 n}{k})

若

k \neq n

，

(\binom{2 n}{n}) > (\binom{2 n}{k})

因此

2 n (\binom{2 n}{n}) \geq \sum_{i = 1}^{2 n} (\binom{2 n}{i}) + 1 = 2^{2 n} = 4^{n}

引理1

$\prod_{k + 1 < p \leq 2 k + 1} p < 4^{k}$

证明：注意到所有大于 k+1 而小于 2k+1 的质数都在(2k+1)! 中而不在(k+1)! 或 k！中，于是 $\prod_{k + 1 < p \leq 2 k + 1} p$ 是 $(\binom{2 k + 1}{k + 1})$ 的因子。

\prod_{k + 1 < p \leq 2 k + 1} p | (\binom{2 k + 1}{k + 1})

同时又有

2 (\binom{2 k + 1}{k + 1}) = (\binom{2 k + 1}{k + 1}) + (\binom{2 k + 1}{k}) < \sum_{i = 0}^{2 k + 1} (\binom{2 k + 1}{i}) = 2 \cdot 4^{k}

于是就有

\prod_{k + 1 < p \leq 2 k + 1} p \leq (\binom{2 k + 1}{k + 1}) < 4^{k}

定理1

這個定理和 $(\binom{2 n}{n})$ 的上界有關。

對於所有正整數 $n$ ， $\prod_{p \leq n} p < 4^{n}$

數學歸納法：

當 $n = 2$ ，2 < 16，成立。

假設對於所有少於 $n$ 的整數，敘述都成立。

顯然，若n>2且n是偶數， $\prod_{p \leq n} p = \prod_{p \leq n - 1} p$ 。对于奇数的n，设n=2k+1。

從引理1和歸納假設可得：

$\prod_{p \leq n} p = \prod_{p \leq 2 k + 1} p = \prod_{p \leq k + 1} p \cdot \prod_{k + 1 < p \leq 2 k + 1} p < 4^{k + 1} \cdot 4^{k} = 4^{2 k + 1} = 4^{n}$

系理1

首先的定理：

若 $p$ 是質數， $n$ 是整數。設 $s$ 是最大的整數使得 $p^{s} | n!$ ，則 $s = \sum_{i = 1}^{\infty} [\frac{n}{p^{i}}]$

下面這些系理和 $(\binom{2 n}{n})$ 的上界有關。

若 $p$ 為質數，設 $s_{p}$ 是最大的整數使得 $p^{s_{p}}$ 整除 $(\binom{2 n}{n})$ ，則：

s_{p} = \sum_{i \geq 1} ([\frac{2 n}{p^{i}}] - 2 [\frac{n}{p^{i}}])

對於所有 $x > 0$ ， $[2 x] - 2 [x] \leq 1$ ，所以

s_{p} = \sum_{i \geq 1} ([\frac{2 n}{p^{i}}] - 2 [\frac{n}{p^{i}}]) \leq m a x {r | p^{r} \leq 2 n}

于是得到三个上界：

$p^{s_{p}} \leq 2 n$
若 $\sqrt{2 n} < p$ ， $s_{p} \leq 1$
若 $2 n / 3 < p \leq n$ ， $s_{p} = 0$ （因为 2n! 中只有两个 p，在 n! 中恰有一个 p）

核心部分

假設存在大於1的正整數 $n$ ，使得沒有質數 $p$ 符合 $n < p < 2 n$ 。根據系理1.2和1.3：

$(\binom{2 n}{n}) = \prod_{p \leq 2 n} p^{s_{p}} = \prod_{p \leq 2 n / 3} p^{s_{p}} \leq \prod_{p \leq \sqrt{2 n}} p^{s_{p} - 1} \cdot \prod_{p \leq 2 n / 3} p$

再根據系理1.1和定理1： $(\binom{2 n}{n}) \leq$ 上式最右方 $< (2 n)^{\sqrt{2 n} / 2 - 1} \cdot 4^{2 n / 3}$

結合之前關於 $(\binom{2 n}{n})$ 的下界的不等式1：

(2 n)^{- 1} 4^{n} < (\binom{2 n}{n}) < (2 n)^{\sqrt{2 n} / 2 - 1} \cdot 4^{2 n / 3}

4^{n} < (2 n)^{\sqrt{2 n} / 2} \cdot 4^{2 n / 3}

4^{2 n / 3} < (2 n)^{\sqrt{2 n}}

兩邊取2的對數，并设 $x = \sqrt{2 n}$ ：

x \ln 2 - 3 \ln x < 0

。

顯然 $x \geq 16$ ，即 $n \geq 128$ 時，此式不成立，得出矛盾。因此 $n \geq 128$ 時，伯特蘭—切比雪夫定理成立。

再在 $n < 128$ 時驗證這個假設即可。

參考

外部連結

Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate Template:Wayback, Lawrence E. Greenfield

伯特蘭-切比雪夫定理

目录

相關定理

西爾維斯特定理

艾狄胥定理

證明

不等式1

引理1

定理1

系理1

核心部分

參考

外部連結

导航菜单

伯特蘭-切比雪夫定理

相關定理

西爾維斯特定理

艾狄胥定理

證明

不等式1

引理1

定理1

系理1

核心部分

參考

外部連結

导航菜单

搜索