線形漸化的数列

難易度目安：6 分野：多項式・形式的べき級数 Discord（質問・議論）

▶ YouTube で解説動画を見る ↗

1. 概要

本講座では，線形漸化的数列について解説します．

線形漸化的数列とはある種の漸化式を満たす数列のことで，代表例としては漸化式

$$ F _ i = F _ {i-1} + F _ {i-2}\quad (i\geq 2) $$

を満たす Fibonacci 数列

$$ F = (0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots) $$

があります．

線形漸化的数列は多項式や形式的べき級数，行列累乗などと密接に関係があります．競技プログラミングでも，興味のある数列が形式的べき級数の係数や行列累乗の成分として現れることはよくあり，重要な対象です．

本講座では，線形漸化的数列と多項式，形式的べき級数，行列累乗との関係を整理し，多くの問題を通して理解を深めることを目指します．

線形漸化的数列については，第 $K$ 項を高速に計算する問題や，数列から漸化式を復元する問題も重要です．このような問題は本講座の後続講座で扱います．

2. 前提知識

本講座では，次の知識を仮定します．

• 形式的べき級数の定義，乗法逆元．
• 行列の積，行列累乗．
• Cayley–Hamilton の定理（6.1 節の定理の証明で一度用いますが，知らなければスキップ可能です）．

多項式 $f(x)$ の次数を $\deg f(x)$ と書きます．$f(x)=0$ の場合には $\deg 0=-\infty$ と定義します．

3. 線形漸化的数列

本講座を通して単位的可換環 $R$ をひとつ固定し，

• 数列の要素．
• 多項式や形式的べき級数の係数．
• 行列の成分．

などはすべて，$R$ の元とします．競技プログラミングにおいては，通常次のような例を想定しておけば十分です．

• 整数全体 $\mathbb{Z}$，有理数全体 $\mathbb{Q}$，複素数全体 $\mathbb{C}$．
• 正整数 $n$ や素数 $p$ を法とした整数演算に対応する $\mathbb{Z}/n\mathbb{Z}$，$\mathbb{F}_p$．

本講座の内容の多くの部分は任意の単位的可換環で成立します．ただし 5.3 節では $R=\mathbb{C}$ に限定した議論も行います．

3.1. 定義

【定義 1】（線形漸化的数列）

数列 $A=(A_0,A_1,A_2,\ldots)$ が 線形漸化的（linearly recurrent）であるとは，正整数 $d$ と $c_1,c_2,\ldots,c_d\in R$ が存在して，任意の $i\geq d$ に対して

$$ A_i=c_1A_{i-1}+c_2A_{i-2}+\cdots+c_dA_{i-d} $$

が成り立つことをいう．このような漸化式を，$A$ の定数係数線形漸化式（linear recurrence with constant coefficients）という．また，$d$ をこの定数係数線形漸化式の位数（order）という．

用語について

本講座でいう線形漸化的数列について，日本語，英語ともに複数の用語が使われています．日本語では

• 線形漸化式的数列
• 線形回帰数列
• （定数係数）線形漸化式を満たす数列

などの用語があります．英語では，

• linearly recurrent sequence，linear recurrence sequence
• C-recursive sequence，constant-recursive sequence
• C-finite sequence

などの用語があります．

また「線形漸化式」という用語の指す範囲は文脈によって様々で，例えば係数が添字 $i$ の関数であるような漸化式

$$ A _ i = c _ 1(i) A _ {i-1} + c_2(i) A _ {i-2} + \cdots + c _ d(i)A _ {i-d} $$

（ただし $c_j(i)$ は $i$ の関数）も線形漸化式と呼ぶことがあります．そのため本講座では，係数が定数であるような線形漸化式は，少し長くなりますが「定数係数線形漸化式」と記述しています．

定義揺れについて

文献によっては，線形漸化的数列を「十分大きなすべての $i$ に対して定数係数線形漸化式を満たす数列」と定義することもあります．この場合例えば，

$$ A_i = \begin{cases} i & (i = 0 , 1) \\\ 2 ^ i & (2 \leq i)\end{cases} $$

により定まる数列 $A=(0,1,4,8,16,32,\ldots)$ は，$i\geq 3$ に対して $A_i = 2A_{i-1}$ を満たすため線形漸化的数列ということになります．ただし，本講座の定義でもこの数列は

$$ A _ i = 2 A_{i - 1} + 0 \cdot A _ {i-2} + 0 \cdot A _ {i-3} \quad (i\geq 3) $$

という定数係数線形漸化式を満たすため，数列が線形漸化的であるかどうかには影響しません．ただし，どのような位数の定数係数線形漸化式を満たすかには定義の違いが影響することがあります．

3.2. 線形漸化的数列の例 (1)

等比数列

定数 $r$ に対して，

$$ A _ i = r ^ i $$

で定まる数列は線形漸化的です．実際，

$$ A _ i = rA _ {i-1}\quad (i\geq 1) $$

を満たします．なお，この数列は他にも

$$ A _ i = r ^ 2 A _ {i-2}\quad (i\geq 2) $$

や

$$ A _ i = (r-1) A _ {i-1} + r A _ {i-2}\quad (i\geq 2) $$

などの漸化式も満たします．このように，線形漸化的数列に対してそれが満たす定数係数線形漸化式は一意ではありません．

Fibonacci 数列

$$ F _ 0 = 0,\quad F_1=1,\quad F _ i = F _ {i-1}+F _ {i-2}\quad (i\geq 2) $$

により定まる数列 $F=(0,1,1,2,3,5,8,13,21,\ldots)$ は線形漸化的数列です．$F$ は Fibonacci 数列と呼ばれます．

周期数列

$p$ を正整数とするとき，漸化式

$$ A_i=A_{i-p}\quad (i\geq p) $$

を満たす数列は，周期 $p$ を持つ数列であるといいます．周期 $p$ を持つ数列は線形漸化的です．

4. 形式的べき級数との関係

線形漸化的数列は，母関数が有理式で表される数列として特徴づけられます．

4.1. 定理

数列 $A=(A_0,A_1,A_2,\ldots)$ に対して，形式的べき級数

$$ A(x) = \sum _ {i\geq 0} A _ i x ^ i $$

を考えます．これを数列 $A$ の母関数（generating function）といいます．

【定理 2】

数列 $A=(A_0,A_1,A_2,\ldots)$ と正整数 $d$ について，次は同値である．

1. $A$ は位数 $d$ の定数係数線形漸化式を満たす．
2. 数列 $A$ の母関数を $A(x)$ とするとき，多項式 $P(x), Q(x)$ であって，以下の条件をすべて満たすものが存在する．
   • $A(x)=\dfrac{P(x)}{Q(x)}$．
   • $\deg P(x) < d$，$\deg Q(x)\leq d$．
   • $[x^0]Q(x)=1$．

証明

まず，1 を仮定して 2 を示します．$A$ が満たす定数係数線形漸化式を

$$ A _ i = c _ 1 A _ {i-1} + c _ 2A _ {i-2} + \cdots + c _ dA _ {i-d} \quad (i\geq d) $$

とします．

$$ Q(x) = 1 - c_1 x -c_2 x ^ 2 - \cdots - c_d x ^ d $$

とすれば，$i\geq d$ に対して

$$ [x ^ i] A(x)Q(x) = A _ i - (c _ 1 A _ {i-1} + c _ 2 A _ {i-2} + \cdots + c _ d A _ {i-d}) $$

