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

等比数列は漸化式

$a_{n+1}=ra_{n}$

と初項により決定される数列であった。実際 $a_{0}=d$ ならば $a_{n}=dr^{n}$ となる。 これを一般化して、漸化式

$a_{n+m}=r_{m-1}a_{n+m-1}+\cdots +r_{0}a_{n}\cdots (1)$

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

例

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

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

$a_{n+2}=a_{n+1}+a_{n}$

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

$a_{1}=1,a_{2}=1,a_{n+2}=a_{n+1}+a_{n}$

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

$a_{n+2}=Aa_{1}+Ba_{0}$ で与えられる2階の線形回帰数列の最初の数項は

${\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}}$

により与えられる。

一般項

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

$x^{m}-r_{m-1}x^{m-1}-r_{m-2}x^{m-2}-\cdots -r_{1}x-r_{0}=0\cdots (2)$

の解とすると

$\alpha ^{m}=r_{m-1}\alpha ^{m-1}+r_{m-2}\alpha ^{m-2}+\cdots +r_{1}\alpha +r_{0}$

を $\alpha ^{n}$ 倍し、

$\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)$

を得る。よって数列 $a_{n}=k\alpha ^{n}$ は漸化式 (1) を満足する。

このことから $\alpha _{1},\alpha _{2},\ldots ,\alpha _{r}$ を方程式 (2) の解とすると

$a_{n}=b_{1}\alpha _{1}^{n}+b_{2}\alpha _{2}^{n}+\cdots +b_{r}\alpha _{r}^{n}\cdots (4)$

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

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

${\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)$

の解とする。これはw:ヴァンデルモンドの行列式に対応するので $\alpha _{1},\alpha _{2},\ldots ,\alpha _{m}$ が相異なるときこの連立方程式は必ず解を持つ。 このとき

$a_{k}=b_{1}\alpha _{1}^{k}+b_{2}\alpha _{2}^{k}+\cdots +b_{m}\alpha _{m}^{k}\cdots (6)$

が $k=0,1,\ldots ,m-1$ について成り立つ。そうすると (3) と数学的帰納法より 任意の k について (6) が成り立つ。よって $a_{n}$ は (4) の形で与えられる。

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

定理 1

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

例

上記の例に挙げた、フィボナッチ数列 $(F_{0}=0,)F_{1}=1,F_{n+2}=F_{n+1}+F_{n}$ の一般項は $\alpha ={\frac {1+{\sqrt {5}}}{2}},\beta ={\frac {1-{\sqrt {5}}}{2}}$ に対し、

$F_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}$

であらわされる。