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

38.1

(a)

あるn₁, n₂, C₁, C₂が存在して、全てのn≥ n₁に対し|f₁(n)-g₁(n)| ≤ C₁|h(n)|、

全てのn≥ n₂に対し|f₂(n)-g₂(n)|≤C₂|h(n)|であるから、全てのn≥max(n₁, n₂)に対し、

| f₁(n) +f₂(n)-g₁(n)-g₂(n)|≤|f₁(n)-g₁(n)|+|f₂(n)-g₂(n)|≤(C₁+C₂)|h(n)|

となるので、f₁(n) +f₂(n)=g₁(n)+g₂(n)+O(h(n))

(b)

(a)と同様にして、全てのn≥max(n₁, n₂)に対し、

| af₁(n) +bf₂(n)-ag₁(n)-bg₂(n)|≤(aC₁+bC₂)|h(n)|だから、

af₁(n) +bf₂(n)=ag₁(n)+bg₂(n)+O(h(n))

(c)

あるn₀, Cが存在して、全てのn≥ n₀に対し|f(n)-g(n)| ≤ C|h(n)|。

両辺に|k(n)|をかけて、|k(n)f(n)-k(n)g(n)| ≤ C|k(n)h(n)|なので、

k(n)f(n)=k(n)g(n)+O(k(n)h(n))。

38.2

あるn₁, n₂, C₁, C₂>0が存在して、全てのn≥ n₁に対し|f₁(n)-g₁(n)| ≤ C₁|h₁(n)|、

全てのn≥ n₂に対し|f₂(n)-g₂(n)|≤C₂|h₂(n)|であるから、全てのn≥max(n₁, n₂)に対し、

| f₁(n) +f₂(n)-g₁(n)-g₂(n)|≤|f₁(n)-g₁(n)|+|f₂(n)-g₂(n)|

≤C₁|h₁(n)|+C₂|h₂(n)|≤max(C₁, C₂)(|h₁(n)|+|h₂(n)|)≤2max(C₁, C₂)max(|h₁(n)|,|h₂(n)|)

これよりf₁(n) +f₂(n)=g₁(n)+g₂(n)+O(max(|h₁(n)|,|h₂(n)|))。

O(max(|h₁(n)|,|h₂(n)|))の中の絶対値は、外しちゃったらおかしいので多分誤植かな。

38.3

(a) n≥1に対し|f(n)|=3/2+37/[2(2n-1)]≤20なのでO(1)。

(b) n≥1に対し|f(n)|=3n/2+3/4+37/[4(2n-1)]≤ 3n/2+37/2≤20nなのでO(n)。

(c) n≥1に対し|f(n)|=|(3+17/n)/(2n-1/n)| ≤20/nなのでO(1/n)。

(d) n≥1に対し|f(n)|=|cos n|≤1なのでO(1)。

(e) |x|≤1/2に対し|sin x|≥|x|-(|x|³+|x|⁵+|x|⁷+...)=|x|-|x|²/(1-|x|²) ≥|x|-4/3より、

n≥2に対し|f(n)|=|sin(1/n)|^-1 ≤|1/n-(1/(3!n³)-1/(5!n⁵)+...)|^-1≤|1/n-1/n³(1-1/n²+1/n⁴)|^-1

=|1/n-1/(n+n³)|^-1=n|1+1/n²|≤2nなのでO(n)。

(f) (e)より|f(n)|=|n sin(1/n)|^-1≤2なのでO(1)。

38.4

∫_{n≤x≤ n+1} √(x-1) dx=2n^2/3/3 [1-(1-1/n)^3/2]

ここで(1-x)^3/2=1-3x/2+3[(1/2!)(x/2)²+(1/3!)(x/2)³+(3/4!)(x/2)⁴+(3·5/4!)(x/2)⁵+...]>1-3x/2

より2n^3/2/3 [1-(1-1/n)^3/2]< n^1/2 (1)

また、q(n)=∫_{n≤x≤ n+1} √x dx-√n=2/3 [(n+1)^3/2-n^3/2]-n^1/2 (2)

とおくと、q(1)≈0.22>0, q(n)→0 (n→∞), dq/dn=(n+1)^1/2-(2n+1)/2n^1/2<0

だから、n≥1に対しq(n)>0 (3)。

