CSU 计算机数学作业解决方案 III（参考：特定数学）
Problem 1.
(a) 给出 π ( 2 n ) π(2n) π(2n)的下界
( 2 n ) π ( 2 n ) ≥ C 2 n n ≥ 2 2 n 2 n (2n)^{π(2n)}\geq{}C_{2n}^n\geq{}\frac{2^{2n}}{2n} (2n)π(2n)≥C2nn≥2n22n
对不等式两端取对数则有
π
(
2
n
)
l
o
g
2
(
2
n
)
≥
2
n
l
o
g
2
(
2
)
−
l
o
g
2
(
2
n
)
π
(
2
n
)
≥
2
n
l
o
g
2
2
n
−
1
π(2n)log_2(2n)\geq{}2nlog_2(2)-log_2(2n)\\ π(2n)\geq{}\frac{2n}{log_22n}-1
π(2n)log2(2n)≥2nlog2(2)−log2(2n)π(2n)≥log22n2n−1
(b) 给出 π ( 2 n ) π(2n) π(2n)的上界
( n ) π ( 2 n ) − π ( n ) ≤ C 2 n n ≤ 2 2 n (n)^{π(2n)-π(n)}\leq{}C_{2n}^n\leq{}2^{2n} (n)π(2n)−π(n)≤C2nn≤22n
对不等式两端取对数有
π
(
2
n
)
−
π
(
n
)
≤
2
n
l
o
g
2
n
π(2n)-π(n)\leq\frac{2n}{log_2n}
π(2n)−π(n)≤log2n2n
假设有
π
(
n
)
≤
4
n
l
o
g
2
n
π(n)\leq{}\frac{4n}{log_2n}
π(n)≤log2n4n,下面使用数学归纳法证明
（1） n = 1 , 2 , 3 n=1,2,3 n=1,2,3时，可以验证该假设成立
（2）假设 x < n x<n x<n时有 π ( x ) ≤ 4 x l o g 2 x π(x)\leq{}\frac{4x}{log_2x} π(x)≤log2x4x成立，当 x = n x=n x=n时有
1. n = 2 k n=2k n=2k
π ( n ) = π ( 2 k ) ≤ π ( k ) + 2 k l o g 2 k ≤ 4 k l o g 2 k + 2 k l o g 2 k = 6 k l o g 2 k = 3 n l o g 2 n 2 ≤ 4 n l o g 2 n ( 1 ) \begin{aligned} π(n)=π(2k)&\leq{}π(k)+\frac{2k}{log_2k}\\ &\leq{}\frac{4k}{log_2k}+\frac{2k}{log_2k}\\ &=\frac{6k}{log_2k}\\ &=\frac{3n}{log_2\frac{n}{2}}\\ &\leq{}\frac{4n}{log_2n} \quad\quad(1) \end{aligned} π(n)=π(2k)≤π(k)+log2k2k≤log2k4k+log2k2k=log2k6k=log22n3n≤log2n4n(1)
1. n = 2 k + 1 n=2k+1 n=2k+1
π
(
n
)
=
π
(
2
k
+
1
)
≤
π
(
2
k
)
+
1
≤
6
k
l
o
g
2
k
+
1
=
3
n
l
o
g
2
n
2
+
1
≤
4
n
l
o
g
2
n
(
2
)
\begin{aligned} π(n)=π(2k+1)&\leq{}π(2k)+1\\ &\leq{}\frac{6k}{log_2k}+1\\ &=\frac{3n}{log_2\frac{n}{2}}+1\\ &\leq{}\frac{4n}{log_2n} \quad\quad(2) \end{aligned}
π(n)=π(2k+1)≤π(2k)+1≤log2k6k+1=log22n3n+1≤
上一篇：
简单的数学作业
下一篇：
C 博客作业 02 - 循环结构