コンテンツにスキップ

初等整数論/線形回帰数列

出典: フリー教科書『ウィキブックス(Wikibooks)』


等比数列は漸化式

と初項により決定される数列であった。実際 ならば となる。 これを一般化して、漸化式

と、最初の m 項により決定される数列が考えられる。これを m 階の線形回帰数列あるいは線形循環数列という。

[編集]

イタリアの数学者フィボナッチは、次の問題を考えた。産まれたばかりの1つがいの兎がいるとする。1つがいの兎は、産まれて1ヶ月後には兎を産むことはないが、2ヶ月後から毎月1つがいずつの兎を産む。産まれてきた1つがいの兎もまた同様、産まれて2ヶ月後から毎月1つがいずつの兎を産み、以下産まれてきた1つがいの兎も同様とする。兎が死ぬことはないとして、産まれたばかりの1つがいの兎は1年の間に何つがいの兎にまで増えるだろうか?

n ヶ月目に つがいの兎がいるとすると、これらの兎のつがい達は、その2ヶ月後、つまり ヶ月目には1つがいずつの兎を産む。一方 ヶ月目に産まれた兎は ヶ月目には兎を産まない。つまり ヶ月目には つがいの兎が新しく産まれる。よって

が成り立つ。一方、1ヶ月目には1つがいの兎がおり、2ヶ月目には兎を産むことはないので である。つまり

により定まるので、2階の線形回帰数列である。 そこで、これにより定まる数列をフィボナッチ数列といい、最初の数項は (0, )1, 1, 2, 3, 5, 8, 13, ... で与えられる。計算していくと となり、1年後には144つがいの兎がいることになるが、ちょうど1年後に89つがいの兎が産まれるのとあわせれば、233つがいの兎がいることになる。

で与えられる2階の線形回帰数列の最初の数項は

により与えられる。

一般項

[編集]

まず、等比数列自身が上記の漸化式 (1) を満足する。実際 を方程式

の解とすると

倍し、

を得る。よって数列 は漸化式 (1) を満足する。

このことから を方程式 (2) の解とすると

も漸化式 (1) を満足する。

ここで、方程式 (2) がちょうど m 個の相異なる複素数解 を持つとする(代数学の基本定理より、 m 次方程式は重解を持たなければちょうど m 個の相異なる解を持つ)。 このとき漸化式 (1) を満足する数列が (4) の形のものしかないことを確かめる。 実際 を連立方程式

の解とする。これはw:ヴァンデルモンドの行列式に対応するので が相異なるときこの連立方程式は必ず解を持つ。 このとき

について成り立つ。そうすると (3) と数学的帰納法より 任意の k について (6) が成り立つ。よって は (4) の形で与えられる。

つまり、次の定理が成り立つ。

定理 1
[編集]

方程式 (2) がちょうど m 個の相異なる複素数解 を持つとする。 このとき (6) の形の数列はすべて漸化式 (1) を満足し初項は (5) によって与えられる。 逆に (1) の漸化式を満足する数列は連立方程式 (5) の解 により、(6) の形で与えられる。

[編集]

上記の例に挙げた、フィボナッチ数列 の一般項は に対し、

であらわされる。