となります．したがって

$$ [x ^ i]A(x)Q(x) = 0\quad (i\geq d) $$

が成り立ちます．このことは，$A(x)Q(x)$ が $d$ 次未満の多項式であることを示しています．この多項式を $P(x)$ とすれば，$P(x), Q(x)$ は

• $A(x)=\dfrac{P(x)}{Q(x)}$．
• $\deg P(x) < d$，$\deg Q(x)\leq d$．
• $[x^0]Q(x)=1$．

をすべて満たしています．

次に，2 を仮定して 1 を示します．やはり $Q(x) = 1 - c_1 x -c_2 x ^ 2 - \cdots - c_d x ^ d$ とすれば，$A(x)=\dfrac{P(x)}{Q(x)}$ について

$$ [x ^ i]A(x)Q(x)=0\quad (i\geq d) $$

が成り立ちます．このことは $A(x)$ の係数列 $A$ が定数係数線形漸化式

$$ A _ i = c _ 1 A _ {i-1} + c _ 2 A _ {i-2} + \cdots + c _ d A _ {i-d} \quad (i\geq d) $$

を満たす線形漸化的数列であることを意味しています．以上により示されました．

□

【問題 3】

Fibonacci 数列 $F = (F_0, F_1, \ldots)$ の母関数 $F(x) = \sum_{i=0} ^ {\infty} F_i x ^ i$ を有理式として表してください．

解説

漸化式より $i\geq 2$ に対して $F _ i - F _ {i-1} - F _ {i-2}=0$ が成り立ちます．したがって

$$ [x ^ i] (1 - x - x ^ 2)F(x) = 0\quad (i\geq 2) $$

が成り立ちます．さらに $(1 - x - x ^ 2)F(x)$ を $1$ 次の係数まで計算することで，

$$(1 - x - x ^ 2)F(x) = x$$

が分かります．したがって

$$ F(x) = \frac{x}{1 - x - x ^ 2} $$

です．

【問題 4】

母関数

$$ A(x) = \frac{1 + 2x}{1 - 2x - 3x ^ 2} $$

の係数を

$$ A(x) = \sum_{i\geq 0}A _ i x ^ i $$

と書きます．このとき，数列 $A$ が満たす線形漸化式を求めてください．また，$A_0,A_1,A_2,A_3,A_4,A_5$ を求めてください．

解説

$(1 - 2x - 3x ^ 2)A(x) = 1+2x$ より，特に

$$ [x ^ i] (1 - 2x - 3x ^ 2)A(x) = 0\quad (i\geq 2) $$

が成り立ちます．したがって，数列 $A$ は定数係数線形漸化式

$$ A _ i = 2 A _ {i-1} + 3 A _ {i-2}\quad (i\geq 2) $$

を満たします．

また，$(1 - 2x - 3x ^ 2)A(x)=1+2x$ における $0$ 次，$1$ 次の係数を比べることで

$$ A_0 = 1,\quad A_1 - 2A_0 =2 $$

となるので $A_0 = 1, A_1 = 4$ です．この初期値と漸化式から

$$ A_0 = 1, A_1 = 4, A_2 = 11, A_3 = 34, A_4 = 101, A_5 = 304 $$

が分かります．

4.2. 線形漸化的数列の例 (2)

定理やその応用として，様々な数列が線形漸化的であることが確かめられます．いくつかの問題を通して，そのような例を紹介します．

【問題 5】

$A=(A_0,A_1,A_2,\ldots)$ を線形漸化的数列とし，

$$ B_i=\sum_{j=0}^i A_j $$

と定めます．このとき，$B=(B_0,B_1,B_2,\ldots)$ が線形漸化的数列であることを示してください．

また，Fibonacci 数列の累積和

$$ B_i=\sum_{j=0}^i F_j $$

はどのような定数係数線形漸化式を満たすかを答えてください．

解説

$B_i = \sum _ {j=0} ^ i A_j$ であるとき，母関数

$$ A(x) = \sum _ {i=0} ^ {\infty} A _ i x ^ i, \qquad B(x) = \sum _ {i=0} ^ {\infty} B _ i x ^ i $$

の間には

$$ B(x) = A(x) (1 + x + x ^ 2 + \cdots) = \frac{A(x)}{1-x} $$

という関係があります．ここから，$A(x)=\dfrac{P(x)}{Q(x)}$ と有理式で表されるとき，$B(x)=\dfrac{P(x)}{(1-x)Q(x)}$ も有理式で表されます．したがって $B$ は線形漸化的です．

特に $A_i$ が Fibonacci 数列である場合には，$A(x)=\dfrac{x}{1-x-x^2}$ より

$$ B(x)=\frac{x}{(1-x)(1-x-x ^ 2)}=\frac{x}{1-2x+x ^ 3} $$

です．したがって $B_i$ は定数係数線形漸化式

$$ B _ i = 2B _ {i-1} - B _ {i-3} \quad (i\geq 3) $$

を満たします．

【問題 6】

$F=(F_0,F_1,F_2,\ldots)$ を Fibonacci 数列とします．初期値 $A_0,A_1$ と漸化式

$$ A _ {i} = 2A _ {i-1} + 3A _ {i-2} + F_i \quad (i\geq 2) $$

によって定まる数列 $A$ が線形漸化的数列であることを示してください．

解説

$A(x), F(x)$ を $A, F$ の母関数とします．【定理 2】 と同様の議論から，

$$ [x ^ i] \left((1 - 2x - 3x ^ 2)A(x)-F(x)\right) = 0 \quad (i\geq 2) $$

であることが分かります．したがってある $1$ 次以下の多項式 $P(x)$ に対して

$$ (1 - 2x - 3x ^ 2)A(x)-F(x)=P(x) $$

が成り立ちます．$F(x)=\dfrac{x}{1 - x - x ^ 2}$ より

$$ A(x) =\frac{P(x)+F(x)}{1-2x-3x ^ 2} =\frac{(1-x-x ^ 2)P(x)+x}{(1-x-x ^ 2)(1-2x-3x ^ 2)} =\frac{(1-x-x ^ 2)P(x)+x}{1 - 3x - 2x ^ 2 + 5x ^ 3 + 3x ^ 4} $$

です．分子 $(1-x-x ^ 2)P(x)+x$ は $3$ 次以下なので，$A$ は定数係数線形漸化式

$$ A _ i = 3 A _ {i-1} + 2A_{i-2}- 5 A _ {i-3} - 3 A _ {i-4}\quad (i\geq 4) $$

を満たす線形漸化的数列です．

【問題 7】

$F=(F_0,F_1,F_2,\ldots)$ を Fibonacci 数列とします．数列 $A$ を

$$ A_i= \begin{cases} F_{i/2} & (i\equiv 0\pmod 2), \\\ 2 ^ {(i-1)/2} & (i\equiv 1\pmod{2}) \end{cases} $$

によって定めます．つまり

$$ A = (F_0, 1, F_1, 2, F_2, 4, F_3, 8, F_4, 16, \ldots) $$

です．数列 $A$ が線形漸化的であることを示してください．

解説

• 数列 $(A_0, A_2, A_4, \ldots)$ の母関数を $B(x)$，
• 数列 $(A_1, A_3, A_5, \ldots)$ の母関数を $C(x)$

