線形回帰数列

体 $\K$ 上、与えられた $s_1, s_2, \ldots, s_r\in \K$ に対して、漸化式 (recursive formula)
$$u_{n+r}=s_1 u_{n+r-1}+s_2 u_{n+r-2}+\cdots +s_r u_n\ (n=0, 1, \ldots)\tag{1}\label{eq11}$$
が成り立っている数列 $(u_n)_{n=0, 1, \ldots}$ を$r$階の線形回帰数列 (linear recurrence sequence) という。
$$a_i=-s_{r-i}\ (i=0, 1, \ldots, r-1)$$
とおくと、\eqref{eq11} は
$$u_{n+r}+a_{r-1}u_{n+r-1}+a_{r-2}u_{n+r-2}+\cdots +a_0 u_n=0$$
と書き直すことができる。
これに対応する多項式
$$P(X)=X^r+a_{r-1}X^{r-1}+\cdots a_0$$
を $(u_n)_{n=0, 1, \ldots}$ の特性多項式 (characteristic polynomial) という。

一般項

線形回帰数列の一般項が特性多項式の根を用いてあらわされることを示す。まず、次の特殊な数列が線形回帰数列となっていることを確かめる。
以下この節では、$\K$ の標数は $0$ であり、$a_r=1$ とおいた特性多項式が $\K$ 上で
$$P(X)=\prod_{i=1}^h(X-\alpha_i)^{e_i}$$
と分解し、$\alpha_1,\ldots,\alpha_h$ は相異なる非零元、$e_1+\cdots+e_h=r$ であると仮定する。特性多項式が $\K$ 上で分解しない場合は分解体へ係数を拡大して同じ議論を適用する。標数が正の場合には $n^k$ が異なる多項式関数を与えないことがあるため、以下の一般項表示をそのまま用いることはできない。

このとき、$0\leq k\leq e_i-1$ ならば
$$u_n=n^k \alpha_i^n$$
は\eqref{eq11}を満足する数列である。

$$\sum_{t=0}^r a_t u_{n+t}=\alpha_i^n\sum_{t=0}^r a_t (n+t)^k \alpha_i^t=\alpha_i^n\sum_{j=0}^k n^j \binom{k}{j} \left(\sum_{t=0}^r a_t t^{k-j} \alpha_i^t\right)$$
となる。
各 $k-j$ について、
$$X^{k-j}=\sum_{m=0}^{k-j} b_{k-j, m} X(X-1)\cdots (X-m+1)$$
とおくと、
$$\begin{split} \sum_{t=0}^r a_t t^{k-j} X^t= & \sum_{t=0}^r \sum_{m=0}^{k-j} a_t b_{k-j, m}t(t-1)\cdots(t-m+1) X^t \\ = & \sum_{m=0}^{k-j} b_{k-j, m}X^m\sum_{t=m}^r a_t t(t-1)\cdots(t-m+1) X^{t-m} \\ = & \sum_{m=0}^{k-j} b_{k-j, m}X^mP^{(m)}(X). \end{split}$$
となるので、
$$\sum_{t=0}^r a_t (n+t)^k \alpha_i^t=\sum_{j=0}^k n^j \binom{k}{j} \left(\sum_{m=0}^{k-j} b_{k-j, m} P^{(m)}(\alpha_i) \alpha_i^m\right)$$
となる。しかし $0\leq m\leq k-j\leq e_i-1$ より $P^{(m)}(\alpha_i)=0$ であるから
$$\sum_{t=0}^r a_t u_{n+t}=\alpha_i^n\sum_{t=0}^r a_t (n+t)^k \alpha_i^t=0$$
となる。

$k=1, 2, \ldots, m$ について数列 $(v_n^{(k)})_{n=0, 1, \ldots}$ が\eqref{eq11}を満足しているとする。このとき
$$w_n=\sum_{k=1}^m b_k v_n^{(k)}$$
で定義される数列 $(w_n)_{n=0, 1, \ldots}$ も\eqref{eq11}を満足する。

