線形回帰数列

$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\K}{\mathbb{K}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$

体 $\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_0\ (n=0, 1, \ldots)\ \ (1.1)$$ が成り立っている数列 $(u_n)_{n=0, 1, \ldots}$ を$r$階の線形回帰数列 (linear recurrence sequence) という。 $$a_i=-s_{r-i}\ (i=0, 1, \ldots, r-1)$$ とおくと、$(1.1)$ は $$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)という。

一般項

線形回帰数列の一般項が特性多項式の根を用いてあらわされることを示す。まず、次の特殊な数列が線形回帰数列となっていることを確かめる。

定理 1

$$P(X)=(X-\alpha_1)^{e_1}(X-\alpha_2)^{e_2}\cdots (X-\alpha_h)^{e_h}$$ と因数分解されるとする。このとき、$0\leq k\leq e_i-1$ ならば $$u_n=n^k \alpha_i^n$$ は $(1.1)$ を満足する数列である。

Proof.

$$\sum_{t=0}^r a_t u_{n+t}=\sum_{t=0}^r a_t (n+t)^k \alpha_i^t=\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}=\sum_{t=0}^r a_t (n+t)^k \alpha_i^t=0$$ となる。

□

定理 2

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

Proof.

$$\begin{split} w_{n+r}=\sum_{k=1}^m b_k v_n^{(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}$ は $(1.1)$ を満足するから $$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}$ も $(1.1)$ を満足する。

$\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}$ を、$(1.1)$ を満足する数列全体のなす空間とすると、定理 2から $\mathbb{V}$ は $\K^\N$ の部分ベクトル空間となる。

数列 $W^{(i, k)}=(v_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$$ で与えられる数列は $(1.1)$ を満足するが、逆に $(1.1)$ を満足する数列はこの形で与えられる。すなわち、つぎの定理が成り立つ。

定理 3

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

Proof.

$(1.1)$ を満足する数列は $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)$ および $(1.1)$ で定まる数列を $(v_n^{(k)})_{n=0, 1, \ldots}$ とおくと $U$ は $(v_n^{(k)})_{n=0, 1, \ldots}$ $(k=0, 1, \ldots, r-1)$ により生成されるので、$\K$ 上の次元は $r$ である。

数列 $W^{(i, k)}=(v_n^{(i, k)})_{n=0, 1, \ldots}$ を $$w_n^{(i, k)}=n^k \alpha_i^n$$ と定めると、$W^{(i, k)}$ は $\K$ 上線型独立である。よって $\mathbb{W}$ の $\K$ 上の次元は $r$ と一致する。 また、定理 1より $\mathbb{W}$ に属する数列は $(1.1)$ を満足するので、$\mathbb{W}$ は $\mathbb{V}$ の部分空間である。 しかし、$\mathbb{V}$ と $\mathbb{W}$ の次元はともに $r$ であるから $$\mathbb{V}=\mathbb{W}$$ が成り立つ。

□

例 1

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), \kappa=-1/(\alpha-\beta)$ が得られるので $(F_n)_{n=0, 1, \ldots}$ は $$F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$$ とあらわされる。

例 2

Padovan数列 (OEIS: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_{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の次元予想）。