とすれば，$A$ の母関数 $A(x)$ について

$$ A(x) = B(x ^ 2) + x C(x ^ 2) $$

が成り立ちます．$B(x) = \dfrac{x}{1 - x - x ^ 2}$，$C(x) = \dfrac{1}{1 - 2 x}$ なので，

$$ A(x) = \frac{x ^ 2}{1 - x ^ 2 - x ^ 4} + \frac{x}{1 - 2 x ^ 2} $$

であり，母関数が有理式で表されたため $A$ は線形漸化的です．

このように，既知の線形漸化式を周期的に組み合わせたような数列も線形漸化的になります．

5. 多項式・等比数列との関係

線形漸化的数列の代表例として，多項式で表される数列や，それと等比数列の積が挙げられます． 複素数列の場合には，すべての線形漸化的数列はそのような数列の線形結合であることが分かります．

5.1. 多項式

多項式で表される数列は線形漸化的です．

【定理 8】

$f(x)$ を $k$ 次以下の多項式とし，$A=(A_0,A_1,\ldots)$ を $A_i=f(i)$ により定まる数列とする．$A(x)=\sum_{i=0} ^ {\infty} A _ i x ^ i$ をその母関数とするとき，

$$ A(x) = \dfrac{P(x)}{(1-x) ^ {k+1}} $$

を満たす $k$ 次以下の多項式 $P(x)$ が存在する．特に $A$ は線形漸化的である．

証明

$A(x)(1-x)^{k+1}$ が $k$ 次以下の多項式であることを示せばよいです．多項式の列 $P_0(x), P_1(x), \ldots$ を次の漸化式によって定義します．

$$ \begin{aligned} P _ 0(x) &= f(x), \\\ P _ {j + 1}(x) &= P _ {j}(x) - P _ {j}(x - 1)．\quad (j\geq 0) \end{aligned} $$

$P _ j(x)$ が $d$ 次多項式であるとき，$P _ {j+1}(x)$ は $d-1$ 次以下の多項式となります．特に $P _ {k+1}(x)=0$ が成り立ちます．

ここで $j$ に関する帰納法によって次が成り立つことを証明します．

$$ [x ^ i] A(x)(1-x) ^ {j} = P_j(i) \quad (i\geq j) $$

$j=0$ のときは $P_0(x) = f(x)$ から明らかです．$j$ での成立を仮定して，$j+1$ での成立を示します．

$$ \begin{aligned} [x ^ i]A(x)(1-x) ^ {j+1} &= [x ^ i]\left((1-x)\cdot A(x)(1-x) ^ j\right) \\\ &= \left([x ^ i]A(x)(1-x) ^ j\right) - \left([x ^ i]x\cdot A(x)(1-x) ^ j\right) \\\ &= \left([x ^ i]A(x)(1-x) ^ j\right) - \left([x ^ {i-1}]A(x)(1-x) ^ j\right) \end{aligned} $$

となるので，$i\geq j+1$ のときこれは $P_j(i) - P_j(i-1) = P_{j+1}(i)$ となります．よって帰納法により

$$ [x ^ i]A(x)(1-x) ^ {j} = P_j(i) \quad (i\geq j) $$

が示されました．特に $j=k+1$ とすると，$P_{k+1}(x)=0$ より

$$ [x ^ i]A(x)(1-x) ^ {k+1} = 0 \quad (i\geq k+1) $$

が得られます．これは $A(x)(1-x) ^ {k+1}$ が $x$ の $k$ 次以下の多項式であることを示しています．以上で定理が示されました．

□

【問題 9】

$k=0,1,2,3$ の場合に，$A_i=i^k$ の母関数を $\dfrac{P(x)}{(1-x) ^ {k + 1}}$ の形で表してください．

解説

$A(x)(1-x)^{k+1}$ の係数を $k$ 次以下の部分について計算することで，答が計算できます．結論は次の通りです．

$$ \begin{aligned} \sum _ {i = 0} ^ {\infty} i ^ 0 x ^ i &= \frac{1}{1-x},\\\ \sum _ {i = 0} ^ {\infty} i ^ 1 x ^ i &= \frac{x}{(1-x) ^ 2},\\\ \sum _ {i = 0} ^ {\infty} i ^ 2 x ^ i &= \frac{x + x ^ 2}{(1-x) ^ 3},\\\ \sum _ {i = 0} ^ {\infty} i ^ 3 x ^ i &= \frac{x + 4 x ^ 2 + x ^ 3}{(1-x) ^ 4}． \end{aligned} $$

なお，$\displaystyle \sum _ {i = 0} ^ {\infty} i ^ k x ^ i = \dfrac{A_k(x)}{(1-x) ^ {k + 1}}$ を満たす多項式 $A _ k(x)$ は Eulerian polynomial と呼ばれることがあります．ただし，$k\geq 1$ に対して $A_k(x)=xE_k(x)$ により定まる多項式 $E_k(x)$ の方を Eulerian polynomial と呼ぶ流儀もあります（つまり $x$ 倍の定義揺れがあります）．

5.2. 多項式と等比数列の積

【定理 10】

$r$ を定数，$f(x)$ を $k$ 次以下の多項式とし，$A=(A_0,A_1,\ldots)$ を $A_i=r ^ i f(i)$ により定まる数列とする．$A(x)=\sum_{i=0} ^ {\infty} A _ i x ^ i$ をその母関数とするとき，

$$ A(x) = \dfrac{P(x)}{(1-rx) ^ {k+1}} $$

を満たす $k$ 次以下の多項式 $P(x)$ が存在する．特に $A$ は線形漸化的である．

証明

$2$ つの数列 $A=(A_0, A_1, \ldots)$，$B=(B_0, B_1, \ldots)$ の間に $A_i = r ^ i B _ i$ の関係式があるとき，その母関数には

$$A(x) = B(rx)$$

という関係式があります．このことと 【定理 8】 より明らかです．

□

【問題 11】

$A_i = (1 + 2i)\cdot 3 ^ i$ により定まる数列 $A=(A_0,A_1,\ldots)$ について，$A$ の満たす定数係数線形漸化式をひとつ答えてください．

解説

【定理 10】 より，ある $1$ 次以下の多項式 $P(x)$ に対して

$$ A(x) = \frac{P(x)}{(1-3x) ^ 2} = \frac{P(x)}{1 - 6x + 9 x ^ 2} $$

が成り立ちます．したがって $A$ は線形漸化的で，定数係数線形漸化式

$$ A_i = 6 A_{i-1} - 9 A _ {i - 2}\quad (i\geq 2) $$

を満たします．なお，$A(x)(1 - 3 x) ^ 2$ を $1$ 次の係数まで計算することで，$A(x) = \dfrac{1+3x}{(1-3x) ^ 2}$ であることも分かります．

5.3. 参考：部分分数分解による表示

まず，次のよく知られた恒等式を確認します．

【定理 12】

$k$ を非負整数とするとき，

$$ \frac{1}{(1-x)^{k+1}} = \sum_{i=0}^{\infty}\binom{i+k}{i}x^i $$

が成り立つ．

証明

様々な証明方法がありますが，ここでは組合せ的な証明を紹介します．

非負整数 $k, i$ に対して，

$$ \frac{1}{(1 - x) ^ {k+1}} = \sum _ {i=0} ^ {\infty} a_{k , i} x ^ i $$

