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

42.1

n=1のときS₁=0=(1-1)/1で成り立つ。

n=mのときS_m=(m-1)/mが成り立つとすると、

S_m+1=S_m+1/[m(m+1)]=m/(m+1)なので、n=m+1のときも成り立つ。

42.2

(a)

C₄(X)=X(X+1)(2X+1)(3X²+3X-1)/30=(6X⁵+15X⁴+10X³-X)/30。

確かにC₄(1)=1, C₄(2)=17, C₄(3)=98。

(b)

C₅(X)=X²(X+1)²(2X²+2X-1)/12=(2X⁶+6X⁵+5X⁴-X²)/12

確かにC₅(1)=1, C₅(2)=33, C₅(3)=276。

42.3

(a)

漸化式においてn^kの項は最初の有理式からのみ現れるから、

C_k-1(n)の主係数は1/k、したがってC_k(n)の主係数は1/(k+1)。

(b)

a=1/2である。

k=2のときC_k-1(n) のn^kの係数a=1/2で成り立つ。

k≥3については、定理42.1の漸化式においてC_k-1 (n) のn^k-1の項の係数は、

(i) 最初の有理式の累乗を展開したn^k-1の項の係数

(ii) 和の項でのj=k-2の項の主係数1/(k-1) ((a)により)と漸化式の係数の積

の2項の和_kC₁/k- _kC_k-2/[k(k-1)]=1/2である。

(c)

b=k/12である。

k=2,3のときC_k-1(n) のn^k-1の係数bはそれぞれ(k-1)/12で成り立つ。

k≥3については、定理42.1の漸化式においてC_k-1 (n) のn^k-2の項の係数は、

(i) 最初の有理式の累乗を展開したn^k-2の項の係数

 (ii) 和の項でのj=k-2の項の最高次の次の次数の係数1/2((b)により)と漸化式の係数の積

(iii) 和の項でのj=k-3の項の最高次係数1/(k-2)((a)により)と漸化式の係数の積

の3項の和_kC₂/k- _kC_k-2/(2k)-_kC_k-3/[k(k-2)]=(k-1)/12。

42.4

(a)

C_k(0)=0であることをkについての数学的帰納法で示す。

k=0,1のときはC_k(0)=0。

定理42.1の漸化式でk≤mのとき成り立つとすると、k=m+1では第2項の和の項は0だから、

C_m(0)=[(0+1)^m+1-1]/(m+1)=0となり、k=m+1でも成り立つ。

すなわち、C_k(X)の多項式はXを因数として持ち、定数項はない。

(b)

C₀(-1)=-1, C_k(-1)=0 (k>0)であることをkについての数学的帰納法で示す。

C₀(X)= Xなので、C₀(-1)=-1。またk=1のときはC₁(-1)=0 。

定理42.1の漸化式でk≤mのとき成り立つとすると、

k=m+1では第2項の和の項で残るのはC₀(X)だけだから、

C_m(-1)=[(-1+1)^m+1-1]/(m+1)-C₀(-1)/(m+1)=0となり、k=m+1でも成り立つ。

すなわち、k>0ではC_k(X)の多項式はX+1を因数として持つ。

(c)

k>0ではC_k(X)の整多項式の部分はX+1を因数として持つから、

C_k(p-1)はpを因数として持ちうる。

が、漸化式の分母にpが現れないことを示さなければならないが・・・。

条件足んなくね？

(d)

C₀(-1/2)=-1/2, C₁(-1/2)=-1/8=-1/2³, C₂(-1/2)=0, C₃(-1/2)=1/64=1/2⁵,

C₄(-1/2)=-7/1920=-7/(2⁷·3·5), C₅(-1/2)=-1/128=-1/2⁷,

C₆(-1/2)=-1/56=-1/(2³·7), C₇(-1/2)=51/6144=51/(2¹¹·3),

C₈(-1/2)=-1123/320=1123/(2⁶·5)., C₉(-1/2)=-31/2048=31/2¹¹...うーん。

42.5

C₅(X)を因数分解してC₅(X)=X²(X+1)²/4=C₁(X)²。

42.6

(a)

k=0のとき(0+1)!C₀(X)=Xで整数係数。

k=1のとき(1+1)!C₁(X)= X²+Xで整数係数。

定理42.1の漸化式のC_k-1(n)を用いてk!C_k-1(n)がk≤mのとき整数係数とする。

k=m+1のときは(m+1)! C_mの式において、

(i) 最初の有理式の項は、分母が(m+1)なので(m+1)!を割るから整数係数多項式。

(ii) 後ろの和の各項m!_m+1C_iC_i(X) (0≤i≤ m-1)について、2項係数は整数で、

帰納法の仮定によりm!C_i(X)= m(m-1)!C_i(X)は整数係数多項式だから、

和も整数係数多項式。

したがって (m+1)!C_mも整数係数多項式となる。

 (b)

2, 6, 4, 30, 12, 42, 24, 90, 20, 66...の列からmod k+1で0らしい。

42.7

n=100までの範囲内では、T₁=C₂(1)=1しか見当たらない。

英語版ウィキペによると、この1組しかないことがBeukers (1988)により証明された。

42.8

(a)(b)

∑_1≤k≤n T_k=∑_{1≤k≤n k+2}C₃=_n+3C₄

∵) n=1のとき₃C₃=₄C₄で成り立つ。

