等比数列は漸化式

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

と、最初の 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) の形で与えられる。

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

 

であらわされる。