数论难题a(n)表示前n个正整数的最小共倍数,证明a(n)>=2^(n-1)

数论难题a(n)表示前n个正整数的最小共倍数,证明a(n)>=2^(n-1)

这个结论挺有意思的,算是质数分布相关的一个初等结果吧.
事实上我的证明也是从Bertrand假设的证明方法入手的.
首先约定几个记号:[x]表示不超过x的最大整数,即成立[x] ≤ x < [x]+1.
C(n,k)表示n中选k的组合数,也即C(n,k) = n!/(k!(n-k)!).
r(n,p)为不超过n的p的方幂的最大指数,可知r(n,p) = [ln(n)/ln(p)],即满足p^r(n,p) ≤ n < p^(r(n,p)+1).
s(n,p)表示n的标准分解式中p的指数,即p^s(n,p) | n而p^(s(n,p)+1)不整除n.
(后两个记号都不是标准的.)
易知a(n) = ∏{p为质数} p^r(n,p),乘积取遍所有质数 (但只有有限项是1).
由此表达式可知,若n不是质数的方幂,则a(n) = a(n-1).
特别的,当n为偶数且不是2的方幂,有a(n) = a(n-1).
而当n为2的方幂,可知a(n) = 2a(n-1).
综合两种情况,当n为偶数,有a(n-1) ≥ a(n)/2.
如果对n为偶数的情况证明了a(n) ≥ 2^(n-1),则有a(n-1) ≥ a(n)/2 ≥ 2^(n-2),即对奇数的情况也成立.
于是只需对偶数情况证明.
证明的关键结论是n·C(2n,n) | a(2n).
主要用到n!的标准分解式:对质数p,有s(n!,p) = ∑{1 ≤ k} [n/p^k].
这是一个基本结论,证明就是计数,这里就不写了.
于是对C(2n,n) = (2n)!/(n!)²有s(C(2n,n),p) = ∑{1 ≤ k} [2n/p^k]-2·[n/p^k].
仔细分析一下[2n/p^k]-2·[n/p^k]:
当k > r(2n,p),有0 < n/p^k < 2n/p^k < 1,于是[2n/p^k]-2·[n/p^k] = 0.
而当k ≤ s(n,p),有p^k | n,于是[2n/p^k]-2·[n/p^k] = 2n/p^k-2·n/p^k = 0.
所以求和中真正有效的是s(n,p)+1 ≤ k ≤ r(2n,p)的部分.
而[2n/p^k]-2·[n/p^k] < (2n/p^k)-2·(n/p^k-1) = 2.
又[2n/p^k]-2·[n/p^k]为整数,故[2n/p^k]-2·[n/p^k] ≤ 1.
于是s(C(2n,n),p) = ∑{1 ≤ k} [2n/p^k]-2·[n/p^k]
= ∑{s(n,p)+1 ≤ k ≤ r(2n,p)} [2n/p^k]-2·[n/p^k]
≤ r(2n,p)-s(n,p).
即s(n·C(2n,n),p) = s(C(2n,n),p)+s(n,p) ≤ r(2n,p).
因此n·C(2n,n) = ∏{p为质数} p^s(n·(2n,n),p) | ∏{p为质数} p^r(2n,p) = a(2n).
可得n·C(2n,n) ≤ a(2n).
最后只需证明n·C(2n,n) ≥ 2^(2n-1),即2n·C(2n,n) ≥ 2^(2n).
只需注意到2n·(2n)!= 2·3·4·5·...·(2n-1)·2n·2n
≥ 2·2·4·4·...·(2n-2)·2n·2n = 2^(2n)·(n!)²,即得2n·C(2n,n) ≥ 2^(2n).
这样就完成了证明.