n=mで成り立つとすると、n=m+1のとき

∑_{1≤k≤m+1 k+2}C₃=_m+3C₄+ _m+3C₃=(m+3)!(m+4)/(4!m!)=(m+4)!/(4!m!)=_(m+1)+3C₄

となり、n=m+1でも成り立つ。

42.9

(a)(b)

略

(c)

∑_{1≤k≤n r-1+k}C_r=_n+rC_r+1

(d)

n=1に対して_r-1+1C_r=_rC_r=_1+rC_r+1=1で成り立つ。

n=mで成り立つとすると、n=m+1のとき

∑_{1≤k≤m+1 r-1+k}C_r=_m+rC_r+1+ _r+mC_r=(m+r)!(m+r+1)/[m!(r+1)!]= _m+1+rC_r+1

となり、n=m+1でも成り立つ。

42.10

(a)

P_k(x)=1^k+2^kx+3^kx²+4^kx³+...+n^kx^(n-1)。

P_k(1)=C_k(n)。

(b)

l'Hospitalの公式からlim_x→1(xⁿ-1)/(x-1)=lim_x→1 nx=n=P₀(n)。

(c)

微分を計算してP₁(x)=nxⁿ/(x-1)-P₀(x)/(x-1)=[nxⁿ⁺¹-(n+1)xⁿ+1]/(x-1)²。

(d)

l'Hospitalの公式を用いて、

lim_x→1 P₁(x)=lim_x→1 n(n+1)x^n-1/2=n(n+1)/2。

(a)のP₁(1)の級数表現とこの結果から、C₁(n)の式が証明された。

(e)

(c)(d)と同様にして、P₂(x)=[n²xⁿ⁺²+(-2n²-2n+1)xⁿ⁺¹+(n+1)²xⁿ -x-1]/(x-1)³。

l'Hospitalの公式を繰り返し用いて、

lim_x→1 P₂(x)=n(n+1)(2n+1)/6= C₂(n)を得る。

(f)

めんどい・・・。

42.11

A(x)=B(x)+xB(x)+x²B(x)+x³B(x)+...=B(x)/(1-x)

42.12

問題文のx²の計算は誤っていて、

x²=S(2,0)+S(2,1)x+S(2,2)x(x-1)=S(2,0)+(S(2,1)-S(2,2))x+S(2,2)x²

よりS(2,0)=0, S(2,1)=1, S(2,2)=1。

(a)

同様に計算してS(3,0)=0, S(3,1)=1, S(3,2)=3, S(3,3)=1。

およびS(4,0)=0, S(4,1)=1, S(4,2)=7, S(4,3)=6, S(4,4)=1。

(c)

問題文は全く誤っていて（てか漸化式になってない）、

正しくはS(k, j)=S(k-1, j-1)+jS(k-1, j)。

x^k=∑_0≤j≤k S(k, j)x(x-1)...(x-j+1) (1)

一方、x^k-1=∑_0≤j≤k-1 S(k-1, j)x(x-1)...(x-j+1)より、

x^k=∑_0≤j≤k-1 S(k-1, j)x(x-1)...(x-j+1)·x

∑_0≤j≤k-1 S(k-1, j)x(x-1)...(x-j+1)(x-j+j)

=∑_1≤i≤k S(k-1, i-1)x(x-1)...(x-i+1)+∑_0≤j≤k-1 jS(k-1, j)x(x-1)...(x-j+1) (i=j+1)

=S(k-1, k-1) x(x-1)...(x-k+1)+∑_1≤j≤k-1 (S(k-1, j-1)+ jS(k-1, j))x(x-1)...(x-j+1) (2)

(1)と(2)の各項の係数を比較して、

S(k, 0)=0

S(k, k)=S(k-1, k-1) (=...=S(1,1)=1)

S(k, j)=S(k-1, j-1)+jS(k-1, j)

を得る。

(d)

与式は漸化式の初項S(1,1)=1, S(1,0)=0を与える。

また与式の表式を用いると、、

S(k-1, j-1)+jS(k-1, j)=[1/(j-1)!]∑_0≤i≤j-1 (-1)^j-1-i_j-1C_i i^k-1+(j/j!)∑_0≤i≤j (-1)^j-i_jC_i i^k-1

=[1/(j-1)!]∑_0≤i≤j-1 (-1)^j-i(-_j-1C_i+ _jC_i)i^k-1+(1/j!)_jC_j j^k

二項係数の加法定理より-_j-1C_i i^k-1+_jC_i=_j-1C_i-1=(i/j) _jC_iだから、

S(k-1, j-1)+jS(k-1, j)=(1/j!)∑_0≤i≤j-1 (-1)^j-i _jC_ii^k+(1/j!)_jC_j j^k=(1/j!)∑_0≤i≤j (-1)^j-i _jC_ii^k

=S(k, j)

となるから、与式は(b)の漸化式も満たす。

したがって、与式は第2種Stirling数の一般項を与えている。

42.13

定理42.1の漸化式から(n+1)^k-1=∑_{0≤i≤k-1 k}C_i C_i(n)。

この式にk=1のときC₁(n)に与式を代入すると右辺=nとなるので成り立つ。

k=mで成り立つとして、k=m+1のときについて、

与式とStirling数の漸化式を用いて右辺=(n+1)^m+1-1を示すのだと思うが・・・。