等比数列は漸化式
![{\displaystyle a_{n+1}=ra_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9aabc1ee867a0baf5d974eb5f5a4f6d991e9b01)
と初項により決定される数列であった。実際
ならば
となる。
これを一般化して、漸化式
![{\displaystyle a_{n+m}=r_{m-1}a_{n+m-1}+\cdots +r_{0}a_{n}\cdots (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c30296e0111a50a0ec476fecf33c2854269d3d0)
と、最初の m 項により決定される数列が考えられる。これを m 階の線形回帰数列あるいは線形循環数列という。
イタリアの数学者フィボナッチは、次の問題を考えた。産まれたばかりの1つがいの兎がいるとする。1つがいの兎は、産まれて1ヶ月後には兎を産むことはないが、2ヶ月後から毎月1つがいずつの兎を産む。産まれてきた1つがいの兎もまた同様、産まれて2ヶ月後から毎月1つがいずつの兎を産み、以下産まれてきた1つがいの兎も同様とする。兎が死ぬことはないとして、産まれたばかりの1つがいの兎は1年の間に何つがいの兎にまで増えるだろうか?
n ヶ月目に
つがいの兎がいるとすると、これらの兎のつがい達は、その2ヶ月後、つまり
ヶ月目には1つがいずつの兎を産む。一方
ヶ月目に産まれた兎は
ヶ月目には兎を産まない。つまり
ヶ月目には
つがいの兎が新しく産まれる。よって
![{\displaystyle a_{n+2}=a_{n+1}+a_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/178ed443a27e75b97e628789834eb768a5ef27b5)
が成り立つ。一方、1ヶ月目には1つがいの兎がおり、2ヶ月目には兎を産むことはないので
である。つまり
は
![{\displaystyle a_{1}=1,a_{2}=1,a_{n+2}=a_{n+1}+a_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b390994e1b4acfb86fab5671db6e13618ca64826)
により定まるので、2階の線形回帰数列である。
そこで、これにより定まる数列をフィボナッチ数列といい、最初の数項は (0, )1, 1, 2, 3, 5, 8, 13, ... で与えられる。計算していくと
となり、1年後には144つがいの兎がいることになるが、ちょうど1年後に89つがいの兎が産まれるのとあわせれば、233つがいの兎がいることになる。
で与えられる2階の線形回帰数列の最初の数項は
![{\displaystyle {\begin{aligned}a_{2}=&Aa_{1}+Ba_{0},\\a_{3}=&(A^{2}+B)a_{1}+ABa_{0},\\a_{4}=&(A^{3}+2AB)a_{1}+(A^{2}B+B^{2})a_{0},\\a_{5}=&(A^{4}+3A^{2}B+B^{2})a_{1}+(A^{3}B+2AB^{2})a_{0},\\a_{6}=&(A^{5}+4A^{3}B+3AB^{2})a_{1}+(A^{4}B+3A^{2}B^{2}+B^{3})a_{0}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afa8cc259f223a837966611f2b3bb1aaf9ed6a2b)
により与えられる。
まず、等比数列自身が上記の漸化式 (1) を満足する。実際
を方程式
![{\displaystyle x^{m}-r_{m-1}x^{m-1}-r_{m-2}x^{m-2}-\cdots -r_{1}x-r_{0}=0\cdots (2)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/948195679f4e45419686272046102d3f2e047aef)
の解とすると
![{\displaystyle \alpha ^{m}=r_{m-1}\alpha ^{m-1}+r_{m-2}\alpha ^{m-2}+\cdots +r_{1}\alpha +r_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1183834fbaa14c1a57ed3908429b25d6c2a365f)
を
倍し、
![{\displaystyle \alpha ^{n+m}=r_{m-1}\alpha ^{n+m-1}+r_{m-2}\alpha ^{n+m-2}+\cdots +r_{1}\alpha ^{n+1}+r_{0}\alpha ^{n}\cdots (3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47d09f36a4cc75b954d1f92c50d8653f08b6d664)
を得る。よって数列
は漸化式 (1) を満足する。
このことから
を方程式 (2) の解とすると
![{\displaystyle a_{n}=b_{1}\alpha _{1}^{n}+b_{2}\alpha _{2}^{n}+\cdots +b_{r}\alpha _{r}^{n}\cdots (4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9405d72f9adfa92f71d9c8656bbf568ebc3b442)
も漸化式 (1) を満足する。
ここで、方程式 (2) がちょうど
m 個の相異なる複素数解
を持つとする(代数学の基本定理より、
m 次方程式は重解を持たなければちょうど m 個の相異なる解を持つ)。
このとき漸化式 (1) を満足する数列が (4) の形のものしかないことを確かめる。
実際
を連立方程式
![{\displaystyle {\begin{cases}b_{1}+b_{2}+\cdots b_{m}&=a_{0},\\b_{1}\alpha _{1}+b_{2}\alpha _{2}+\cdots b_{m}\alpha _{m}&=a_{1},\\\ldots \\b_{1}\alpha _{1}^{m-1}+b_{2}\alpha _{2}^{m-1}+\cdots b_{m}\alpha _{m}^{m-1}&=a_{m-1}\\\end{cases}}\cdots (5)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f643a58f99c415cb43633325116a779c44b97475)
の解とする。これはw:ヴァンデルモンドの行列式に対応するので
が相異なるときこの連立方程式は必ず解を持つ。
このとき
![{\displaystyle a_{k}=b_{1}\alpha _{1}^{k}+b_{2}\alpha _{2}^{k}+\cdots +b_{m}\alpha _{m}^{k}\cdots (6)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2748877fef322a12f4b32242a95c2c86286df6f4)
が
について成り立つ。そうすると (3) と数学的帰納法より
任意の k について (6) が成り立つ。よって
は (4) の形で与えられる。
つまり、次の定理が成り立つ。
方程式 (2) がちょうど m 個の相異なる複素数解
を持つとする。
このとき (6) の形の数列はすべて漸化式 (1) を満足し初項は (5) によって与えられる。
逆に (1) の漸化式を満足する数列は連立方程式 (5) の解
により、(6) の形で与えられる。
上記の例に挙げた、フィボナッチ数列
の一般項は
に対し、
![{\displaystyle F_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b208ac8bbf0f000942466c69cc5c16f58dc8d86)
であらわされる。