$$\begin{split} w_{n+r}=\sum_{k=1}^m b_k v_{n+r}^{(k)}= & \sum_{k=1}^m b_k\left(\sum_{i=1}^r s_i v_{n+r-i}^{(k)}\right) \\ = & \sum_{i=1}^r s_i \left(\sum_{k=1}^m b_k v_{n+r-i}^{(k)}\right) \\ = & \sum_{i=1}^r s_i w_{n+r-i}. \end{split}$$

とくに、$1\leq i\leq h, 0\leq k\leq e_i-1$ に対して数列 $(w_n^{(i, k)})_{n=0, 1, \ldots}$ を
$$w_n^{(i, k)}=n^k \alpha_i^n$$
と定めると、定理1 から各 $(w_n^{(i, k)})_{n=0, 1, \ldots}$ は\eqref{eq11}を満足するから
$$u_n=\sum_{i, k} b_{i, k}w_n^{(i, k)}=\sum_{i, k} b_{i, k}n^k \alpha_i^n$$
で定義される数列 $(u_n)_{n=0, 1, \ldots}$ も\eqref{eq11}を満足する。
$\K$ 上の数列 $(u_n)_{n=0, 1, \ldots}$ 全体のなす空間 $\K^\N$ は項ごとの和とスカラー倍
$$(u_n)_{n=0, 1, \ldots}+(v_n)_{n=0, 1, \ldots}=(u_n+v_n)_{n=0, 1, \ldots}, k(u_n)_{n=0, 1, \ldots}=(ku_n)_{n=0, 1, \ldots}$$
により、$\K$ 上のベクトル空間となる。
$\mathbb{V}$ を、\eqref{eq11}を満足する数列全体のなす空間とすると、定理2 から $\mathbb{V}$ は $\K^\N$ の部分ベクトル空間となる。
数列 $W^{(i, k)}=(w_n^{(i, k)})_{n=0, 1, \ldots}$ を
$$w_n^{(i, k)}=n^k \alpha_i^n$$
と定め、このような数列で生成されるベクトル空間を $\mathbb{W}$ とおく。
定理2 より、
$$u_n=\sum_{i, k} b_{i, k}w_n^{(i, k)}=\sum_{i, k} b_{i, k}n^k \alpha_i^n$$
で与えられる数列は\eqref{eq11}を満足するが、逆に\eqref{eq11}を満足する数列はこの形で与えられる。すなわち、つぎの定理が成り立つ。

$$\mathbb{V}=\mathbb{W}$$ が成り立つ。

