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

等比数列は漸化式

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