によって整数 $a_{k,i}$ を定義します．すると，非負整数 $k,i$ に対して

$$ \frac{1}{(1-x)^{k+2}} = \frac{1}{1-x}\cdot \frac{1}{(1-x) ^ {k+1}} = (1+x+ x ^ 2 + \cdots)\cdot \frac{1}{(1-x) ^ {k+1}} $$

より $a _ {k+1, i} = \sum _ {j\leq i} a _ {k, j}$ が成り立ちます．したがって

$$a _ {k+1,i+1} = a _ {k+1,i} + a _ {k,i+1}$$

が成り立ちます．

これはグリッドにおいてマス $(0,0)$ からマス $(k,i)$ まで，右方向または下方向への移動を繰り返して到達するための経路数が満たす漸化式と同一です．このことから $a_{k,i}$ はマス $(0,0)$ からマス $(k,i)$ までの経路数と一致することが分かり，

$$ a_{k,i}=\binom{k+i}{i} $$

であることが分かります．

□

5.3 節のこれ以降の部分では，数列の要素や多項式・形式的べき級数の係数を複素数範囲で考えます．

【定理 13】

$k$ を非負整数とします．複素数列 $A = (A_0, A_1, A_2,\ldots)$ の母関数 $A(x)$ が，ある $k$ 次以下の複素数係数多項式 $P(x)$ を用いて

$$ A(x)=\frac{P(x)}{(1-x)^{k+1}} $$

と表されるならば，ある複素数係数の $k$ 次以下の多項式 $f(x)$ が存在して，任意の $i\geq 0$ に対して $A_i=f(i)$ が成り立つ．

証明

$P(1-x) = \sum _ {0\leq j\leq k} p _ j x ^ j$ により係数列 $p_0, p_1, \ldots, p_k$ を定めると，

$$ P(x) = \sum _ {0\leq j\leq k} p _ j (1-x) ^ j $$

です．したがって

$$ A(x)=\sum_{0\leq j\leq k}\frac{p_j}{(1-x)^{k+1-j}} $$

が成り立ちます．【定理 12】 より，$\dfrac{1}{(1-x)^{k+1-j}}$ の $x ^ i$ の係数は

$$ \binom{i+k-j}{i}=\binom{i+k-j}{k-j} $$

です．これは $i$ の $k-j$ 次以下の多項式です．よって $A_i$ は，$i$ の $k$ 次以下の多項式の線形結合で表されます．したがって，ある $k$ 次以下の多項式 $f(x)$ が存在して，任意の $i\geq 0$ に対して $A_i=f(i)$ が成り立ちます．

□

【系 14】

$k$ を非負整数とし，$r$ を $0$ でない複素数とする．複素数列 $A = (A_0, A_1, A_2,\ldots)$ の母関数 $A(x)$ が，ある $k$ 次以下の複素数係数多項式 $P(x)$ を用いて

$$ A(x)=\frac{P(x)}{(1-rx)^{k+1}} $$

と表されるならば，ある複素数係数の $k$ 次以下の多項式 $f(x)$ が存在して，任意の $i\geq 0$ に対して $A_i=r^if(i)$ が成り立つ．

証明

$B(x)=A(x/r)$ とすると，$B(x)=\dfrac{P(x/r)}{(1-x)^{k+1}}$ であり，$P(x/r)$ は $k$ 次以下の多項式です．したがって 【定理 13】 よりある $k$ 次以下の多項式 $f(x)$ が存在して，$B(x)$ の係数 $B_i = [x ^ i]B(x)$ について $B_i = f(i)$ が成り立ちます．

$A(x) = B(rx)$ より $A _ i = r ^ i B _ i$ が成り立つので，$A_i = r ^ i f(i)$ です．

□

さらに，複素数係数の有理式に関する部分分数分解の理論を用いると，任意の線形漸化的数列は（有限項の例外を除き）$f(i)r ^ i$ の形の数列の線形結合であることが分かります．

【定理 15】（部分分数分解）

複素数係数有理式 $A(x)=\dfrac{P(x)}{Q(x)}$ （$[x ^ 0] Q(x) = 1$）に対して，ある多項式 $f(x)$ と，有限個の $0$ でない複素数 $r_j$，非負整数 $k_j$，$k_j$ 次以下の多項式 $P_j(x)$ であって，次を満たすものが存在する．

$$ A(x) = f(x) + \sum_{j}\frac{P_j(x)}{(1-r_jx)^{1+k_j}} $$

この定理を証明するには少し準備が必要であり，また本講座では重要性が低いため，証明を省略します．興味のある方は，「代数学の基本定理」「部分分数分解」等の検索語で調べてみてください．

【定理 16】

複素数列 $A=(A_0,A_1,A_2,\ldots)$ について，次は同値である．

1. $A$ は線形漸化的数列である．
2. 有限個の $0$ でない複素数 $r_j$，多項式 $f_j(x)$ が存在して，十分大きなすべての整数 $i$ について $A_i=\sum_j f_j(i)r_j^i$ が成り立つ．

証明

【定理 15】 および 【系 14】 から従います．なお，【定理 15】 に現れる多項式部分 $f(x)$ は母関数の有限個の係数にのみ影響するため，係数列の表示では有限個の例外が生じます．

□

【問題 17】

Fibonacci 数列の第 $i$ 項を，$F_i=\sum_j f_j(i)r_j^i$ の形で表してください．

解説

$a = \dfrac{1+\sqrt{5}}{2}, b = \dfrac{1-\sqrt{5}}{2}$ とおくと，$1-x-x ^ 2 = (1-ax)(1-bx)$ が成り立ちます．母関数 $F(x)$ は

$$ F(x) = \frac{x}{1-x-x ^ 2} =\frac{1}{a - b}\left(\frac{1}{1-ax}-\frac{1}{1-bx}\right) $$

と部分分数分解できます．このことから

$$ F_i = \frac{1}{a-b}(a ^ i - b ^ i) = \frac{1}{\sqrt 5}\left( \left(\frac{1+\sqrt{5}}{2}\right) ^ i - \left(\frac{1-\sqrt{5}}{2}\right) ^ i \right) $$

が得られます．

6. 行列との関係

線形漸化的数列を，行列累乗により表される数列として特徴づけることもできます．

6.1. 定理

【定理 18】

数列 $A=(A_0,A_1,A_2,\ldots)$ と正整数 $d$ について，次は同値である．

1. $A$ は位数 $d$ の定数係数線形漸化式を満たす．
2. ある $d\times d$ 行列 $M$ が存在して，$A_i$ は $M ^ i$ の成分の線形結合である．つまりある $d ^ 2$ 個の定数 $w_{p,q}$ ($0\leq p,q < d$) が存在して $$ A_i = \sum_{0\leq p,q < d}w_{p,q}(M ^ i)_{p,q} $$ が成り立つ．ここで $(M ^ i)_{p,q}$ は $M ^ i$ の $(p,q)$ 成分である．また，行列の行番号，列番号は $0$-based index であるとする．

証明

まず 1 $\implies$ 2 を示します．$A$ が満たす定数係数線形漸化式を

$$ A_i = c_1A _ {i-1} + c_2 A _ {i-2} + \cdots + c_d A _ {i-d} \quad (i\geq d) $$

とします．非負整数 $i$ に対して列ベクトル $V_i$ を

