38.8
(a) n10/2n=exp{-n log2[1-(10/log2)log n/n]}→0 (n→∞)。
(b) 2n/n!=∏1≤k≤ n 2/k<2·1·(2/3)n-2→0 (n→∞)。
(c) n!/2n2=∏1≤k≤ n k/2n<nn/2n2=exp[-n2(log2- log n/n)]→0 (n→∞)。
(d) 定義式によりf(n)=ο(1)ならlim n→∞f(n)=0。したがって(i)と(iii)がο(1)。
38.9
(a)
(i) |n2-n|=|n(n-1)|≥n (n≥2)なのでn2-n＝Ω(n)
(ii) n!/2n>(1/2)·1·(3/2)n-2≥(1/2)·1 (n≥3)なのでn!＝Ω(2n)。
(iii) (5n-3n)/2n=1+nC1·(3/2)+...+nCn-1·(3/2)n-1≥1+nC1+...+nCn-1=2n-1≥(1/2)·2n (n≥1)
なので(5n-3n)/2n＝Ω(2n)。
(b)
ある正定数C1, C2が存在して|f(n)|≥C1|h(n)|, |h(n)|≥C2|k(n)|だから
|f(n)|≥C1C2|k(n)|なのでf(n)＝Ω(k(n))。
(c)
ある正定数Cが存在して|f(n)|≥C|h(n)|なので|h(n)|≤(1/C)|f(n)|だから
h(n)＝O(f(n))となり成り立つ。
(d)
|n3-3n2+7|/nd=n3-d-3n2-d +7n-d ≥C>0が
十分大きな全てのnについて成り立つために
3-d≥0でなければならないからd=0,1,2,3。
(e)
d≤0で√n=Ω(log2 n)d)は明らかに成り立つ。d>0に対しては、
√n/(log2 n)d=exp{(1/2)log n[1-2d log(log n)/log n]+d log(log2)}
log(log n)/log n→0 (n→∞)だから、任意に小さい正定数ε/dに対しあるn0が存在して、
n≥n0なる全てのnに対しlog(log n)/log n<ε/d
となる。したがってn≥n0なる全てのnに対し√n/(log2 n)d>(log2)dn1/2-ε>(log2)dだから、
d>0に対し√n=Ω(log2 n)d)は成り立つ。
したがって、すべての整数dについて成り立つ。
(f)
f(n)=Ω(√n)と仮定すると、n≥n0なる全てのnに対し
|n sin n/√n|=|√n sin n|≥C (1)となる自然数n0と正定数Cが存在する。
一方、定理31.2により、|n-2πm|<1/mの整数解(n,m)は無数に存在する。
n≥n0となる解(n,m)を十分大きくとると|sin 1/m|<1/m、
またn/m-2π≤|n/m-2π|<1/m2よりn/m<2π+1/m2で、
さらにこの二次不等式からm>n/(4π)なので、
C≤|√n sin n|=|√n sin(n-2πm)|<√n/m
=(1/√m)√(n/m)< (1/√m)√(2π+1/m2)<√(3π/m)<√(12π2/n)。
これよりn<12π2/C2となるから、n≥n0なる全てのnに対し(1)が成り立つことと矛盾する。
したがって、f(n)=Ω(√n)でない。
38.10
(a)
|log(1+1/n)|=|1/n-1/(2n2)+1/(3n3)-...|=1/n|1-1/(2n)+ 1/(3n2)-...|
≤1/n[1+1/(2n)+1/(3n2)+...]<1/n(1+1/n+ 1/n2+...)=1/(n-1)≤2/n (n≥2)。
また、
|log(1+1/n)|=|1/n-1/(2n2)+1/(3n3)-...|≥1/n|1-1/n[-1/2+1/(3n)-...]|
≥1/n{1-1/n[1/2+1/(3n)+1/(4n2)...]}>1/n{1-1/n[1/2+1/(2n)+1/(2n2)+...]}
=(1/n)[1-1/(2n-2)]≥1/2n (n≥2)。
したがって1/2n<|log(1+1/n)|<2/n (n≥2)だからlog(1+1/n)=Θ(1/n)
(b)
|log |n3-n2+3|-3log n|=|log|1-1/n+3/n3||<log(1+2/n)<4/n (n≥1)。
また|log|1-1/n+3/n3||>log(1+1/2n)>1/4n (n≥3)
以上により|log |n3-n2+3|=3log n+Θ(1/n)
(c)
f(n)=a0nd+a1nd-1+...+adとすると、log|f(n)|-d log n=log|a0+a1/n+...+ad/nd|で、
十分大きなnに対し支配的な項は1/nに比例する項なので、
(a)によりlog|f(n)|=d log n+Θ(1/n)。
・・・というのが大まかな話だが、細かい不等式の計算がややこしい・・・。
(d)
...
(e)
f(n)=Θ(h(n))すなわち正定数C1, C2, n0が存在して全てのn≥n0に対し
C1|h(n)|≤| f(n)|≤C2|h(n)|なら、(1/C2)|f(n)|≤|h(n)|≤(1/C1)|f(n)|なので、
h(n)=Θ(f(n))となり必要条件である。
