Oct 6, 2016

Method of Differences

異なることを同じ用語で呼ぶ場合があります.この method of differences という用語は数列において2つの場合に使われます.

そのひとつは,telescoping series(望遠鏡級数または畳み込み級数)、すなわち,中の符号の異なる項が次々に消えていき,最初と最後の和で全体の和が求まるような級数,例えば$$\sum_{k=1}^n \frac{1}{k(k+1)}=\sum_{k=1}^n\left(\frac{1}{k}-\frac{1}{k+1}\right)$$のような級数ですが,このようなtelescoping sum(望遠鏡和または畳み込み和)を用いる方法をmethod of differences といいます.このtelescopingは,いくつか半径の異なる鏡筒でできた望遠鏡を畳み込むと最初から最後までの鏡筒がひとつにまとまることから来ています.

一方,difference sequence(階差数列)を考えて一般項を求める方法も method of differencesと呼ばれています.(a)初項に階差数列のn-1項の和を加える方法の他に,(b)二項定理に似た方法,(c)連立方程式を用いる方法があります.

(a)初項に階差数列のn-1項の和を加える方法
元の数列{an}の第1階差数列を{bk}とするとき,an=a1+Σbk(ただしΣはn-1までの和)で求めます.第2階差{cn},第3階差{dn}まで考えるときも,{dn}から{cn}を求め,{cn}から{bn}を求め,{bn}から{an}を求めます.

<例1> (第2階差数列が定数列になるとき、もとの数列を2階等差数列といいます)
{an} 5, 10, 17, 26, 37, …
{bn}   5,  7,  9,  11, …
{cn}     2,  2,  2, ….
an=5+Σ(2k+3)(ただしΣはn-1までの和)
   =n^2+2n+2

<例2> (3階等差数列)
{an} 2, 12, 36, 80, 150, 252, …
{bn}   10, 24, 44, 70, 102, …
{cn}     14,  20, 26, 32, …
{dn}        6,   6,  6, …
bn=10+Σ(6k+8)
   =3n^2+5n+2
an=2+Σ(3k^2+5k+2)
   =n^3+n^2

(b)二項定理に似た方法
a1=a1(係数が1)
a2=a1+b1(係数が1,1)
a3=a2+b2
   =a1+b1+b1+c1
   =a1+2b1+c1(係数が1,2,1)
a4=a3+b3
   =a1+2b1+c1+b1+2c1+d1
   =a1+3b1+3c1+d1(係数が1,3,3,1)
...
an=a1+n-1C1・b1+n-1C2・c1+n-1C3・d1+...(+0になるまで)

<上と同じ例1> (2階等差数列)
{an} 5, 10, 17, 26, 37, …
{bn}   5,  7,  9,  11, …
{cn}     2,  2,  2, …
an=5+(n-1)・5+{(n-1)(n-2)/2}・2 (cnの次から0なのでc1で終わり)
   =n^2+2n+2

<上と同じ例2> (3階等差数列)
{an} 2, 12, 36, 80, 150, 252, …
{bn}   10, 24, 44, 70, 102, …
{cn}     14,  20, 26, 32, …
{dn}        6,   6,  6, …
an=2+(n-1)・10+{(n-1)(n-2)/2}・14+{(n-1)(n-2)(n-3)/3!}・6 (dnの次から0なのでd1で終わり)
   =n^3+n^2

<例3 [Explicit Formula 問題]に出てきたMoser's Circle Problem> (4階等差数列)
{an} 1, 2, 4, 8, 16, 31, …
{bn}   1, 2, 4, 8, 15, …
{cn}     1, 2, 4, 7, …
{dn}       1, 2, 3, …
{en}         1, 1, …
an=1+(n-1)・1+(n-1)(n-2)/2・1+(n-1)(n-2)(n-3)/3!・1+(n-1)(n-2)(n-3)(n-4)/4!・1 (enの次から0なのでe1で終わり)
   =1/24(n^4−6n^3+23n^2−18n+24)

(c)連立方程式を用いる方法
第m階差数列が定数列になるとき、もとの数列をm階等差数列といいますが,m階等差数列なら一般項がm次式になることが分かっているので,anをnのm次式とおいて,係数を連立方程式を解いて求めます.

<上と同じ例1> (2階等差数列 m=2の場合)
{an} 5, 10, 17, 26, 37, …
{bn}   5,  7,  9,  11, …
{cn}     2,  2,  2, …
an=an^2+bn+cとおいて,
a1= a+ b+ c= 5
a2=4a+2b+c=10
a3=9a+3b+c=17
を解くと,a=1, b=2, c=2を得るので,
an=n^2+2n+2

<上と同じ例2> (3階等差数列 m=3の場合)
{an} 212, 36, 80, 150, 252, …
{bn}   10, 24, 44, 70, 102, …
{cn}     14,  20, 26, 32, …
{dn}        6,   6,  6, …
an=an^3+bn^2+cn+dとおいて,
a1= a+ b+ c+ d= 2
a2=8a+4b+2c+d=12
a3=27a+9b+3c+d=36
a4=64a+16b+4c+d=80 
を解くと,a=1, b=1, c=0, d=0を得るので, 
an=n^3+n^2 
 

図はこの連立方程式を解いたTI84というGDC(グラフ電卓)の画面です.このrrefは与えられた行列[A]を左基本変形した行列(reduced row-echelon form)を示しています.

<Reference>
望遠鏡和
http://integers.hatenablog.com/entry/2015/11/27/200158

Mathematics Higher Level (Core) 3rd Edition (IBID Press)

Finding the Next Number in a Sequence: Common-Difference Examples
http://www.purplemath.com/modules/nextnumb2.htm