$$ V_i = \begin{pmatrix} A _ {i} \\\ A _ {i+1} \\\ A _ {i+2} \\\ \vdots \\\ A _ {i+d-3} \\\ A _ {i+d-2} \\\ A _ {i+d-1} \\\ \end{pmatrix} $$

により定めます．すると，漸化式より，任意の非負整数 $i$ について $V _ {i+1} = MV _ i$ が成り立つような $d\times d$ 行列 $M$ を作ることができます．実際，次のように $M$ を定めると，$V _ {i+1} = MV _ i$ が成り立ちます．

$$ M= \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 0 & 0 \\\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\\ 0 & 0 & 0 & 0 & \cdots & 1 & 0 \\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\\ c _ d & c _ {d-1} & c _ {d-2} & c _ {d-3} & \cdots & c _ 2 & c _ 1 \\\ \end{pmatrix}. $$

$M$ を左からかけることで添字が $1$ ずつ増えるという形になっており，これを繰り返し適用することで任意の非負整数 $i$ に対して

$$V _ {i}=M ^ iV _ {0}$$

が成り立つことが分かります．両辺の第 $0$ 成分を比べると

$$ A_i=\sum_{0\leq j < d}A_j\cdot (M ^ i) _ {0,j} $$

となり，右辺は $M ^ i$ の成分の線形結合です．以上で 1 $\implies$ 2 が示されました．

次に 2 $\implies$ 1 を示します．Cayley–Hamilton の定理より，ある定数 $c_1, c_2, \ldots, c_d$ に対して

$$ M ^ d = c _ 1 M ^ {d - 1} + c _ 2 M ^ {d-2} + \cdots + c_d I $$

が成り立ちます（ここで $I$ は単位行列を表します）．式全体に $M ^ {i-d}$ を左からかけることで，

$$ M ^ i = c _ 1 M ^ {i - 1} + c _ 2 M ^ {i-2} + \cdots + c_d M ^ {i-d}\quad (i\geq d) $$

が得られます．したがって任意の $(p,q)$ 成分が定数係数線形漸化式

$$ (M ^ i) _ {p,q} = c _ 1 (M ^ {i - 1}) _ {p,q} + c _ 2 (M ^ {i-2}) _ {p,q} + \cdots + c_d (M ^ {i-d}) _ {p,q}\quad (i\geq d) $$

を満たすため，その線形結合である $A_i$ も同じ漸化式

$$ A _ i = c _ 1 A _ {i-1} + c _ 2 A _ {i-2} + \cdots + c_d A _ {i-d}\quad (i\geq d) $$

を満たします．以上で 2 $\implies$ 1 が示されました．

□

同伴行列について

定数係数線形漸化式

$$ A_i = c_1A _ {i-1} + c_2 A _ {i-2} + \cdots + c_d A _ {i-d} \quad (i\geq d) $$

に対して，上の証明中で用いた行列

$$ \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots & 0 & 0 \\\ 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\\ 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\\ 0 & 0 & 0 & 0 & \cdots & 1 & 0 \\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\\ c _ d & c _ {d-1} & c _ {d-2} & c _ {d-3} & \cdots & c _ 2 & c _ 1 \\\ \end{pmatrix} $$

を同伴行列（companion matrix）と呼びます．同伴行列は線形漸化式や，行列の Frobenius 標準形の理論で重要になります．

なお，この行列の転置を同伴行列と呼ぶなどの定義揺れもあります．

【問題 19】

数列 $A=(A_0,A_1,A_2,\ldots)$ は $A_0 = 1, A_1 = 2$ および漸化式

$$ A_i=2A_{i-1}+3A_{i-2}\quad (i\geq 2) $$

を満たすとします．$A_i$ を，ある行列 $M$ の $i$ 乗の成分の線形結合として表してください．

解説

漸化式から，任意の $i\geq 2$ に対して

$$ \begin{pmatrix} A _ {i - 1} \\\ A _ {i} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\\ 3 & 2 \end{pmatrix} \begin{pmatrix} A _ {i - 2} \\\ A _ {i - 1} \end{pmatrix} $$

が成り立つので，

$$ M=\begin{pmatrix} 0 & 1 \\\ 3 & 2\end{pmatrix} $$

とすれば任意の非負整数 $i$ に対して

$$ \begin{pmatrix} A _ {i} \\\ A _ {i+1} \\\ \end{pmatrix} = M ^ i \begin{pmatrix} A _ {0} \\\ A _ {1} \\\ \end{pmatrix} = M ^ i \begin{pmatrix} 1 \\\ 2 \\\ \end{pmatrix} $$

が成り立ちます．したがって $A_i = (M ^ i)_{0,0} + 2(M ^ i)_{0,1}$ が成り立ちます．

【問題 20】

行列

$$ M= \begin{pmatrix} 1 & 2 \\\ 3 & 4 \end{pmatrix} $$

に対して，$M ^ i$ の $(0,0)$ 成分を $A_i$ と定めるとき，$A_i$ の満たす定数係数線形漸化式をひとつ求めてください．さらに $A_0, A_1, A_2, A_3, A_4$ を求めてください．

解説

Cayley–Hamilton の定理より $M ^ 2 - 5 M - 2 I = O$ が成り立ちます．したがって $i\geq 2$ に対して $M ^ i = 5 M ^ {i-1} + 2 M ^ {i-2}$ が成り立ちます．よってその $(0,0)$ 成分 $A_i$ は漸化式

$$ A _ i = 5A _ {i-1} + 2A _ {i-2}\quad (i\geq 2) $$

を満たします．$A_0 = 1, A_1 = 1$ なので，漸化式から

$$ A_0=1,A_1=1,A_2=7,A_3=37,A_4=199 $$

と計算できます．

6.2. 線形漸化的数列の例 (3)

【問題 21】

$2$ つの数列 $A=(A_0,A_1,\ldots)$，$B=(B_0,B_1,\ldots)$ を，初期値 $A_0=1,B_0=2$ および漸化式

$$ \begin{aligned} A_{i} &= 2A_{i-1} + 3B_{i-1}, \\\ B_{i} &= 4A_{i-1} + 5B_{i-1} \end{aligned} $$

により定めるとき，$A_i, B_i$ をある行列 $M$ の $i$ 乗の成分の線形結合として表してください．

解説

列ベクトル $V_i= \begin{pmatrix} A_i \\\ B_i \end{pmatrix} $ を考えると，漸化式から

$$ M = \begin{pmatrix} 2 & 3 \\\ 4 & 5\end{pmatrix} $$

に対して $V_i=MV_{i-1}$ $(i\geq 1)$ が成り立ちます．したがって $V_i=M^iV_0=M^i \begin{pmatrix} 1 \\\ 2 \end{pmatrix} $ が成り立つので，両辺の成分を比べることで

$$ A _ i=(M ^ i) _ {0,0} + 2(M ^ i) _ {0,1},\quad B _ i=(M ^ i) _ {1,0} + 2(M ^ i) _ {1,1} $$

と表せます．

【問題 22】

$2$ つの数列 $A=(A_0,A_1,\ldots)$，$B=(B_0,B_1,\ldots)$ を，初期値 $A_0=1,B_0=2$ および漸化式

$$ \begin{aligned} A_{i} &= 2A_{i-1} + 3B_{i-1} + i + 1, \\\ B_{i} &= 4A_{i-1} + 5B_{i-1} + 2i + 3 \end{aligned} $$

