漸化式と連立方程式

Pocket

次のような問題があります。

「1,4,10,20,35,」という数列がある。n番目の数を表わせ。

このような問題では隣の数との差を調べる方法があります。
4-1=3、10-4=6、というように差を調べると
3,6,10,15,
となります。
さらに差を調べてみます。
3,4,5,
等差数列になりました。

この3番目の数列をC(n)とすると、C(n)=n+2と表わすことができます。
2番目の数列をB(n)とすると
C(1)=B(2)-B(1)
C(2)=B(3)-B(2)

C(n)=B(n+1)-B(n)
となります。
左辺の合計と右辺の合計をみると
ΣC=B(n+1)-B(1)
B(n+1)=ΣC+B(1)=Σ(n+1)+3=Σn+Σ1+3
となってB(n)がnを使った式で表わせます。
続いてA(n)=B(n+1)-B(n)を使って同様にすればA(n)がnを使った式で表わせます。
「できます」と書きましたが、実際にはとても面倒です。

2回、差を取って等差数列(上の例ではC(n))になる場合、元の数列A(n)は3次式(an3+bn2+cn+d)で表わすことができることが知られています。

n=1のとき、an3+bn2+cn+d=a*1+b*1+c*1+d=a+b+c+dとなるので
a+b+c+d=1
となります。
同様にn=2,3,4の場合を調べると
8a+4b+2c+d=4
27a+9b+3c+d=10
64a+16b+4c+d=20
となります。四元一次連立方程式になるので解けます。

You Look Too Cool » Excelで連立方程式を解く

これを解くと
a=1/6
b=1/2
c=1/3
d=0
となるので求める式は
1/6*n3+1/2*n2+1/3*n
となります。

この例と併せて、その他の例をまとめておきます。

数列 1,4,10,20,35,
1/6*n3+1/2*n2+1/3*n

数列 2,7,16,30,50,
1/6*n3+n2+5/6*n

数列 3,10,22,40,65,
1/6*n3+3/2*n2+5/3*n

数列 1,5,14,30,55,
1/3*n3+1/2*n2+1/6*n

[ 2010年9月28日 | カテゴリー: 小ネタ | タグ: , , , ]

« | »

コメント

  1. […] 漸化式と連立方程式という記事を書きました。 このような形式の漸化式を求めるツールを作りました。 […]

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報