(1)(2)(3)により∫_{n≤x≤ n+1} √(x-1) dx<n^1/2<∫_{n≤x≤ n+1} √x dx。

この式の1からnまでの総和をとると∫_{0≤x≤ n}√x dx<√1+√2+...+√n<∫_{1≤x≤ n+1} √x dxで、

∫_{0≤x≤ n}√x dxを辺々引けば0<√1+√2+...+√n-∫_{0≤x≤ n}√x dx=√1+√2+...+√n-2n^3/2/3

<2/3 [(n+1)^3/2-1]-2n^3/2/3<(2/3)[ (n+1)^3/2-n^3/2] (4)

Cを定数としてp(n)=2/3 [(n+1)^3/2-n^3/2]-Cn^1/2とすれば、

十分大きなC（例えばC>2）と、十分大きな全てのnに対しp(n)<0となるので、

(4)は、0<√1+√2+...+√n-2n^3/2/3<Cn^1/2

となる。したがって、√1+√2+...+√n=(2/3)n^3/2+O(n^1/2)。

38.5

(a)

n≥2に対しq(n)=1/n-∫_{n≤x≤ n+1} 1/x dx=1/n-log(1+1/n) (1)

とおくと、q(2)≈0.41>0, q(n)→0 (n→∞), dq/dn=1/[n(n+1)]-1/n²<0

だから、n≥2に対しq(n)>0 (2)。

また、∫_{n≤x≤ n+1} 1/(x-1) dx=-log(1-1/n)=1/n+1/2n²+1/3n³+...>1/n (3)。

(1)(2)(3)によりn≥2に対し∫_{n≤x≤ n+1} 1/x dx<1/n<∫_{n≤x≤ n+1} 1/(x-1) dx。

この式の2からnまでの総和をとると、log[(n+1)/2]<1/2+1/3...+1/n<log nで、

H_n=1+1/2+1/3...+1/nとおくと、

辺々に1を足し、H_n=1+1/2+1/3...+1/nとおくとlog[(n+1)e/2]< H_n <log ne

log[(n+1)e/2] を辺々引けば

0< H_n - log[(n+1)e/2]<log2-log(1+1/n)<log2 (n≥2) (4)となる。

さらに、0<H_n - log[(n+1)e/2]= H_n-log n-log(1+1/n)-log e/2<H_n-log nだから、

(4)に辺々log(1+1/n)+log e/2を足して(0<) log(1+1/n)+log e/2<H_n -log n

<log 2+ log(1+1/n)+log e/2=1+log(1+1/n) ≤1+log3/2となるので、

H_n = log n+O(1)。

(b)

...

38.6

(a)

ボブは一度推測して外れた数はその後選択しないものとすれば、

最悪の場合、n-2回目までの推測はすべて外れ、n-1回目でアリスの選んだ数が確定する

（n-1回目が外れたら、それまで一度も選択しなかった数がアリスの選んだ数）。

したがってG(n)=n-1<nなのでG(n)=O(n)。

(b)

G(n)=O(√n)とすると、十分大きい全てのnに対し定数Cが存在してG(n)=C√n となる。

一方G(n)=O(n)なので、十分大きい全てのnに対し定数Dが存在して

G(n)=Dn=(D/C) √n ·C√n なので、十分大きい全てのnと全ての定数Cに対し

G(n)> C√nとなり矛盾。

(c)

h(n)はnと同等か高位の無限大である。

(d)

大小の情報があれば、二分探索アルゴリズムを用いることができる。

二分探索では2^G(n)>nとなる最小のG(n)が最大の推測回数だから、

G(n)=O(log₂ n)。

38.7

(a)

√n以下の約数を調べれば十分であるから、約数を見つけるステップ数は√n

に比例するのでF(n)=O(√n)。

(b)

√nまでの素数の数は定理13.1（素数定理）により√n /log√n=2√n/log n程度なので、

F(n)=O(√n/log n)。

(c)

x=log nとおくと、

与式=lim _x→∞ exp[c√(x log x)-x/2]= lim _x→∞ exp[-x/2 (1-2c√(log x/x)]=0

√nの代わりにn^εに変えても同様。

(d)

x=log nとおくと、x→∞で

c'[x(log x)²]^1/3-c[x(log x)]^1/2

=-c[x(log x)]^1/2[1-(c'/c)(log x/x)^1/6] →-∞

だから、lim _n→∞ M(n)/L(n)=0。