により定めるとき，$A_i, B_i$ をある行列 $M$ の $i$ 乗の成分の線形結合として表してください．

解説

列ベクトル $V_i= \begin{pmatrix} A_i \\\ B_i \\\ i \\\ 1 \end{pmatrix} $ を考えると，漸化式から

$$ M= \begin{pmatrix} 2 & 3 & 1 & 2 \\\ 4 & 5 & 2 & 5 \\\ 0 & 0 & 1 & 1 \\\ 0 & 0 & 0 & 1 \end{pmatrix} $$

に対して $V_i=MV_{i-1}$ $(i\geq 1)$ が成り立ちます．したがって $V_i=M^iV_0=M^i \begin{pmatrix} 1 \\\ 2 \\\ 0 \\\ 1 \end{pmatrix} $ が成り立つので，両辺の成分を比べることで

$$ \begin{aligned} A _ i &= (M ^ i) _ {0, 0} + 2 (M ^ i) _ {0, 1} + (M ^ i) _ {0, 3}, \\\ B _ i &= (M ^ i) _ {1, 0} + 2 (M ^ i) _ {1, 1} + (M ^ i) _ {1, 3} \end{aligned} $$

と表せます．

【問題 23】

$F=(F_0,F_1,F_2,\ldots)$ を Fibonacci 数列とします．$2$ つの数列 $A=(A_0,A_1,\ldots)$，$B=(B_0,B_1,\ldots)$ を，初期値 $A_0=1,B_0=2$ および漸化式

$$ \begin{aligned} A_{i} &= 2A_{i-1} + 3B_{i-1} + F _ i, \\\ B_{i} &= 4A_{i-1} + 5B_{i-1} \end{aligned} $$

により定めるとき，$A_i, B_i$ をある行列 $M$ の $i$ 乗の成分の線形結合として表してください．

解説

列ベクトル $ V_i= \begin{pmatrix} A_i \\\ B_i \\\ F_i \\\ F_{i+1} \end{pmatrix} $ を考えると，漸化式から

$$ M= \begin{pmatrix} 2 & 3 & 0 & 1 \\\ 4 & 5 & 0 & 0 \\\ 0 & 0 & 0 & 1 \\\ 0 & 0 & 1 & 1 \end{pmatrix} $$

に対して $V_i=MV_{i-1}$ $(i\geq 1)$ が成り立ちます．したがって $V_i=M^iV_0=M^i \begin{pmatrix} 1 \\\ 2 \\\ 0 \\\ 1 \end{pmatrix} $ が成り立つので，両辺の成分を比べることで

$$ \begin{aligned} A_i &= (M ^ i) _ {0,0} + 2 (M ^ i) _ {0,1} + (M ^ i) _ {0,3}, \\\ B_i &= (M ^ i) _ {1,0} + 2 (M ^ i) _ {1,1} + (M ^ i) _ {1,3} \end{aligned} $$

と表せます．

このようにいくつかの数列に対する連立漸化式によって数列を定義するという状況は，様々な問題における動的計画法の解法としてよく現れます．

【問題 24】

a，b，c からなる長さ $i$ の文字列 $S$ であって，aa，ba，bb を部分文字列として含まないものの個数を $A_i$ と書くことにします．$A_i$ をある行列 $M$ の $i$ 乗の成分の線形結合として表してください．

解説

• $X_i$ を，条件を満たす長さ $i$ の文字列であって，末尾が `a` であるものの個数とします．
• $Y_i$ を，条件を満たす長さ $i$ の文字列であって，末尾が `b` であるものの個数とします．
• $Z_i$ を，条件を満たす長さ $i$ の文字列であって，末尾が `a`，`b` ではないもの（空文字列または，末尾が `c` であるもの）の個数とします．

すると，$X_0 = 0, Y_0 = 0, Z_0 = 1$ および漸化式

$$ \begin{aligned} X _ i &= Z _ {i-1} \\\ Y _ i &= X _ {i-1} + Z _ {i-1} \\\ Z _ i &= X _ {i-1} + Y _ {i-1} + Z _ {i-1} \\\ \end{aligned}\quad (i\geq 1) $$

が成り立ちます．よって列ベクトル $V_i$ を $ V_i= \begin{pmatrix} X_i \\\ Y_i \\\ Z_i \end{pmatrix} $ により定め，行列 $M$ を

$$ M= \begin{pmatrix} 0 & 0 & 1 \\\ 1 & 0 & 1 \\\ 1 & 1 & 1 \\\ \end{pmatrix} $$

により定めると，$V_i = MV_{i-1}$ ($i\geq 1$) が成り立ちます．したがって $V_i=M^iV_0=M ^ i\begin{pmatrix}0 \\\ 0 \\\ 1\end{pmatrix}$ です．両辺の成分を比べることで

$$ X_i = (M ^ i) _ {0, 2},\quad Y_i = (M ^ i) _ {1, 2},\quad Z_i = (M ^ i) _ {2, 2} $$

が成り立ち，$A_i$ はこれらの和 $(M ^ i) _ {0, 2} + (M ^ i) _ {1, 2} + (M ^ i) _ {2, 2}$ と表せます．

【問題 25】

次の図のような $4$ 頂点のグラフがあります．頂点 $0$ から $1$ への長さ $i$ 以下のウォークの個数を $A_i$ とします．$A_i$ をある行列 $M$ の $i$ 乗の成分の線形結合として表してください．

解説

始点が頂点 $0$ であるような長さ $i$ のウォークであって，終点が頂点 $0, 1, 2, 3$ であるものの個数をそれぞれ $X_i, Y_i, Z_i, W_i$ とします．これらは $i\geq 1$ に対して漸化式

$$ \begin{aligned} X _ i &= Y _ {i-1} + Z _ {i-1}, \\\ Y _ i &= X _ {i-1} + Z _ {i-1}, \\\ Z _ i &= X _ {i-1} + Y _ {i-1} + W _ {i-1}, \\\ W _ i &= Z _ {i-1} \end{aligned} $$

を満たします．求めるものは $A_i = Y_0 + Y_1 + \cdots + Y_{i}$ ですが，これは $i\geq 1$ に対して漸化式

$$ A _ i = A _ {i-1} + Y _ i = A _ {i-1} + X _ {i-1} + Z _ {i-1} $$

を満たします．したがって列ベクトル $V_i$ および行列 $M$ を

$$ V_i= \begin{pmatrix} X_i \\\ Y_i \\\ Z_i \\\ W_i \\\ A_i \end{pmatrix}, $$

$$ M=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\\ 1 & 0 & 1 & 0 & 0 \\\ 1 & 1 & 0 & 1 & 0 \\\ 0 & 0 & 1 & 0 & 0 \\\ 1 & 0 & 1 & 0 & 1 \end{pmatrix} $$

により定めると，$V_i=MV_{i-1}$ $(i\geq 1)$ が成り立ちます．したがって

$$ V_i = M ^ i V_0 = M ^ i \begin{pmatrix} 1 \\\ 0 \\\ 0 \\\ 0 \\\0 \end{pmatrix} $$

と表せます．第 $4$ 成分を比べることで $A_i=(M^i)_{4,0}$ が得られます．

7. 線形漸化的数列の性質

7.1. 和と定数倍

線形漸化的数列は，和や定数倍に関して閉じています．

【定理 26】

