シルヴァーマン 「はじめての数論」第3版 第38章練習問題2

38.8

(a) n¹⁰/2ⁿ=exp{-n log2[1-(10/log2)log n/n]}→0 (n→∞)。

(b) 2ⁿ/n!=∏_{1≤k≤ n} 2/k<2·1·(2/3)^n-2→0 (n→∞)。

(c) n!/2ⁿ²=∏_{1≤k≤ n} k/2ⁿ<nⁿ/2ⁿ²=exp[-n²(log2- log n/n)]→0 (n→∞)。

(d) 定義式によりf(n)=ο(1)ならlim _n→∞f(n)=0。したがって(i)と(iii)がο(1)。

38.9

(a)

(i) |n²-n|=|n(n-1)|≥n (n≥2)なのでn²-n＝Ω(n)

(ii) n!/2ⁿ>(1/2)·1·(3/2)^n-2≥(1/2)·1 (n≥3)なのでn!＝Ω(2ⁿ)。

(iii) (5ⁿ-3ⁿ)/2ⁿ=1+_nC₁·(3/2)+...+_nC_n-1·(3/2)^n-1≥1+_nC₁+...+_nC_n-1=2ⁿ-1≥(1/2)·2ⁿ (n≥1)

なので(5ⁿ-3ⁿ)/2ⁿ＝Ω(2ⁿ)。

(b)

ある正定数C₁, C₂が存在して|f(n)|≥C₁|h(n)|, |h(n)|≥C₂|k(n)|だから

|f(n)|≥C₁C₂|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)

|n³-3n²+7|/n^d=n^3-d-3n^2-d +7n^-d ≥C>0が

十分大きな全てのnについて成り立つために

3-d≥0でなければならないからd=0,1,2,3。

(e)

d≤0で√n=Ω(log₂ n)^d)は明らかに成り立つ。d>0に対しては、

√n/(log₂ 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に対しあるn₀が存在して、

n≥n₀なる全てのnに対しlog(log n)/log n<ε/d

となる。したがってn≥n₀なる全てのnに対し√n/(log₂ n)^d>(log2)^dn^1/2-ε>(log2)^dだから、

d>0に対し√n=Ω(log₂ n)^d)は成り立つ。

したがって、すべての整数dについて成り立つ。

(f)

f(n)=Ω(√n)と仮定すると、n≥n₀なる全てのnに対し

|n sin n/√n|=|√n sin n|≥C (1)となる自然数n₀と正定数Cが存在する。

一方、定理31.2により、|n-2πm|<1/mの整数解(n,m)は無数に存在する。

n≥n₀となる解(n,m)を十分大きくとると|sin 1/m|<1/m、

またn/m-2π≤|n/m-2π|<1/m²よりn/m<2π+1/m²で、

さらにこの二次不等式からm>n/(4π)なので、

C≤|√n sin n|=|√n sin(n-2πm)|<√n/m

=(1/√m)√(n/m)< (1/√m)√(2π+1/m²)<√(3π/m)<√(12π²/n)。

これよりn<12π²/C²となるから、n≥n₀なる全てのnに対し(1)が成り立つことと矛盾する。

したがって、f(n)=Ω(√n)でない。

38.10

(a)

|log(1+1/n)|=|1/n-1/(2n²)+1/(3n³)-...|=1/n|1-1/(2n)+ 1/(3n²)-...|

≤1/n[1+1/(2n)+1/(3n²)+...]<1/n(1+1/n+ 1/n²+...)=1/(n-1)≤2/n (n≥2)。

また、

|log(1+1/n)|=|1/n-1/(2n²)+1/(3n³)-...|≥1/n|1-1/n[-1/2+1/(3n)-...]|

≥1/n{1-1/n[1/2+1/(3n)+1/(4n²)...]}>1/n{1-1/n[1/2+1/(2n)+1/(2n²)+...]}

=(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 |n³-n²+3|-3log n|=|log|1-1/n+3/n³||<log(1+2/n)<4/n (n≥1)。

また|log|1-1/n+3/n³||>log(1+1/2n)>1/4n (n≥3)

以上により|log |n³-n²+3|=3log n+Θ(1/n)

(c)

f(n)=a₀n^d+a₁n^d-1+...+a_dとすると、log|f(n)|-d log n=log|a₀+a₁/n+...+a_d/n^d|で、

十分大きなnに対し支配的な項は1/nに比例する項なので、

(a)によりlog|f(n)|=d log n+Θ(1/n)。

・・・というのが大まかな話だが、細かい不等式の計算がややこしい・・・。

(d)

...

(e)

f(n)=Θ(h(n))すなわち正定数C₁, C₂, n₀が存在して全てのn≥n₀に対し

C₁|h(n)|≤| f(n)|≤C₂|h(n)|なら、(1/C₂)|f(n)|≤|h(n)|≤(1/C₁)|f(n)|なので、

h(n)=Θ(f(n))となり必要条件である。