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

等比数列は漸化式

$a_{n+1}=r{a}_n$

と初項により決定される数列であった。実際 $a_0=d$ ならば $a_n=d{r}^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}=A{a}_1+B{a}_0$ で与えられる2階の線形回帰数列の最初の数項は

$\begin{array}{cc}{a}_2=& A{a}_1+B{a}_0,\\ a_3=& (A^2+B)a_1+AB{a}_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+2A{B}^2)a_0,\\ a_6=& (A^5+4A^{3}B+3A{B}^2)a_1+(A^{4}B+3A^2{B}^2+B^3)a_0\end{array}$

により与えられる。

一般項

まず、等比数列自身が上記の漸化式 (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,\dots ,{\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,\dots ,{\alpha }_m$ を持つとする（代数学の基本定理より、 m 次方程式は重解を持たなければちょうど m 個の相異なる解を持つ）。 このとき漸化式 (1) を満足する数列が (4) の形のものしかないことを確かめる。 実際 $b_1,b_2,\dots ,b_m$ を連立方程式

$\{\begin{array}{cc}{b}_1+b_2+\cdots b_m& =a_0,\\ b_1{\alpha }_1+b_2{\alpha }_2+\cdots b_m{\alpha }_m& =a_1,\\ \dots \\ b_1{\alpha }_1^{m-1}+b_2{\alpha }_2^{m-1}+\cdots b_m{\alpha }_m^{m-1}& =a_{m-1}\end{array}\cdots (5)$

の解とする。これはw:ヴァンデルモンドの行列式に対応するので ${\alpha }_1,{\alpha }_2,\dots ,{\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,\dots ,m-1$ について成り立つ。そうすると (3) と数学的帰納法より 任意の k について (6) が成り立つ。よって $a_n$ は (4) の形で与えられる。

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

定理 1

方程式 (2) がちょうど m 個の相異なる複素数解 ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_m$ を持つとする。 このとき (6) の形の数列はすべて漸化式 (1) を満足し初項は (5) によって与えられる。 逆に (1) の漸化式を満足する数列は連立方程式 (5) の解 $b_1,b_2,\dots ,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 }$

であらわされる。