$A=(A_0,A_1,A_2,\ldots)$ と $B=(B_0,B_1,B_2,\ldots)$ が線形漸化的数列であるとする．$p, q$ を定数とするとき，

$$ C_i = pA_i + qB_i $$

により定まる数列 $C=(C_0,C_1,C_2,\ldots)$ も線形漸化的数列である．

証明

$A$ と $B$ の母関数をそれぞれ $A(x),B(x)$ とすると，$C$ の母関数は $C(x)=pA(x)+qB(x)$ です．

仮定より $A(x), B(x)$ は有理式で表されるため，$C(x)$ も有理式で表されます．したがって $C$ は線形漸化的数列です．

□

7.2. 畳み込み

線形漸化的数列は，畳み込みに関して閉じています．

【定理 27】

$A=(A_0,A_1,A_2,\ldots)$ と $B=(B_0,B_1,B_2,\ldots)$ が線形漸化的数列であるとする．このとき

$$ C_i=\sum_{j=0}^i A_jB_{i-j} $$

により定まる数列 $C=(C_0,C_1,C_2,\ldots)$ も線形漸化的数列である．

証明

$A$ と $B$ の母関数をそれぞれ $A(x),B(x)$ とします．このとき，$C$ の母関数は $C(x)=A(x)B(x)$ です．

仮定より $A(x), B(x)$ は有理式で表されるため，$C(x)$ も有理式で表されます．したがって $C$ は線形漸化的数列です．

□

例えば $B_j = 1$ の場合を考えれば，線形漸化的数列の累積和が線形漸化的であることが分かります．このことは 【問題 5】 でも扱いました．

7.3. 項ごとの積

線形漸化的数列は，項ごとの積に関しても閉じています．

【定理 28】

$A=(A_0,A_1,A_2,\ldots)$ と $B=(B_0,B_1,B_2,\ldots)$ が線形漸化的数列であるとする．このとき

$$ C_i=A_iB_i $$

により定まる数列 $C=(C_0,C_1,C_2,\ldots)$ も線形漸化的数列である．

証明

$A$ が位数 $d$ の定数係数線形漸化式を満たし，$B$ が位数 $e$ の定数係数線形漸化式を満たすとします．このとき長さ $de$ の列ベクトル $V_i$ を，

$$ A _ {i+j}B _ {i+k} \quad (0\leq j < d, 0\leq k < e) $$

を適当な順に並べたものとして定めます．$V _ {i+1}$ の各成分は $A _ {i+j}B _ {i+k}$ ($1\leq j\leq d, 1\leq k\leq e$) の形をしています．ここで $A _ {i+d}$ や $B _ {i+e}$ が出てくる場合には，それぞれ $A$ や $B$ の漸化式を用いて

$$ A _ i, A _ {i+1}, \ldots, A _ {i+d-1},\quad B _ i, B _ {i+1}, \ldots, B _ {i+e-1} $$

を用いた式に直すことができます．このような式変形により，$V _ {i+1}$ の各成分は $V _ i$ の成分の線形結合で表されるため，ある $de\times de$ 行列 $M$ が存在して $V _ {i+1}=MV _ i$ が成り立ちます．詳細は次の 【問題 29】 の具体例を参考にしてください．

したがって，$A_iB_i$ は $M ^ i$ の成分の線形結合として表せるので，線形漸化的です．

□

【問題 29】

数列 $A=(A_0, A_1, A_2, \ldots)$ および $B=(B_0,B_1,B_2,\ldots)$ が漸化式

$$ A_i = 2A_{i-1}+3A_{i-2}\quad (i\geq 2), $$

$$ B_i = 4B_{i-1}+5B_{i-2}\quad (i\geq 2) $$

を満たすとき，$C_i = A_i B_i$ が線形漸化的であることを示してください．

解説

列ベクトル $V_i$ を

$$ V _ i = \begin{pmatrix}A _ iB _ i \\\ A _ {i}B _ {i+1} \\\ A _ {i+1}B _ i \\\ A _ {i+1}B _ {i+1}\end{pmatrix} $$

により定めます．非負整数 $i$ について

$$ \begin{aligned} A _ {i+1}B _ {i+2} &= A _ {i+1}(4B _ {i+1} + 5B _ i) = 4A _ {i+1}B _ {i+1} + 5A _ {i+1}B _ i, \\\ A _ {i+2}B _ {i+1} &= (2A _ {i+1} + 3A _ i)B _ {i+1} = 2A _ {i+1} B _ {i+1} + 3A _ {i}B _ {i+1}, \\\ A _ {i+2}B _ {i+2} &= (2A _ {i+1} + 3A _ i)(4B _ {i+1} + 5B _ i) \\\ &= 8A _ {i+1}B _ {i+1} + 10A _ {i+1}B _ i + 12A _ iB _ {i+1} + 15A _ iB _ i \end{aligned} $$

が成り立つので，行列 $M$ を

$$ M= \begin{pmatrix} 0 & 0 & 0 & 1 \\\ 0 & 0 & 5 & 4 \\\ 0 & 3 & 0 & 2 \\\ 15 & 12 & 10 & 8 \end{pmatrix} $$

により定めると $V_{i+1}=MV_i$ が成り立ちます．このことから $A_iB_i$ は $M^i$ の成分の線形結合であることが分かるので，$A_iB_i$ は線形漸化的数列です．

参考：Kronecker 積による方法

行列の Kronecker 積の知識がある場合は，次のように証明することもできます．

$X$ を $d\times d$ 行列，$Y$ を $e\times e$ 行列とし，$A_i$ が行列 $X^i$ の成分の線形結合，$B_i$ が行列 $Y^i$ の成分の線形結合であるとします．

$Z = X\otimes Y$ をこれらの Kronecker 積とします（$Z$ は $de\times de$ 行列です）． $Z ^ i = (X ^ i)\otimes (Y ^ i)$ なので，$X ^ i$ の成分と $Y ^ i$ の成分の積は $Z ^ i$ の成分です．

このことから，$A_i B_i$ は $Z ^ i$ の成分の線形結合であることが分かります．

8. 今後の講座で扱う内容

本講座では，どのような数列が線形漸化的であるかを調べました． また，そのような数列の母関数を有理式として表したり，行列累乗の成分の線形結合として表したりする方法についても，多くの例を扱いました．

さらに AtCoder Algorithm Lectures の後続講座では，線形漸化的数列に関する次のような重要な問題を扱います．

8.1. 線形漸化的数列の第 $K$ 項

【問題 30】

線形漸化的数列 $A=(A_0,A_1,A_2,\ldots)$ の初期値 $A_0, A_1, \ldots, A_{d-1}$ および，漸化式

$$ A_i=c_1A_{i-1}+c_2A_{i-2}+\cdots+c_dA_{i-d}\quad (i\geq d) $$

が与えられます．非負整数 $K$ に対して，第 $K$ 項 $A_K$ を求めてください．

この問題は単純に漸化式を順に用いると $\mathrm{O}(dK)$ 時間で解くことができます．また，このような数列はある行列累乗の成分の線形結合として表せるので，繰り返し二乗法などにより行列累乗を計算することで，$\mathrm{O}(d ^ 3 \log K)$ 時間で解くことができます．

以下の講座では，特に $d$ が大きい場合について，線形漸化的数列の第 $K$ 項をより高速に求める方法を扱います．

