シリーズ一覧 → ■
関連解説：
・[AtCoder] G – フィボナッチ数の総和（square869120Contest）
・[AtCoder] E – Placing Squares（AGC 013）
有理式の構造
本記事では、有理式で表される形式的べき級数を中心に調べていきます。まずは、そのような形式的べき級数がどのようなものか理解を深めましょう。
部分分数分解
【定理】$x$ の有理式 $\frac{P}{Q}$（$P,Q$ は多項式） において、$P$ の次数が $Q$ の次数よりも小さくて、$Q = \prod (1-r_i x)^{m_i}$ と因数分解されるとき、$\frac{P}{Q}$ は $(1-r_ix)^{-j}$ （$1\leqq j\leqq m_i$）の線形結合に等しい．
記号がごちゃごちゃしていますが、例えば $\dfrac{a+bx+cx^2}{(1-x)(1-2x)^2} = \dfrac{d}{1-x} + \dfrac{e}{1-2x} + \dfrac{f}{(1-2x)^2}$ といった要領です。
$\deg P < \deg Q$ という条件がありますが、これは大して本質的ではありません。一般の有理式は、上の形のものに多項式（$1,x,x^2,\ldots$の線形結合）を加えたものであり、形式的べき級数については有限個の係数の例外が生ずるだけです。
因数分解されるという仮定については、$Q$ の定数項が $1$ であれば、$P,Q$ の係数体の適当な拡大体においては成り立ちます。例えば $P,Q$ が $\C$ 係数なら、適当な $\C$ の元 $r_i$ が条件を満たします（代数学の基本定理）。
以上により、有理式で表せる形式的べき級数を理解するには、$(1-r_ix)^{-j}$ の形の形式的べき級数を理解すれば良さそうです。
微分
$(1-r_ix)^{-j}$ を調べるついでに、形式的べき級数の微分を導入しておきましょう。
形式的べき級数 $F = \sum_{n=0}^{\infty}f_nx^n$ に対して、その（形式）微分 $F’$ を、$F = \sum_{n=0}^{\infty}nf_nx^{n-1}$ により定義します（計算方法ではなく定義です）。
本記事の読者層の多くは、いわゆる「関数の微分」について見聞きしたことがあるかもしれませんが、そもそも $F$ は微分可能性どころか、数 $x$ の代入が定義できず関数の定義式にすらなっていない場合があります。しかしここでは、それを真似した純代数的な操作をやっているだけです。また同じ事情で、係数体が $\R$ や $\C$ に含まれない場合（有限体 $\F_q$ など）も全く同じように扱えます。
- Leibniz則（積の微分）：$(FG)’ = F’G + FG’$．
が成り立つことが証明できます（解析的な定義を採用していないので、関数の微分を知っている人も改めて証明しなおすべき命題ではあります）。Leibniz則から導かれる次も成り立ちます。
- 商の微分：$\biggl(\dfrac{F}{G}\biggr)’ = \dfrac{F’G – FG’}{G^2}$． （商 $\dfrac{F}{G}$ が定義される場合）
- $n$ 乗の微分：$(F^n)’ = nF^{n-1}F’ \quad (n\in \Z)$. （$n<0$ に対する主張は商 $\dfrac{1}{F}$ が定義される場合）
負の二項定理
【定理】$(1-rx)^{-d} = \sum_{n=0}^{\infty}\binom{n+d-1}{d-1}(rx)^n$ が成り立つ．
二項係数が登場するということで，何らかの数え上げと対応付けて証明することも可能ですが、ここでは微分を使ってみましょう。
$rx$ を $x$ に置き換えることで、$r=1$ の場合に示せばよいです。$d$ についての帰納法で示します。$d$ について示されたとして、$d+1$ について示しましょう。帰納法の仮定 $(1-x)^{-d} = \sum_{n=0}^{\infty}\binom{n+d-1}{d-1}x^n$ の両辺を微分すると、$-d(1-x)^{-d-1}\cdot(-1) = \sum_{n=0}^{\infty}\binom{n+d}{d-1} (n+1)x^n$ が分かるので、\[(1-x)^{-d-1} = \sum_{n=0}^{\infty}\frac{n+1}{d}\binom{n+d}{d-1}x^n=\sum_{n=0}^{\infty}\binom{n+d}{d}x^n\]となって示されました。
なお、二項係数 $\binom{n}{k}$ は $n$ の $\Q$ 係数多項式ですから、そのまま任意の $x\in\C$ に対する$\binom{x}{k}$ を定義することが可能です．上記の等式は、$d\geqq 0$ の場合に二項定理から分かる等式 $(1-x)^d = \sum_{n=0}^{\infty}\binom{d}{n}(-x)^n$ においてそのまま $d$ を負にしたものと完全に一致して、負の二項定理などとも呼ばれます。 なお、二項定理は適切に扱えば、$(x+y)^d (d\in\C)$ に一般化することもできます（■）。
数列の母関数
数列 $a_0,a_1,a_2,\ldots$ に対して、形式的べき級数 $A = \sum_{n=0}^{\infty} a_nx^n = a_0 + a_1x + a_2x^2 + \cdots$ を $\{a_n\}$ の母関数と言います。本記事では特に断りのない場合、「数列 $\{a_n\}$ の母関数 $A$ 」のように，数列と母関数の記号を小文字・大文字のアルファベットで対応させます。
数列に対するいくつかの操作は、母関数に対するとても簡単な操作として表すことができます。重要な例を見ておきましょう。
- シフト： 数列 $\{b_n\}_{n\geqq k}$ を $b_n = a_{n-k}$ により定めると、$B = x^{k}A$ が成り立つ（$k < 0$ の場合には $B$ は負べきの項を含みます）。
- 線形結合：数列 $\{c_n\}$ を $c_n = pa_n + qb_n$ （$p,q$ は定数）により定めると、$C = pA + qB$ が成り立つ。
- 等比数列との各点積：数列 $\{b_n\}$ を $b_n = a_nr^n$ により定めると、$B = A(rx)$ が成り立つ。
- 多項式との各点積：数列 $\{b_n\}$ を $b_n = na_n$ により定めると、$B = xA’$ が成り立つ。
- 累積和：数列 $\{b_n\}$ を $b_n = \sum_{i=0}^na_i = a_0+a_1+\cdots+a_n$ により定めると、$B = A\cdot \frac{1}{(1-x)}$ が成り立つ。
- 畳み込み：数列 $\{c_n\}$ を $c_n = \sum_{i+j=n}a_ib_j$ により定めると、$C = AB$ が成り立つ。
非自明なものはあまりないと思います。
$b_n = na_n$ については、微分の定義ほとんどそのままです。$na_n$ の母関数が表せたということは、繰り返せば $n^2a_n$, $n^3a_n$ 等の母関数も表せるため、線形結合をとれば「多項式との各点積」が手に入ります。
累積和については、$\dfrac{1}{1-x} = \sum_{n=0}^{\infty}x^n$ を思い出せばよいです。畳み込みは形式的べき級数の積の定義そのものです。
線形漸化式と形式的べき級数
定数 $c_1,c_2,c_3,\ldots,c_d$ に対して \[ n\geqq d\implies a_n = \sum_{i=1}^dc_ia_{n-i}\] と書ける漸化式を、定数係数斉次線形漸化式と言います。 $n$ の範囲は省略する場合もあります。修飾語が多いですが、本記事では単に線形漸化式と言えばこれを指すこととします。
このような漸化式を持つ数列 $\{a_n\}$ に対して、母関数 $A$ を考察します。右辺は $\{a_n\}$ のシフトの線形結合ですから、この等式は $A$ の言葉に書き直せるはずです。実際、$a_{n-i} = [x^{n-i}]A = [x^n]x^iA$ なので、 上記の漸化式は \[n\geqq d\implies [x^n] \Bigl(A – \sum_{i=1}^nc_ix^iA\Bigr)=0\] と表すことができます。そこで、$Q=1-c_1x-c_2x^2-\cdots-c_nx^n$ とおけば、$n\geqq d\implies [x^n]QA = 0$ であることが分かります。
「$n\geqq d\implies$」の部分に注意すると、ここから $P=QA$ は $d$ 次未満の多項式であることが分かります。$A=\dfrac{P}{Q}$ なので、次の対応があることが分かります。
【定理】数列 $\{a_n\}_{n\geq 0}$ について次は同値。
（１）線形漸化式を持つ。
（２）多項式 $P,Q$ （$\deg P < \deg Q$, $Q$ の定数項は $1$）が存在して、$A = \dfrac{P}{Q}$ が成り立つ。
（３）$a_n$ は、$\binom{n+j-1}{j-1}r^n$ $(1\leqq j)$ の形の数列の線形結合である。
（４）$a_n$ は、$n^jr^n$ $(0\leqq j)$ の形の数列の線形結合である。
（１）$\implies$ （２）を上で説明しました。（２）$\implies$ （１）もほぼ同様です。また、線形漸化式の形と有理式の分母 $Q$ が対応していることも、よく確認しておきましょう。
（２）$\iff$（３）は、部分分数分解と負の二項定理から分かります。（３）$\iff$（４）を示すには、$\binom{x+j-1}{j-1}$ $(1\leqq j \leqq m)$ の線形結合全体が、$m$ 次未満の多項式全体と一致することを示せばよく、容易です。
（３）・（４）で 用いるべき $r,j$ が（２）の分母 $Q$ の因数分解と対応していることもよく確認しておくとよいでしょう。
線形漸化式の第 $N$ 項の計算
数列 $\{a_n\}$ が満たす線形漸化式が分かっている場合、巨大な $N$ について $a_N$ を $\Theta(\log N)$ 時間で計算することができます。このことを確認しましょう。
行列累乗
$a_{n+d}$ を $a_n, \ldots, a_{n+d-1}$ の線形結合で表す線形漸化式が与えられていると、写像 $(a_n, \ldots, a_{n+d-1})\mapsto (a_{n+1},\ldots, a_{n+d})$ は線形写像です。この線形写像の $N$ 回合成を計算すればよく、「行列累乗」と呼ばれるテクニックにより $a_N$ を計算できます。例えば、フィボナッチ数列（$a_{n+2}=a_{n+1}+a_n$）であれば $$\pmat{a_{n+1}\\a_{n+2}}=\pmat{0&1\\1&1}\pmat{a_n\\a_{n+1}}$$ より、$A = \pmat{0&1\\1&1}$ として $\pmat{a_N\\a_{N+1}}=A^N\pmat{a_0\\a_1}$ と表すことができます。$A^N$ を繰り返し二乗法により計算すれば、$a_N$ を $O(\log N)$ 時間で計算することができます。
一般の $d$ 項間線形漸化式の場合、行列の積は最もシンプルな実装で $O(d^3)$ 時間であるため、$d, N$ について $O(d^3\log N)$ 時間ということになります。
参考：アリ本 3.4 節
Feduccia’s algorithm
多項式の乗算・除算を利用して効率よく $a_N$ を計算する方法は、Feduccia’s algorithm と呼ばれます。学術的には Fiduccia, C.M.: An Efficient Formula for Linear Recurrences. が最初であるように思われます。国内競プロ界隈のローカルネームとして、きたまさ法という呼ぶ人も居るようです。
線形漸化式を持つ数列 $\{a_n\}$ の母関数が $A = \dfrac{P_A}{Q}$ であるとします（$P_A,Q$ は $\deg P_A < \deg Q$ であるような多項式）。
数列 $\{b_n\}$ を、$b_n = a_{N+n}$ により定めることにします。 $\{b_n\}$ は明らかに $\{a_n\}$ と同じ線形漸化式を持ちます。したがって、$B=\dfrac{P_B}{Q}$ と書けます。$A$ の $N$ 次未満の部分を $R = \sum_{0\leq i < N}a_ix^i$ とします。
このとき、$\dfrac{P_A}{Q} = R + x^N\cdot\dfrac{P_B}{Q}$ が成り立ちます。分母を払うと、$P_A = RQ + x^NP_B$ です。$P_A, P_B$ は次数が $Q$ よりも小さい多項式です。また、$x$ は $\pmod{Q}$ で（あるいは環 $K[X] / (Q)$） で可逆です（例えば $Q = 1 + 2x + 3x^2$ ならば、$-(2 + 3x)$ が $\pmod{Q}$ での逆元を与えます）。
したがって、$P_B = x^{-N}P_A\pmod{Q}$ により多項式 $P_B$ を求めることができます。$N$ 乗の剰余なので、繰り返し二乗法により $\Theta(\log N)$ の回数の多項式の乗法・除法により $P_B$ を手に入れることができます。$P_B$ の定数項が $b_0 = a_N$ なので、これで $a_N$ が計算できました。
$Q$ が $d$ 次式である場合、多項式の乗法・除法は最も自然にやっても $\Theta(d^2)$ で計算できます。大きな $d$ に対しては、FFTを基礎とする方法で $\Theta(d\log d)$ で計算できます。上述の行列累乗よりも高速です。
Bostan–Mori algorithm
多項式除算を経由する必要がなく、実装が簡単で定数倍も軽い方法になります。私は上の記事を参考に実装しています。関連として
https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a
https://qiita.com/ryuhe1/items/c18ddbb834eed724a42b
も確認しておくと良いと思います。
競プロ文脈だと、$d$ が小さく FFT とナイーブな畳み込みの差が小さい場合も多いため、FFT を用意していない場合も、先にこちらを実用化することも可能です。
いろいろな計算例
高校数学で学ぶ漸化式の解法も、その多くを形式的べき級数に置き換えることが可能です。特に、「なぜ特性方程式の解をとると上手くいくのか」が、高校数学の標準的な教育だとかなり隠されてしまっている印象があります。
$a_0=3, a_1=4, a_{n}=5a_{n-1}-6a_{n-2}$ で定まる数列 $\{a_n\}$ の第 $n$ 項を求めよ。
$n$ の範囲はさぼっていきます。ある $1$ 次以下の多項式 $P$ が存在して、$A = \dfrac{P}{1-5x+6x^2}$ が成り立つことが分かります。$1-5x+6x^2=(1-2x)(1-3x)$ ですから、定数 $p,q$ が存在して、$A = p(1-2x)^{-1} + q(1-3x)^{-1}$ です（部分分数分解）。
$(1-rx)^{-d} = \sum_{n=0}^{\infty}\binom{n+d-1}{d-1}(rx)$ より特に $(1-rx)^{-1}\sum_{n=0}^{\infty}r^nx^n$ ですから、$a_n = p\cdot 2^n + q\cdot 3^n$ が成り立つことが分かります。
$p,q$ の求め方には主に 2 つの方法が考えられます。
（１）上の計算を追って $P, p,q$ をきちんと計算する。
$P = (1-5x+6x^2)A = (1-5x+6x^2)(3 + 4x + \cdots)$ です。さらに計算結果が$1$次以下の多項式になることは分かっているので、$(1-5x)(3+4x)$ の1次以下の部分だけ計算すればよいです。$P=3-11x$ と分かります。よって $3-11x=p(1-3x)+q(1-2x)$ ですから、$p=5,q=-2$ となります。
（２）$a_0,a_1$ に合うように $p,q$ を定める。
$a_0$ と $a_1$ の値および $a_n = p\cdot 2^n + q\cdot 3^n$ から、$3=p+q$ かつ $4=2p+3q$ が分かります。したがって $p=5, q=-2$ となります。
以上により、$a_n=5\cdot 2^n-2\cdot 3^n$ が証明されました。
$a_0=3, a_1=4, a_{n}=6a_{n-1}-9a_{n-2}$ で定まる数列 $\{a_n\}$ の第 $n$ 項を求めよ。
1次以下の多項式 $P$ が存在して、母関数が $\dfrac{P}{(1-3x)^2}$ と書けます。これは $(1-3x)^{-1}, (1-3x)^{-2}$ の線形結合です。$a_n$ は $3^n$ と $n3^n$ の線形結合です。あとは $a_0,a_1$ の値から $a_n = \bigl(3-\frac53n\bigr)\cdot 3^n$ となります。
$a_0=0, a_1=1, a_{n} = a_{n-1} + a_{n-2}$ の第 $n$ 項を求めよ。（Fibonacci数列）
$(1-x-x^2) = (1-\alpha x)(1-\beta x)$ と因数分解すると、やはり $a_n = p\alpha^n + q\beta^n$ と書けることが分かります。あとは $a_0$, $a_1$ の値からそれっぽく定めましょう。$a_0$ の値から $q=-p$ となって、$a_n = p(\alpha^n-\beta^n)$ となります。$a_1$ の値と合わせて $a_n = \dfrac{ \alpha^n-\beta^n}{\alpha-\beta}$ となります。
（参考）通常 $\alpha = \dfrac{1+\sqrt{5}}{2}$, $\beta = \dfrac{1-\sqrt{5}}{2}$ としますが体は複素数体 $\C$ の部分体である必要はありません。例えば、$a_n\pmod{11}$ に興味がある場合には、物事を体 $\F_{11}$ で考えると、因数分解 $(1-x-x^2) = (1-4x)(1-8x)$ から $a_n = \dfrac{1}{4}(8^n-4^n)$ が分かります。これと Fermat の小定理より、$a_n\pmod{11}$ は10の約数の周期を持つことも分かります。体が $\F_5$ なら、因数分解は $(1-3x)^2$ で、$a_n=2n\cdot3^n$ になり、周期 $20$ があることも分かります（このような方法で Fibonacci 数を $\mod p$ で見たときの周期を理解することが可能です）。
$a_n = 2^n$ とするとき、$b_n = \sum_{i=0}^na_i$ を求めよ。
ただの等比数列の和ですが、形式的べき級数で計算しましょう。$a_n$ の母関数は $\frac{1}{1-2x}$ です。よって $b_n$ の母関数は $\dfrac{1}{(1-2x)(1-x)} = \dfrac{2}{1-2x} – \dfrac{1}{1-x}$ なので、$b_n=2\cdot 2^n-1$ です。
明示公式の他に、 $b_n$ が線形漸化式 $b_n=3b_{n-1}-2b_{n-2}$ を満たすことが導かれていることも確認しておくと良いでしょう。
$a_0=0, a_1=1, a_n=a_{n-1}+a_{n-2}$ とするとき、$b_n = \sum_{i=0}^na_i$ を求めよ。
$A$ は分母 $(1-x-x^2)$ を持つ有理式なので、$B$ は分母 $(1-x-x^2)(1-x)$ を持つ有理式です。$(1-x-x^2)=(1-\alpha x)(1 -\beta x)(1-x)$ として、$B$ は $(1-x)^{-1}$, $(1-\alpha x)^{-1}$, $(1-\beta x)^{-1}$ の線形結合です。よって $b_n$ は $3$ つの等比数列 $1^n, \alpha^n, \beta^n$ の線形結合なので、いつものように計算できます。
それとは異なる道筋も示しましょう。$(1-\alpha x)^{-1}$, $(1-\beta x)^{-1}$ の線形結合は、$\dfrac{1}{1-x-x^2}$ と $\dfrac{x}{1-x-x^2}$ の線形結合です。よってこの部分は $x^{-1}A$ と $A$ の線形結合なので、$b_n$ は $a_n, a_{n+1}, 1$ の線形結合であると分かります。ここから $b_n=pa_n+qa_{n+1}+r$ の形の表示の存在が分かり、$b_n = a_n+a_{n+1}-1$ という形の関係式を発見することもできます。
さて、ここまで見てきたように、母関数の有理式表示から第 $n$ 項の表示を得る際に、「有理式の分母から、いくつかの数列の線形結合であることを示す」「$a_0,a_1,a_2$ 等の値から線形結合の係数を得る」という手順をとることができます。有理式の分母さえ得られれば、あとは同じ手順なわけですね。
また、$a_n$ を $n$ の式で表すことに興味がない場合も多いでしょう。そのような場合にも、結局小さい $n$ に対する $a_n$ と線形漸化式が分かれば第 $N$ 項を計算できます。
いずれにせよ重要なのは、数列がどのような線形漸化式（母関数の分母）を持つのかを知ることです。そのような方法を見ていきましょう。数列の初期値も省略していきます。
$a_n = a_{n-1} + a_{n-2}$, $b_n = \sum_{i+j=n}a_ia_j$ とするとき、$B$ の有理式表示の分母を求めよ。
$B = A^2$ です。$A$ は分母 $(1-x-x^2)$ を持つので、$B$ は分母 $(1-x-x^2)^2$ を持ちます。ここから $\{b_n\}$ の線形漸化式が得られるので、1件ずつ計算していくことも、巨大な $N$ に対する高速計算を行うことも可能です（問題例）。
$a_n=n^32^n$, $b_n=\sum_{i=0}^na_i$ とするとき、$A$, $B$ の有理式表示の分母を求めよ。
$A$ の分母は $(1-2x)^4$、$B$ の分母は $(1-2x)^4(1-x)$ です。
例えば $a_{n}=8a_{n-1}-24a_{n-2}+32a_{n-3}-16a_{n-4}$ を満たすことが分かります。$B$ についても、展開すれば $6$ 項間漸化式が得られます。ここから巨大な $N$ に対して $b_N$ を高速計算することも可能です。
$a_n = (5n^2+6n+7)^{8}$, $b_n=\sum_{i=0}^na_i$ とするとき、$A$, $B$ の有理式表示の分母を求めよ。
$a_n$ は $16$ 次多項式なので、$A$ は分母 $(1-x)^{17}$ を持ちます。$B$ は $A$ の累積和なので分母 $(1-x)^{18}$ を持ちます。よって $b_0,\ldots,b_{17}$ を愚直計算してしまえば、巨大な $N$ に対する $b_N$ が計算できることが分かります。
一般の線形漸化式に対する手法を使うと $b_N$ の計算には $\Theta(\log N)$ 時間がかかりそうですが，$\Theta(1)$ 時間でこれを求めることもできます。部分分数分解を考えると $B$ は $(1-x)^k$ （$1\leq k\leq 18$）の線形結合で書けるため、$b_N$ は $\binom{N+k-1}{k}$ の線形結合として計算できます。
$a_n=2a_{n-1}+3$ とするとき、$A$ の有理式表示の分母を求めよ。
高校数学典型です。これは定数係数非斉次線形漸化式というタイプになっていて、本記事でここまで扱った線形漸化式の範囲の外にありますが、問題ありません。
$a_n-2a_{n-1}=0$ という漸化式からは、$(1 – 2x)A = 多項式$ という性質が得られるのでした。今回は右辺に「3」が余分についていて、得られる式は \[ (1 – 2x)A = 多項式 + (3+3x+3x^2+3x^3+\cdots)\] と書き変わります。$(1-2x)A=多項式+\dfrac{3}{1-x}$ から、$A$ は 分母 $(1-x)(1-2x)$ を持ちます。
$a_n = a_{n-1} + a_{n-2}$, $b_n = 2b_{n-1} + a_n$ とするとき、$A$ の有理式表示の分母を求めよ。
同様に、$(1-2x)B = 多項式 + A$ が分かります。$A$ が分母 $(1-x-x^2)$ を持つので、$B$ は分母 $(1-2x)(1-x-x^2)$ を持ちます。
$a_n = 2a_{n-1} + 3a_{n-2} + 4^n + 5n^2+6n+7$ とするとき、$A$ の有理式表示の分母を求めよ。
$b_n = 4^n + 5n^2+6n+7$ とすると、$B$ が分母 $(1-4x)(1-x)^3$ を持つことと$(1-2x-3x^2)A = 多項式 + B$ から、$A$ は分母 $(1-4x)(1-x)^3(1-2x-3x^2)$ を持つことが分かります。
線形漸化式を持つことの確認
ものによっては、分母の因数分解や個別の係数を求めるところに手間があるものの、有理式である（線形漸化式を持つ）こと自体は容易に分かる場合があります。実は、「線形漸化式を持つという事実」だけでも価値があります。数列のはじめの方から漸化式を復元することは、愚直な連立$1$次方程式解法で $\Theta(d^3)$ で出来ますし、さらに上手にやることで $\Theta(d^2)$ になります（BM法：Berlekamp–Massey algorithm）。よって、どのような数列がどのような項数の線形漸化式を持つかがすぐに判断できるようになれば、それだけでも問題解決に利用することが可能です。
$a_n, b_n$ が線形漸化式を持つとき、その線形結合も線形漸化式を持つ。
有理式の線形結合は有理式なので。
$a_n, b_n$ が線形漸化式を持つとき、$c_n = a_nb_n$ も線形漸化式を持つ。
線形漸化式を持つことと、$n^kr^n$ の形の数列の線形結合で書けることの同値性から分かります。
$A$ の分母を $\prod_{i}(1-\alpha_i x)$ 、$B$ の分母を $\prod_{j}(1-\beta_j x)$ とするとき、$C$ の分母を $\prod (1-\alpha_i\beta_j x)$ にとれることも分かります。 また、各々の分母の次数が $d_A, d_B$ ならば、$C$ の分母を $d_Ad_B$ 次式にとれることも分かります。
（注：重解を持つ場合も含めて正しい）
$A,B$ の係数をもとに $C$ の係数を求める方法もありますが、ここでは省略します（参考：https://codeforces.com/blog/entry/103136）
もっとも、$d_A, d_B$ が十分低次ならば手計算でも簡単です。例えば $a_n$ を Fibonacci数列として、$b_n = a_n^2$ とすると、$B$ の分母として $(1-\alpha^2 x)(1-\alpha\beta x)(1-\beta^2 x) = (1+x)(1-3x+x^2)$ をとることができます。$c_n = \sum_{i=0}^nb_n$ は分母$(1-x)(1+x)(1-3x+x^2)$ を持ちますね（問題例)。
$a_n$ を線形漸化式を持つ数列として、$b_n = a_{3n}$ とするとき、$b_n$ は線形漸化式を持つ。
$a_n$ は $n^kr^n$ の形の数列の線形結合です。よって $b_n$ は $(3n)^kr^{3n}$ の形の数列の線形結合です。これは $n^k(r^{3})^n$ の形の数列の線形結合なので、線形漸化式を持ちます。$\{a_n\}$ の線形漸化式と同じ項数の線形漸化式を持つことも確認できます。
これも実際に漸化式を得るのは少し手間です。$A$ の分母が $\prod_i(1-\alpha_i x)$ である場合、$B$ の分母は$\prod_i(1-\alpha_i^3 x)$ ととれます。例えば $\{a_n\}$ がFibonacci数列なら、$\{b_n\}$ は漸化式 $b_n = 4b_{n-1} + b_{n-2}$ を持つことなどが確かめられます。
あるいは、$\zeta$ を $1$ の原始 $3$ 乗根として、$B(x^3) = \frac13\bigl(A(x) + A(\zeta x) + A(\zeta^2 x)\bigr)$ なんていう表示も可能です。ここからも $B$ が有理式であることが確認できます。
$a_n,b_n,c_n$ を線形漸化式を持つ数列として、$d_n$ を「$a_0,b_0,c_0,a_1,b_1,c_1,a_2,\ldots$」と並べた数列とするとき、$\{d_n\}$ は線形漸化式を持つ。
$D(x) = A(x^3) + xB(x^3) + x^2C(x^3)$ ですから、有理式です。
剰余ごとの考察で線形漸化式を持ちそうなら、全体で見ても線形漸化式を持つので、例えばこういう数え上げも線形漸化式を持ちます。
$a_{n+1} = 2a_n + 3b_n + 4$, $b_{n+1} = 5a_n + 6b_n + 7^n$ のとき、$\{a_n\}$, $\{b_n\}$ は線形漸化式を持つ。
連立漸化式ですが、形式的べき級数考察をすると、\[A-2xA-3xB=\frac{4}{1-x}+多項式,\qquad B-5xA-6xB=\frac{1}{1-7x}+多項式\] となります。$(1-2x)A – (3x)B$ のように理解してあげると$A, B$ の連立 $1$ 次方程式の格好で、方程式の係数がすべて有理式という状況です。問題設定より方程式が一意に解けるので、 $A$ は有理式です。
なお、分母を具体的に書くのも難しくはなくて、$(1-x), (1-7x)$ に加えて行列式 $(1-2x)(1-6x)-(-3x)(-5x)$ をかけてあげればよいです。
$M$ を $d\times d$ 行列とし、$M^n$ の各成分や、成分の線形結合は線形漸化式を持つ。
ケーリー・ハミルトンの定理より、$M$ 自体が線形漸化式を持ちますので明らかです。
例えば疎行列 $M$・列ベクトル $v,w$・大きな $N$ に対して ${}^tvM^Nw$ を計算したいとします（複雑な式っぽいですが、$M^Nw$ の成分の線形結合です、いわゆる「行列累乗」を想定解とする問題のほぼすべてに当てはまると思います）。仮に $M$ を $d\times d$ 行列、$C$ を正定数として、 $0$ でない成分が $O(Cd)$ 個であるとしましょう。繰り返し二乗法で $M^N$ を計算すると、初手以外は密行列になりえて、$O(d^3\log N)$ しか保証できません。$M$ と列ベクトルの積が $O(Cd)$ で計算できることを踏まえると、$O(d)$ 個の項が $O(Cd^2)$ の計算量で手に入るので、BM 法と合わせて ${}^tvM^Nw$ が $O((C+1)d^2 + d\log d\log N)$ などで計算できます。