\eqref{eq11}を満足する数列は $u_0, u_1, \ldots, u_{r-1}$ から一意的に定まるので、$k=0, 1, \ldots, r-1$ に対して $v_k^{(k)}=1, v_i^{(k)}=0\ (0\leq i\leq r-1, i\neq k)$ および\eqref{eq11}で定まる数列を $(v_n^{(k)})_{n=0, 1, \ldots}$ とおくと、$\mathbb{V}$ はこれら $r$ 個の数列により生成される。初期値への制限写像 $\mathbb{V}\to\K^r$ は全単射だから、$\dim_{\K}\mathbb{V}=r$ である。
数列 $W^{(i, k)}=(w_n^{(i, k)})_{n=0, 1, \ldots}$ を
$$w_n^{(i, k)}=n^k \alpha_i^n$$
と定める。これらが線型独立であることを示す。数列の左シフトを $(Eu)_n=u_{n+1}$ と書く。$q(n)\alpha_i^n$ 型の数列に対して
$$ (E-\alpha_j)\bigl(q(n)\alpha_i^n\bigr) =\alpha_i^n\bigl(\alpha_iq(n+1)-\alpha_jq(n)\bigr) $$
である。$j=i$ なら右辺の多項式部分の次数は1つ下がり、$j\neq i$ ならその最高次係数には非零元 $\alpha_i-\alpha_j$ が掛かる。したがって $(E-\alpha_i)^{e_i}$ は $q(n)\alpha_i^n$（$\deg q< e_i$）をすべて零にし、$j\neq i$ なら $E-\alpha_j$ はこの空間上の全単射である。
いま
$$\sum_{i=1}^h q_i(n)\alpha_i^n=0,\qquad \deg q_i< e_i$$
とする。固定した $i$ について $\prod_{j\neq i}(E-\alpha_j)^{e_j}$ を作用させると、$i$ 以外の項は消え、$i$ の項には全単射が作用するので $q_i(n)\alpha_i^n=0$ となる。$\alpha_i\neq0$ であり、標数 $0$ の体上では次数 $e_i$ 未満の多項式が $n=0,1,\ldots$ ですべて零なら零多項式だから、$q_i=0$ である。これは各 $i$ について成り立つので $W^{(i,k)}$ は線型独立である。個数は $\sum_i e_i=r$ だから、$\dim_{\K}\mathbb{W}=r$ である。
また、定理1 より $\mathbb{W}$ に属する数列は\eqref{eq11}を満足するので、$\mathbb{W}$ は $\mathbb{V}$ の部分空間である。
しかし、$\mathbb{V}$ と $\mathbb{W}$ の次元はともに $r$ であるから
$$\mathbb{V}=\mathbb{W}$$
が成り立つ。

&&&ex [ex11]
Fibonacci数列 ( OEIS:A000045 )
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$$
は漸化式
$$F_0=0, F_1=1, F_{n+2}=F_{n+1}+F_n\ (n=0, 1, \ldots)$$
により定義される。
$$\alpha=\frac{1+\sqrt{5}}{2}, \beta=\frac{1-\sqrt{5}}{2}$$
を方程式
$$x^2-x-1=0$$
の解とすると、定理3 より
$$F_n=\kappa\alpha^n+\lambda\beta^n\ (n=0, 1, \ldots)$$
となる $\kappa, \lambda$ が存在する。$F_0=0, F_1=1$ より
$$\lambda=-\kappa, \kappa\alpha+\lambda\beta=\kappa(\alpha-\beta)=1$$
となるので $\kappa=1/(\alpha-\beta), \lambda=-1/(\alpha-\beta)$ が得られるので $(F_n)_{n=0, 1, \ldots)$ は $$F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$$ とあらわされる。 &&& &&&ex [ex12] **Padovan数列** ([OEIS:A000931](http://oeis.org/A000931)) $$1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, \ldots$$ は $$u_0=1, u_1=0, u_2=0, u_{n+3}=u_{n+1}+u_n\ (n=0, 1, \ldots)$$ により定まる数列である。 $$X^3-X-1=0$$ の解は $1$ の原始 $3$ 乗根 $\omega=(-1\pm\sqrt{-3})/2$ を用いて $$x_k=\frac{\omega^k\sqrt[3]{9+\sqrt{69}}+\omega^{-k}\sqrt[3]{9-\sqrt{69}}}{\sqrt[3]{18}}\ (k=0, 1, 2)$$ であらわされ、Padovan数列 $(u_n)_{n=0, 1, \ldots)$ は $$u_n=\frac{x_0^n}{2x_0+3}+\frac{x_1^n}{2x_1+3}+\frac{x_2^n}{2x_2+3}$$ とあらわされる。 $1, 2, \ldots, n$ を引き続く $2$ 個または $3$個の整数の組に分割する方法の総数は $u_{n+3}$ に一致する。また Padovan数列はある種の[[多重ゼータ値]]のなす空間の $\Q$ 上の次元をあらわしていると予想されている。すなわち、$u_{k+3}$ は重さ $k$ の許容インデックスから生成される多重ゼータ値のなす空間の $\Q$ 上の次元をあらわしていると予想されている（Zagierの次元予想）。 &&&