• 線形漸化的数列の第 K 項

なお，本講座の関連問題で紹介している問題では，行列累乗による解法が十分高速であるような問題を扱っています．

8.2. 定数係数線形漸化式の復元

【問題 31】

位数 $d$ 以下の定数係数線形漸化式を満たす線形漸化的数列 $A=(A_0,A_1,A_2,\ldots)$ があります．十分大きな $N$ について $A_0, A_1, \ldots, A_{N-1}$ が与えられるとき，$A$ が満たす位数 $d$ 以下の定数係数線形漸化式を見つけてください．

例えば，

$$ F=(0,1,1,2,3,5,8,13,21,\ldots) $$

という数列を入力として，

$$ F _ i = F _ {i-1} + F _ {i-2}\quad (i\geq 2) $$

という漸化式を出力するような問題です．

この問題では，「数列が線形漸化的であることは分かっているが，それが満たす定数係数線形漸化式は未知である」という状況を想定しています．例えば，線形漸化式で定まる乱数列の解析などで重要になります．一方で，一見すると競技プログラミングでの重要性は分かりにくいかもしれません．

しかし本講座で扱った問題についても，線形漸化的であることは証明したものの，具体的にどのような定数係数線形漸化式を満たすかまでは求めていない数列があります．特に 6 節で扱ったような行列累乗によって記述される線形漸化的数列や，7.3 節で扱ったような線形漸化的数列の項ごとの積などでは，そのような状況になりやすいです．

そのような数列でも，原理的には行列の特性多項式を計算することなどにより，定数係数線形漸化式を求められる場合があります．しかし，【問題 31】 を解くことで，より直接的かつ簡潔に漸化式を求めるという使い方をすることが競技プログラミングでは多いです．

この問題は，数列を観察して背後にある漸化式を発見する問題と見ることもできます．また，定数係数線形漸化式を復元できれば，8.1 節で述べた第 $K$ 項計算のアルゴリズムと組み合わせることで，数列の遠く離れた項を高速に求められるようになります．

以下の講座では，係数環 $R$ が体である場合や $\mathbb{Z}/m\mathbb{Z}$ である場合にこの問題を解く方法を扱います．

• 線形漸化式の復元
• 線形漸化式の復元（mod m）

8.3. P-recursive な数列

本講座で扱った線形漸化的数列は，定数係数線形漸化式を満たす数列でした．一方で，より広いクラスとして，係数が添字 $i$ の多項式であるような漸化式を満たす数列も重要です．特に多項式 $p_0, p_1, \ldots, p_d$ について

$$ p _ 0(i) A _ i + p _ 1 (i) A _ {i-1} + \cdots + p _ d (i)A _ {i-d}=0 $$

のような漸化式を満たす数列は，P-recursive であるといい，やはり多くの重要な例を含む数列のクラスです．P-recursive な数列についても，今後の講座で扱う予定です．

9. 関連問題

関連問題として取り上げる問題は，基本的に線形漸化的数列の第 $K$ 項を求めるというタイプの問題ばかりです．

yukicoder No.891 隣接3項間の漸化式 難易度目安：★

直接線形漸化式が与えられている，線形漸化的数列です．

yukicoder No.658 テトラナッチ数列 Hard 難易度目安：★

直接線形漸化式が与えられている，線形漸化的数列です．

yukicoder No.1105 Many Triplets 難易度目安：★

連立漸化式が与えられており，行列累乗による立式を確認できます．

AtCoder ABC360 E - Random Swaps of Balls 難易度目安：★★

漸化式の立式の練習問題です．

yukicoder No.1073 無限すごろく 難易度目安：★★

漸化式の立式の練習問題です．

AtCoder ABC204 F - Hanjo 2 難易度目安：★★

漸化式の立式の練習問題です．

yukicoder No.2883 K-powered Sum of Fibonacci 難易度目安：★★

線形漸化的数列の積が線形漸化的であるということに関する問題です．

yukicoder No.980 Fibonacci Convolution Hard 難易度目安：★★

形式的べき級数を考えることで漸化式を見つけやすくなります．

AtCoder エイシング プログラミング コンテスト 2020 F - Two Snuke 難易度目安：★★

形式的べき級数を考えることで漸化式を見つけやすくなります．

AtCoder AGC013 E - Placing Squares 難易度目安：★★★

AGC の問題ですが，形式的べき級数を考えたり，漸化式を作ることに慣れれば，比較的解きやすいと思います．

AtCoder ABC009 D - 漸化式 難易度目安：★★

少し珍しい単位的可換環 $R$ における線形漸化的数列の問題です．

AtCoder square869120Contest #3 G - フィボナッチ数の総和 難易度目安：★★★

有理式の部分分数分解について考えることで，（高度な多項式アルゴリズムを使わずとも）高速に解くことができる問題です．

10. まとめ

本講座では，どのような数列が線形漸化的であるかを調べました． また，そのような数列の母関数を有理式として表したり，行列累乗の成分の線形結合として表したりする方法についても多くの例を扱いました．

線形漸化的数列は，定義としては定数係数線形漸化式を満たす数列ですが，実際には様々な形で現れます．例えば，多項式で表される数列，等比数列との積，行列累乗の成分，動的計画法で現れる状態遷移などは，いずれも線形漸化的数列と深く関係しています．また，和，畳み込み，項ごとの積などの操作に関しても線形漸化的数列は閉じていることを見ました．

本講座では定理だけでなく，競技プログラミングの問題としても重要な例を多く扱いました．これらの例は，今後競技プログラミングで線形漸化的数列が現れる場面を見つけたり，そのような問題を形式的べき級数や行列と結びつけて扱ったりする際に役に立つはずです．

一方で，本講座では「線形漸化的であることを見抜く」「母関数や行列累乗として表す」という部分を主に扱い，線形漸化的数列を用いた高速なアルゴリズムについては詳しく扱いませんでした．

8 節で紹介したように，AtCoder Algorithm Lectures では今後，線形漸化的数列の第 $K$ 項を高速に求める方法や，数列の先頭項から定数係数線形漸化式を復元する方法を扱います．本講座で整理した母関数や行列との関係は，それらの講座を理解するための基礎になります．

11. 参考文献

1. maspy．[多項式・形式的べき級数]（3）線形漸化式と形式的べき級数．https://maspypy.com/[多項式・形式的べき級数]（3）線形漸化式と形式的べき級数．（閲覧日: 2026-05-21）．
2. Ryuhei Mori．線形漸化的数列のN項目の計算．Qiita．https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a．（閲覧日: 2026-05-21）．
3. demoralizer．[Tutorial] Solving Linear Recurrences with various methods, Including O(N logN logK) using FFT．Codeforces Blog．https://codeforces.com/blog/entry/97627．（閲覧日: 2026-05-21）．
4. Wikipedia．線型回帰数列．https://ja.wikipedia.org/wiki/線形回帰数列．（閲覧日: 2026-05-21）．
5. Wikipedia．Constant-recursive sequence．https://en.wikipedia.org/wiki/Constant-recursive_sequence．（閲覧日: 2026-05-21）．
6. SageMath．C-finite sequences．SageMath Reference Manual．https://doc.sagemath.org/html/en/reference/combinat/sage/rings/cfinite_sequence.html．（閲覧日: 2026-05-21）．

AtCoder Algorithm Lectures

トップページ Discord（質問・議論）