母関数
私が「母関数」というものに初めて出会ったのは、高1の順列・組合せの計算のときだった
と思う。母関数は生成関数とも言われる。
例えば、大小2個のさいころを投げて、目の和が8になる場合の数を求める場合、
(大,小)=(2,6)、(3,5)、(4,4)、(5,3)、(6,2) の5通り
とすれば、特段問題はないが、次のように求めてもいいということを理解するには多少時間
を要した。
2個のサイコロを投げるとき、目の和が8となる場合の数は、多項式
(x+x2+x3+x4+x5+x6)2
を展開したときの、x8 の係数を調べればよい。これが母関数との出会いである。
実際に、 (x+x2+x3+x4+x5+x6)2
=x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12
よって、求める場合の数は、5通りである。
高1のときは、左右対称な係数を覚えるだけで、それ以上の進展はなかったように思う。
しかし、「目の積」の問題で、n 個のサイコロを投げるとき、目の積が2a・3b・5c となる場
合の数が、(1+x+x2+y+xy+z)nを展開したときの、xa・yb・zc の係数に等しいというこ
とや、そのページでの at さんによる母関数の豊かな応用を目にすると、もう少し母関数のこ
とをまとめておく必要性を痛感した。
母関数は、18世紀頃、ド・モアブルやスターリング、オイラーたちによって考案されたという。
母関数を初めて使ったのは、ド・モアブル(1667〜1754)で、1730年のことらしい。
例 2項定理 (1+x)3=1+3x+3x2+x3 における xk の係数 3Ck からも分かるように
xk の係数は、異なる3個の文字から k 個取る場合の数に等しい。
異なる3個の文字 a、b、c から文字を選ぶ場合、各文字について
その文字を選ぶ場合 と その文字を選ばない場合
の2つの場合がある。
そこで、各 a、b、c について、選ぶ場合は x 、選ばない場合は 1 として、文字 a には、多
項式 1+ax、文字 b には、多項式 1+bx、文字 c には、多項式 1+cx を対応させて考
える。
換言すれば、文字 a を高々1度とる組合せを表す多項式が、1+ax ということである。
よって、文字 a を高々2度とる組合せを表す多項式は、1+ax+a2x2 となる。
このとき、
(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3
となる。上式で、1、x、x2、x3 の係数を見ると、
1:異なる3個の文字 a、b、c のどれも選ばない場合は、1通り
x:異なる3個の文字 a、b、c から1個の文字を選ぶ場合は、 a、b、c の3通り
x2:異なる3個の文字 a、b、c から2個の文字を選ぶ場合は、 ab、bc、ca の3通り
x3:異なる3個の文字 a、b、c から3個の文字を選ぶ場合は、 abc の1通り
異なる3個の文字 a、b、c からいくつかの文字を選ぶ場合の数の計算だけだったら、
a=b=c=1として、
(1+x)(1+x)(1+x)=1+(1+1+1)x+(1+1+1)x2+1x3
すなわち、 (1+x)3=1+3x+3x2+x3 であったわけである。
したがって、異なる3個の文字 a、b、c から文字を選ぶ場合の母関数は、
(1+x)3=1+3x+3x2+x3
である。一般に、
数列{an}に対して、形式的なべき級数 a0+a1x+a2x2+a3x3+・・・+anxn+・・・ を、
その数列の通常型母関数という。
例 3個の文字 a、a、b から文字を選ぶ場合の母関数は、
(1+x+x2)(1+x)=1+2x+2x2+x3 である。
これは、(1+ax+a2x2)(1+bx) と考えれば明らかだろう。
例 4個の文字 a、a、b、b から文字を選ぶ場合の母関数は、
(1+x+x2)(1+x+x2)=1+2x+3x2+2x3+x4 である。
これは、(1+ax+a2x2)(1+bx+b2x2) と考えれば明らかだろう。
一般に、次が成り立つ。
n 個のうち、m1、m2、・・・、mk 個が同じものであるとき、n 個のものから重複を許
して r 個とる組合せの数は、次の多項式の xr の係数に等しい。
(1+x+x2+・・・+xm1)(1+x+x2+・・・+xm2)・・・(1+x+x2+・・・+xmk)
ただし、n=m1+m2+・・・+mk とする。
例 5個の文字 a、a、a、b、b から重複を許して3個とる組合せの数を求めよ。
求める場合の数は、 aaa、aab、abb の3通りである。
この計算を母関数の考えを用いて行ってみよう。
(1+x+x2+x3)(1+x+x2)=・・・+x3+・・・+x3+・・・+x3+・・・
より、x3 の係数は、1+1+1=3 なので、求める場合の数は、3通りである。
(証明) n 個のうち、
a が m1個 、b が m2個 、・・・、c が mk 個 (n=m1+m2+・・・+mk)
とする。このとき、k個の多項式
1+ax+a2x2+・・・+am1xm1
1+bx+b2x2+・・・+bm2xm2
・・・・・・・・・・・・・・・・・・・
1+cx+c2x2+・・・+cmkxmk
の積を考え展開したとき、
x の係数 : a、b、・・・、c の和
x2 の係数 : a、b、・・・、c から重複を許して2個ずつの積
・・・・・・・・・・・・・・・・・・・・・・・・・・・・
xr の係数 : a、b、・・・、c から重複を許して r 個ずつの積
である。 (証終)
上記では、組合せの数が母関数から得られることを見たが、順列の数も母関数から得ら
れる。
(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+abcx3
において、
異なる3個の文字 a、b、c のどれも選ばない場合は、1通り
異なる3個の文字 a、b、c から1個とる順列の数は、 a、b、c の3通り
異なる3個の文字 a、b、c から2個とる順列の数は、
ab、ba、bc、cb、ca、ac の6通り
そこで、 ab+ba=2ab、 bc+cb=2bc、 ca+ac=2ca と考えれば、
x2 の項は、(ab+bc+ca)x2=2(ab+bc+ca)x2/2! とも変形できる。
異なる3個の文字 a、b、c から3個とる順列の数は、
abc、acb、bac、bca、cab、cba の6通り
そこで、 abc+acb+bac+bca+cab+cba=6abc と考えれば、
x3 の項は、abcx3=6abcx3/3! とも変形できる。
すなわち、
(1+ax)(1+bx)(1+cx)
=1+(a+b+c)x+(ab+bc+ca)x2+abcx3
=1+(a+b+c)x/1!+2(ab+bc+ca)x2/2!+6abcx3/3!
と考えることができる。ここで、 a=b=c=1 とすると、
(1+x)3=1+3x/1!+6x2/2!+6x3/3!
となり、xr/r!の係数が、異なる3個のものより r 個とる順列の数に等しい。一般に、
(1+x)n
=nC0+nC1x+nC2x2+・・・+nCrxr+・・・+nCnxn
=nP0+nP1x/1!+nP2x2/2!+・・・+nPrxr/r!+・・・+nPnxn/n!
が成り立つ。
一般に、数列{an}に対して、形式的なべき級数
a0+a1x/1!+a2x2/2!+a3x3/3!+・・・+anxn/n!+・・・
を、その数列の指数型母関数という。
例 4個の文字 a、a、b、b から文字をいくつか選んで並べる場合の母関数は、
(1+ax/1!+a2x2/2!)(1+bx/1!+b2x2/2!)
=1+(a+b)x/1!+(a2/2!+ab/1!1!+b2/2!)x2
+(ab2/1!2!+a2b/1!2!)x3+(a2b2/2!2!)x4
=1+(a+b)x/1!+(a2+2ab+b2)x2/2!+(3ab2+3a2b)x3/3!+6a2b2x4/4!
である。
このとき、例えば、4個の文字 a、a、b、b から3個とって並べる順列の数は、
aab、aba、baa、abb、bab、bba の6通り
であるが、母関数のx3/3!の係数 3ab2+3a2b から
aab+aba+baa+abb+bab+bba の6項
を意味するので、求める場合の数は、6通りであることが分かる。
一般に、次が成り立つ。
n 個のうち、m1、m2、・・・、mk 個が同じものであるとき、n 個のものから r 個とる
順列の数は、次の多項式の xr の係数に r!を掛けたものに等しい。
ただし、n=m1+m2+・・・+mk で、0≦r≦n とする。
例 5個の文字 a、a、a、b、b から3個とる順列の数を求めよ。
a 3個のとき、 1通り
a 2個、b 1個のとき、 3通り
a 1個、b 2個のとき、 3通り 以上から、求める場合の数は、 1+3+3=7(通り)
この計算を母関数の考えを用いて行ってみよう。
(1+x+x2/2+x3/6)(1+x+x2/2)=・・・+x3/2+・・・+x3/2+・・・+x3/6+・・・
より、x3 の係数は、 1/2+1/2+1/6=7/6 なので、3!=6 を掛けて、
求める場合の数は、 (7/6)×6=7(通り)
(証明) n 個のうち、
a が m1個 、b が m2個 、・・・、c が mk 個 (n=m1+m2+・・・+mk)
とする。このとき、k個の多項式
1+ax+a2x2/2!+・・・+am1xm1/m1!
1+bx+b2x2/2!+・・・+bm2xm2/m2!
・・・・・・・・・・・・・・・・・・・・・・・・・・・・
1+cx+c2x2/2!+・・・+cmkxmk/mk!
の積を考え展開したとき、
(ar1xr1/r1!)(br2xr2/r2!)・・・(crkxrk/rk!)
={1/(r1!r2!・・・rk!)}ar1br2・・・crkxr (r=r1+r2+・・・+rk)
は、r個のうち、a を r1 個、b を r2 個、・・・、c を rk 個とった1つの組合せに対応している。
このときの係数 1/(r1!r2!・・・rk!) (r=r1+r2+・・・+rk) の和に r!を掛けたも
のが求める場合の数を与える。 (証終)
母関数というと馴染みがないように感じるが、パスカルの三角形を考えているとき、母関数
の概念を無意識に使っていたことに気づかされる。
また、パスカルの三角形を縦方向に見ると、母関数 (1−x)-n を与えているという事実は
面白い。
F(x)=(1−x)-n とおくと、 F(0)=1 で、
F’(x)=n(1−x)-n-1
より、 F’(0)=n
F”(x)=n(n+1)(1−x)-n-2
より、 F”(0)=n(n+1)
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
F(k)(x)=n(n+1)・・・(n+k−1)(1−x)-n-k より、F(k)(0)=n(n+1)・・・(n+k−1)
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
以上から、(1−x)-n
を x=0
のまわりでマクローリン展開すると、
(1−x)-n=1+nx+{n(n+1)/2}x2+・・・+{n(n+1)・・・(n+k−1)/k!}xk+・・・
因みに、パスカルの三角形から
(1−x)-1=1+1・x+1・x2+・・・+1・xk+・・・
(1−x)-2=1+2・x+3・x2+・・・+(k+1)・xk+・・・
(1−x)-3=1+3・x+6・x2+・・・+{(k+1)(k+2)/2}・xk+・・・
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
となり、マクローリン展開の結果と一致する。
(コメント) この関係は面白いですね!ある意味で、裏技です...。
さらに、Fn(x)=(1−x)-n として、
G(x)=F1(x)+x2F2(x)+x4F3(x)+x6F4(x)+x8F5(x)+・・・
とおくと、フィボナッチ数列の母関数になることが知られている。
実際に、 G(x)=1+x+x2+x3+x4+x5+・・・
+x2+2x3+3x4+4x5+・・・・
+x4+3x5+・・・・
・・・・・・
=1+x+2x2+3x3+5x4+8x5+・・・
から、フィボナッチ数列 1,1,2,3,5,8,・・・ が得られる。
ここで、G(x)は初項が (1−x)-1 で公比
x2(1−x)-1 の無限等比級数であるので、
G(x)=(1−x)-1/{1−x2(1−x)-1}=1/(1−x−x2)
となる。ただし、収束条件は、 −1<x2(1−x)-1<1 すなわち、|2x+1|<
(形式的なべき級数なので、収束条件を考えても意味がないかな?)
フィボナッチ数列 {an}は、漸化式
a0=1、a1=1、an+2=an+1+an (n=0、1、2、・・・)
により定義される。漸化式の解法にも母関数の考えは用いられる。
フィボナッチ数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・
を考える。このとき、
−xF(x)= −a0x−a1x2−a2x3−a3x4−・・・・−anxn+1−・・・
−x2F(x)= −a0x2−a1x3−a2x4−a3x5−・・・・−anxn+2−・・・
より、 (1−x−x2)F(x)=1 なので、 F(x)=1/(1−x−x2)
これは上記で得られた母関数 G(x) と一致している。
ここで、1−x−x2=0 即ち x2+x−1=0 の2つの解を α、β(α>β) とすると、
α=(−1+)/2 、β=(−1−)/2 より、 α−β=
さらに、 1/α=(1+)/2 、 1/β=(1−)/2
このとき、 F(x)={1/(α−x)−1/(β−x)}/(α−β)
={1/{α(1−x/α)}−1/{β(1−x/β)}/(α−β)
={(1/α)Σ(x/α)n−(1/β)Σ(x/β)n)}/(α−β)
xn の係数に着目して、
an={(1/α)(1/α)n−(1/β)(1/β)n}/(α−β)
={(1/α)n+1−(1/β)n+1}/(α−β)
=[{(1+)/2}n+1−{(1−)/2}n+1]/ (n=0、1、2、・・・)
これは、フィボナッチ数列の一般項で、「ビネの公式」と言われる。
当HP読者のK.S.さんから上記の話題について、メールを頂いた。
(平成23年11月11日付け)
α=(1+)/2 、β=(1−)/2 とおくと、 α+β=1、αβ=−1 である。
このとき、 x/(1−x−x2)=(1/){1/(1−αx)−1/(1−βx)}
=(1/){1+αx+α2x2+・・・+αnxn+・・・
−1−βx−β2x2−・・・−βnxn−・・・}
=(1/){(1−1)+(α−β)x+(α2−β2)x2+・・・}
ここで、an=[{(1+)/2}n+1−{(1−)/2}n+1]/ (n=0、1、2、・・・)
なので、 x/(1−x−x2)=(1/){a0x+a1x2+・・・+anxn+1+・・・}
という形のフィボナッチ数列の母関数が得られる。
(コメント) 上記の母関数の両辺を x で割ると、当初得られた母関数が得られる。どちらの
導入がより易しいのだろう?
母関数を利用した漸化式の解法を見ると、次の問題にも使いたくなるような...気分!
問 題 次の4項間漸化式を解け。
a0=1、a1=0、、a2=−5、 an+3−4an+2+5an+1−2an=0 (n≧0)
(特性方程式を利用する解) x3−4x2+5x−2=0 は因数分解されて、
(x−1)2(x−2)=0 より、 解は x=1、2
このとき、 x3−(α+β+γ)x2+(αβ+βγ+γα)x−αβγ=0 は、
x3−(β+γ)x2+βγx=α{x2−(β+γ)x+βγ}
と変形されるので、
α=1、β=1、γ=2 のとき、
an+3−3an+2+2an+1=an+2−3an+1+2an=a2−3a1+2a0=−3
α=2、β=1、γ=1 のとき、
an+3−2an+2+an+1=2(an+2−2an+1+an)
ここで、 a2−2a1+a0=−4 なので、 an+2−2an+1+an=−4・2n=−2n+2
よって、連立方程式 an+2−3an+1+2an=−3 、an+2−2an+1+an=−2n+2 から、
an+1−an=3−2n+2
したがって、n≧1のとき、
an=a0+Σ[k=0〜n-1](3−2k+2)=1+3n−4(2n−1)=5+3n−2n+2
この式は、n=0 のときも成り立つ。
以上から、 an=5+3n−2n+2 (n≧0) (終)
(母関数を利用する解) 数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・
を考える。このとき、
−4xF(x)= −4a0x−4a1x2−4a2x3−4a3x4−・・・−4anxn+1−・・・
5x2F(x)= 5a0x2+5a1x3+5a2x4+・・・+5anxn+2+・・・
−2x3F(x)= −2a0x3−2a1x4−・・・−2anxn+3−・・・
より、 (1−4x+5x2−2x3)F(x)=1−4x なので、
F(x)=(1−4x)/(1−4x+5x2−2x3)=(1−4x)/{(1−x)2(1−2x)}
部分分数に分解して、
F(x)=2/(1−x)+3/(1−x)2−4/(1−2x)
=2Σxn+3(Σxn)2−4Σ(2x)n
=2Σxn+3Σ(n+1)xn−4Σ2nxn
xn の係数に着目して、 an=2+3(n+1)−4・2n=5+3n−2n+2 (終)
(コメント) (特性方程式を利用する解)では非常に技巧的な趣きがあるが、(母関数を利用
する解)の方では、自然な流れというものを感じます。
上記の解における手法を用いると、次の漸化式も容易に解けるだろう。
問 題 次の n+1 項間漸化式を解け。
a0=1 、an=a0・an-1+a1・an-2+a2・an-3+・・・+an-1・a0 (n≧1)
(解) 数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・
を考える。このとき、
xF(x)2= a02x+(a0・a1+a1・a0)x2+(a0・a2+a1・a1+a2・a0)x3+・・・
より、 F(x)−xF(x)2=1 すなわち、 xF(x)2−F(x)+1=0 となる。
F(0)=1 なので、
(解の公式で、複号のうち、「+」とすると、x→0 のとき、F(x)は発散してしまう!)
2項級数より、
なので、F(x)の xn の係数は、 −1/2Cn+1(−4)n+1/2 である。
ここで、
1/2Cn+1=(1/2)(−1/2)(−3/2)・・・(−(2n−1)/2)/(n+1)!
=(−1)n・1・3・5・・・・・(2n−1)/{2n+1・(n+1)!}
=(−1)n・1・2・3・・・・・・(2n−1)・2n/{22n+1・n!(n+1)!}
=(−1)n・(2n)!/{22n+1・n!(n+1)!}
=(−1)n・2nCn/{22n+1・(n+1)}
なので、
−1/2Cn+1(−4)n+1/2
=−[(−1)n・2nCn/{22n+1・(n+1)}]・(−1)n+1・22n+1=2nCn/(n+1)
したがって、 an=2nCn/(n+1) となる。(→ 参考:「カタラン数」)
(コメント) この漸化式を、母関数を用いないで解くなんて想像できない!
(追記) 「母関数の有効利用」と題して、当HPがいつもお世話になっているHN「GAI」さん
からの投稿です。(平成28年10月20日付け)
ここ何日かの計算を行っていて、次のようなテーマを一気に解決できる母関数を作れるこ
とに気づきました。
例えば、10個の奇素数の集合W={3,5,7,11,13,17,19,23,29,31}があるとき、
(1) Wから相異なるk個の積(k=1,2,3,・・・,10)の和s1[k]を知りたいなら
F1(x)=(1+3*x)(1+5*x)(1+7*x)・・・・・(1+31*x) を展開して、
F1(x) = 1 + 158*x + 10805*x^2 + 419800*x^3 + 10224018*x^4
+ 162393924*x^5
+ 1695059330*x^6 + 11412878200*x^7 + 47114595181*x^8 + 106868339918*x^9
+ 100280245065*x^10
より、s1[k]=x^k の項の係数
(2) Wから同じものを含めたk個の積(3^k,7^(k-3)*17^2*23,などを含む。)の和s2[k]は
F2(x)=1/((1-3*x)(1-5*x)(1-7*x)・・・・・(1-31*x)) を級数展開して、
F2(x) = 1+ 158*x + 14159*x^2 + 949732*x^3 + 53174043*x^4 + 2630591814*x^5
+ 118986775397*x^6 + 5031681224656*x^7 + 202010077418806*x^8
+ 7785253969285508*x^9 + 290375919746318634*x^10
+ 10546897376137664232*x^11 + O(x^12)
より、s2[k]=x^k の項の係数
(3) Wの各要素のk乗の和S[k](=3^k+5^k+7^k+・・・・・+31^k)(k=1,2,3,・・・,10)を知りたいなら、
F3[x]=(x-3)(x-5)(x-7)・・・・・(x-31) を準備して、
(x^10*x*F3[x])を微分したものをF3[x]で割り、その商を求める。(kは最大で10までなので)
<これをPARIのソフトで実行したもの>
gp>F3(x)=prod(k=2,11,x-prime(k))
gp>divrem(deriv(x^10*x*F3(x)),F3(x))[1]を実行して
= 21*x^10 + 158*x^9 + 3354*x^8 + 82142*x^7 + 2170794*x^6 + 60025118*x^5
+ 1708278714*x^4 + 49554665822*x^3 + 1456444007754*x^2 + 43202201145758*x
+ 1290073179869274
より、S[k]=x^(10-k)の項の係数(S[10]は定数項に対応する。)
(確かめ) gp>for(k=1,10,print("S[",k,"]=",sum(i=2,11,prime(i)^k)))
S[1]=158
S[2]=3354
S[3]=82142
S[4]=2170794
S[5]=60025118
S[6]=1708278714
S[7]=49554665822
S[8]=1456444007754
S[9]=43202201145758
S[10]=1290073179869274
(追記) 令和3年4月26日付け
数列{an}に対して、形式的なべき級数
a0+a1x+a2x2+a3x3+・・・+anxn+・・・
は、その数列の通常型母関数と言われるが、具体的な例をまとめておこう。
例1. an=1 (n=0、1、2、3、・・・) のとき、
1+x+x2+x3+・・・+xn+・・・=1/(1−x)
例2. an=(−1)n (n=0、1、2、3、・・・) のとき、
1−x+x2−x3+・・・+(−1)nxn+・・・=1/(1+x)
例3. an=n (n=0、1、2、3、・・・) のとき、
x+2x2+3x3+・・・+nxn+・・・=x/(1−x)2
この母関数は、 1+x+x2+x3+・・・+xn+・・・=1/(1−x) の両辺を微分して、x を
掛けて得られる。
実際に、まず、 1+x+x2+x3+・・・+xn+・・・=1/(1−x) を微分して、
1+2x+3x2+4x3+・・・+nxn-1+・・・=1/(1−x)2
よって、 x+2x2+3x3+・・・+nxn+・・・=x/(1−x)2
例4. an=2n (n=0、1、2、3、・・・) のとき、
1+2x+22x2+23x3+・・・+2nxn+・・・=1/(1−2x)
例5. an=n2 (n=1、2、3、・・・) のとき、
F(x)=1+22x+32x2+42x3+・・・+(n−1)2xn+・・・ とおくと、
xF(x)=x+22x2+32x3+42x4+・・・+(n−1)2xn+1+・・・ より、
(1−x)F(x)=1+3x+5x2+7x3+9x4+・・・+(2n−3)xn+・・・
x(1−x)F(x)=x+3x2+5x3+7x4+9x5+・・・+(2n−5)xn+・・・
なので、
(1−x)2F(x)=1+2x+2x2+2x3+2x4+2x5+・・・+2xn+・・・
=2/(1−x)−1=(1+x)/(1−x)
したがって、 F(x)=(1+x)/(1−x)3 が母関数となる。
読者のために、練習問題を残しておこう。
練習問題 an=(2n−1)2 (n=1、2、3、・・・) のとき、母関数を求めよ。
(解) F(x)=1+x+32x2+52x3+・・・+(2n−1)2xn+・・・ とおくと、
xF(x)=x+x2+32x3+52x4+・・・+(2n−3)2xn+・・・ より、
(1−x)F(x)=1+8x2+16x3+24x4+・・・+(8n−8)xn+・・・
=1+8x2(1+2x+3x2+・・・+(n−1)xn-2+・・・)
=1+8x2(1+2x+3x2+・・・+nxn-1+・・・)
=1+8x2/(1−x)2 (← 例3)
=1+8x2/(1−x)2=(1−2x+9x2)/(1−x)2
したがって、 F(x)=(1−2x+9x2)/(1−x)3 が母関数となる。 (終)
(追記) 令和5年6月30日付け
上記の問題で、漸化式を通して求める解法もある。
(別解) an+1−an=(2n+1)2−(2n−1)2=8n なので、
(an+2−an+1)−(an+1−an)=8(n+1)−8n=8 から、 an+2−2an+1+an=8
よって、数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・ について、
F(x)−2xF(x)+x2F(x)=1−x+8x2(1+x+x2+x3+・・・+xn+・・・) より、
(1−2x+x2)F(x)=1−x+8x2/(1−x)=(1−2x+9x2)/(1−x)
よって、 F(x)=(1−2x+9x2)/(1−x)3 (終)
問題 漸化式 a0=1 、an+1=2an+1 を母関数を用いて解け。
(解) 数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・ について、
F(x)−2xF(x)=1+x+x2+x3+・・・+xn+・・・=1/(1−x)
よって、F(x)=1/{(1−2x)(1−x)}=2/(1−2x)−1/(1−x) すなわち、
F(x)=Σn=0∞ 2n+1xn−Σn=0∞ xn=Σn=0∞ (2n+1−1)xn
よって、数列{an}の一般項 an は、 an=2n+1−1 (終)
読者のために、練習問題を残しておこう。
練習問題 漸化式 a0=1 、a1=3 、an+2=an+1+2an を母関数を用いて解け。
(解) 数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・ について、
F(x)=1+3x+Σn=0∞an+2xn+2=1+3x+Σn=0∞(an+1+2an)xn+2
すなわち、 F(x)=1+3x+x(Σn=0∞anxn−1)+2x2Σn=0∞anxn より、
F(x)=1+3x+x(F(x)−1)+2x2F(x)
よって、 F(x)=(1+2x)/(1−x−2x2)=(4/3)/(1−2x)−(1/3)/(1+x) より、
F(x)=(4/3)(Σn=0∞2nxn)−(1/3)(Σn=0∞(−1)nxn)
=Σn=0∞{(2n+2−(−1)n)/3}xn
よって、数列{an}の一般項 an は、 an=(2n+2−(−1)n)/3 (終)
(コメント) 教科書的には次のように解かれる。
漸化式より、 an+2+an+1=2(an+1+an) を解いて、 an+1+an=4・2n=2n+2
また、 an+2−2an+1=−(an+1−2an) を解いて、 an+1−2an=(−1)n
辺々引いて、 3an=2n+2−(−1)n より、 an=(2n+2−(−1)n)/3
#こちらの方が慣れているせいか、しっくりきますね...。
さらに、練習問題を残しておこう。
練習問題 an=3n+1 (n=1、2、3、・・・) のとき、母関数を求めよ。
(解) an−an-1=3 なので、数列{an}に対して、形式的なべき級数
F(x)=Σn=0∞anxn について、
F(x)−xF(x)=Σn=0∞anxn1−Σn=0∞anxn+1=1+3xΣn=0∞xn=1+3x/(1−x)
よって、 F(x)=(1+2x)/(1−x)2 が求める母関数である。 (終)
(コメント) F(x)=(1+2x)/(1−x)2=1/(1−x)+3x/(1−x)2 において、
x+2x2+3x3+・・・+nxn+・・・=x/(1−x)2 を用いて、
F(x)=Σn=0∞xn+3Σn=0∞nxn=Σn=0∞(3n+1)xn
となるので、確かに、F(x)は、数列{3n+1}の母関数となっている。
練習問題 漸化式 a0=1、a1=−3、an+2+2an+1+an=0 を解け。
(解) an+2+an+1=−(an+1+an) と変形し、bn=an+1+an とおくと、
漸化式 b0=−2、bn+1=−bn を得る。
このとき、 bn=(−2)・(−1)n=2・ (−1)n+1 となるので、
漸化式 a0=1、a1=−3、an+1+an=2・(−1)n+1 を得る。
両辺を、(−1)n+1 で割って、 an+1/(−1)n+1−an/(−1)n=2
よって、数列 {an/(−1)n}は、初項が1で公差が2の等差数列となるので、
an/(−1)n=1+2(n−1)=2n+1 より、 an=(2n+1)(−1)n (終)
この問題を、母関数を用いて解いてみよう。
(別解) 数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・ について、
F(x)+2xF(x)+x2F(x)=1−x 即ち、 (1+x)2F(x)=1−x となるので、
F(x)=(1−x)/(1+x)2=2/(1+x)2−1/(1+x) と書ける。
ここで、 1/(1+x)=Σn=0∞ (−x)n=Σn=0∞ (−1)nxn で、
両辺を微分すれば、 −1/(1+x)2=Σn=1∞ (−1)nnxn-1 なので、
F(x)=Σn=1∞ 2n(−1)n-1xn-1−Σn=0∞ (−1)nxn
=Σn=0∞ 2(n+1)(−1)nxn−Σn=0∞ (−1)nxn=Σn=0∞ (2n+1)(−1)nxn
よって、数列{an}の一般項 an は、 an=(2n+1)(−1)n (終)
練習問題 漸化式 a0=1、a1=0、a2=−5、an+3−4an+2+5an+1−2an=0 を解け。
4項間漸化式の解法は、高校ではあまり扱われないと思うが、その解法は、既存の知識を
用いて十分対応できる。
(解) an+3+pan+2+qan+1=r(an+2+pan+1+qan) とし、展開して係数比較すると、
−p+r=4 、−q+pr=−5 、qr=2
q=pr+5 を、qr=2 に代入して、pr2+5r=2
p=r−4 を代入して整理すると、 r3−4r2+5r−2=0
このとき、 (r−1)2(r−2)=0 より、 r=1 、2
r=1 のとき、 p=−3 、q=2 なので、 an+3−3an+2+2an+1=an+2−3an+1+2an
よって、 an+2−3an+1+2an=a2−3a1+2a0=−3 ・・・ (*)
r=2 のとき、 p=−2 、q=1 なので、 an+3−2an+2+an+1=2(an+2−2an+1+an)
よって、 an+2−2an+1+an=2n(a2−2a1+a0)=−4・2n=−2n+2 ・・・ (**)
(**)−(*) より、 an+1−an=−2n+2+3 となるので、n≧1 のとき、
an=a0+Σk=0n-1 (−2k+2+3)=1−4(2n−1)+3n=−2n+2+3n+5
この式は、n=0 のときも成り立つ。
したがって、数列{an}の一般項 an は、 an=−2n+2+3n+5 (終)
この問題を、母関数を用いて解いてみよう。
(別解) 数列{an}に対して、形式的なべき級数
F(x)=a0+a1x+a2x2+a3x3+・・・+anxn+・・・ について、
F(x)−4xF(x)+5x2F(x)−2x3F(x)=1−4x 即ち、
(1−4x+5x2−2x3)F(x)=1−4x より、(1−x)2(1−2x)F(x)=1−4x となるので、
F(x)=(1−4x)/(1−x)2(1−2x) と書ける。右辺を部分分数分解して、
F(x)=5/(1−x)+3x/(1−x)2−4/(1−2x)
=5Σn=0∞xn+3Σn=0∞nxn−4Σn=0∞2nxn=Σn=0∞(−2n+2+3n+5)xn
よって、数列{an}の一般項 an は、 an=−2n+2+3n+5 (終)
(追記) 令和5年7月8日付け
自然対数の底の定義から、Σn=0∞ (1/n!)=e であるが、Σn=0∞ ((n+1)/n!)の
値はいくつになるだろうか?
結論から言えば、 Σn=0∞ ((n+1)/n!)=2e である。
実際に、部分和 Sn=Σk=0n ((k+1)/k!) について、
Sn=1+Σk=1n ((k+1)/k!)=1+Σk=1n ((1/(k−1)!)+1+Σk=1n (1/k!)
すなわち、 Sn=Σk=0n-1 ((1/k!)+Σk=0n (1/k!) と書けるので、
n → ∞ のとき、 Sn → 2e なので、 Σn=0∞ ((n+1)/n!)=2e である。
これに対して、母関数を用いると、次のように解かれる。
数列 {an} において、an=1/n!の母関数は、F(x)=Σn=0∞ (1/n!)xn であるが、
これは指数関数 ex のマクローリン展開そのものである。すなわち、
ex =Σn=0∞ (1/n!)xn ・・・ 収束半径は∞で、すべての実数に対して定義される。
両辺に x を掛けて、 x・ex =Σn=0∞ (1/n!)xn+1
両辺を微分して、 (1+x)・ex =Σn=0∞ ((n+1)/n!)xn
ここで、x=1 とおくと、 Σn=0∞ ((n+1)/n!)=2e であることが分かる。
読者のために、練習問題を残しておこう。
練習問題 Σn=0∞ ((n+1)2/n!) の値を求めよ。
(解) ex =Σn=0∞ (1/n!)xn から、 (1+x)・ex =Σn=0∞ ((n+1)/n!)xn
両辺に x を掛けて、 (x+x2)・ex =Σn=0∞ ((n+1)/n!)xn+1
両辺を微分して、 (1+3x+x2)・ex =Σn=0∞ ((n+1)2/n!)xn
ここで、x=1 とおくと、 Σn=0∞ ((n+1)2/n!)=5e であることが分かる。 (終)
(別解) 部分和 Sn=Σk=0n ((k+1)2/k!) について、
Sn=1+Σk=1n ((k+1)2/k!)
=1+Σk=1n ((k2+2k+1)/k!)
=1+Σk=1n (k/(k−1)!)+2Σk=1n (1/(k−1)!)+Σk=1n (1/k!)
=Σk=1n ((k−1+1)/(k−1)!)+2Σk=0n-1 (1/(k−1)!)+Σk=0n (1/k!)
=1+Σk=2n (1/(k−2)!)+Σk=2n (1/(k−1)!)
+2Σk=0n-1 (1/(k−1)!)+Σk=0n (1/k!)
=1+Σk=0n-2 (1/k!)+Σk=1n-1 (1/k!)+2Σk=0n-1 (1/(k−1)!)+Σk=0n (1/k!)
=Σk=0n-2 (1/k!)+Σk=0n-1 (1/k!)+2Σk=0n-1 (1/(k−1)!)+Σk=0n (1/k!)
よって、n → ∞ のとき、 Sn → 5e なので、
Σn=0∞ ((n+1)2/n!)=5e である。 (終)
(コメント) 母関数を用いた方が、あまり気を使わず、形式的に求められますね!
以下、工事中