[多項式・形式的べき級数](3)線形漸化式と形式的べき級数

シリーズ一覧 →

関連解説:
[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$)の線形結合に等しい.

記号がごちゃごちゃしていますが、例えば $\frac{a+bx+cx^2}{(1-x)(1-2x)^2} = \frac{d}{1-x} + \frac{e}{1-2x} + \frac{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則から導かれる次も成り立ちます。

  • 商の微分:$\bigl(\frac{F}{G}\bigr)’ = \frac{F’G – FG’}{G^2}$.
  • $n$ 乗の微分:$(F^n)’ = nF^{n-1}F’ \quad (n\in \Z)$.

負の二項定理

【定理】$(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$ 等の母関数も表せるため、線形結合をとれば「多項式との各点積」が手に入ります。

累積和については、$\frac{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 = \frac{P}{Q}$ なので、次の対応があることが分かります。

【定理】数列 $\{a_n\}_{n\geq 0}$ について次は同値。
(1)線形漸化式を持つ。
(2)多項式 $P,Q (\deg P < \deg Q, Qの定数項は1)$ が存在して、$A = \frac{P}{Q}$ が成り立つ。
(3)$a_n$ は、$\binom{n+j-1}{j-1}r^n$ $(1\leqq j)$ の形の数列の線形結合である。
(4)$a_n$ は、$n^jr^n$ $(0\leqq j)$ の形の数列の線形結合である。

(1)$\implies$ (2)を上で説明しました。(2)$\implies$ (1)もほぼ同様です。また、線形漸化式の形と有理式の分母 $Q$ が対応していることも、よく確認しておきましょう。

(2)$\iff$(3)は、部分分数分解と負の二項定理から分かります。(3)$\iff$(4)を示すには、$\binom{x+j-1}{j-1}$ $(1\leqq j \leqq m)$ の線形結合全体が、$m$ 次未満の多項式全体と一致することを示せばよく、容易です。

(3)・(4)で 用いるべき $r,j$ が(2)の分母 $Q$ の因数分解と対応していることもよく確認しておくとよいでしょう。

線形漸化式の高速計算

数列 $\{a_n\}$ が満たす線形漸化式が分かっている場合、巨大な $N$ について $a_N$ を $\Theta(\log N)$ 時間で計算することができます。このことを確認しましょう。

線形漸化式を持つ数列 $\{a_n\}$ の母関数が $A = \frac{P_A}{Q}$ であるとします($P_A,Q$ は $\deg P_A < \deg Q$ であるような多項式)。

数列 $\{b_n\}$ を、$b_n = a_{N+n}$ により定めることにします。 $\{b_n\}$ は明らかに $\{a_n\}$ と同じ線形漸化式を持ちます。したがって、$B = \frac{P_B}{Q}$ と書けます。$A$ の $N$ 次未満の部分を $R = \sum_{0\leq i < N}a_ix^i$ とします。

このとき、$\frac{P_A}{Q} = R + x^N\frac{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)$ で計算できます。(後の記事で扱われる予定?)。

この周辺の処理は、競プロ界では行列累乗による解法が一般的ですが、行列の積は自然な方法で $\Theta(d^3)$ ですので、特に $d$ が巨大な場合、多項式の乗法・除法と比べて計算量が悪いですし、その差が問われる場面も存在するようです。

補足

第 $N$ 項を多項式のべき剰余と言い換える方法は探せばわりと色々あるので、気に入った説明を採用してください。

上では母関数の分母を $Q$ として、$a_N$ の計算を $x^{-N}\pmod{Q}$ の計算に帰着しました。実際には、$Q$ の係数を逆順にした多項式 $Q_{\mathrm{rev}} = x^dQ(1/x)$ に関するべき剰余 $x^N\pmod{Q_{\mathrm{rev}}}$ を用いた説明の方が一般的かと思います。実質的な計算に差異はありません。$Q_{\mathrm{rev}}$ は対応する線形漸化式の特性多項式と呼ばれています。

この記事の説明は他では見たことがありませんが、利点のひとつとしては、母関数の分母を逆順に並べなおす必要がないこと。もうひとつは、計算結果が $a_N$ だけでなく $b_n = a_{N+n}$ 全体の情報と自然に対応していることです(これに基づく問題解説記事 → )。

〇〇〇〇法

日本の競プロ界隈では、この手法についてはプレイヤ名を由来とする用語が広まっているようです。私としては、手法や概念にローカルな呼称をつけることは構わないと思っています(まぁ世界標準な呼称があるならなるべくそれに置き換えたいですが)。ただプレイヤ名を冠する手法については、初出から遠いことを認識した上で使いづつけるのは不誠実な姿勢のように感じます。

Fiduccia, C.M.: An Efficient Formula for Linear Recurrences.

学術的にはこれが初出であるように見えます。FFTと合わせて $\Theta(d\log d\log N)$ で計算できることが指摘されています。Fiduccia’s algorithmという呼称は学術論文でも存在する呼称のようですので、とりあえず妥当だと思います。ただ海外の競プロ界で普及している呼称というわけでもなさそう。それっぽい呼称があるのかは私は確認できていません。Fiduccia’s algorithmと呼ぶか、線形漸化式の高速計算くらいの呼び方をするかでも良いかと思いますが、いかがでしょうか。

いろいろな計算例

高校数学で学ぶ漸化式の解法も、その多くを形式的べき級数に置き換えることが可能です。特に、「なぜ特性方程式の解をとると上手くいくのか」が、高校数学の標準的な教育だとかなり隠されてしまっている印象があります。

$a_0=3, a_1=4, a_{n} = 5a_{n-1} – 6a_{n-2}$ の第 $n$ 項を求めよ。

$n$ の範囲はさぼっていきます。ある $1$ 次以下の多項式 $P$ が存在して、$A = \frac{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 つの方法が考えられます。

(1)上の計算を追って $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$ となります。

(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}$ の第 $n$ 項を求めよ。

1次以下の多項式 $P$ が存在して、母関数が $\frac{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 = \frac{ \alpha^n-\beta^n}{\alpha-\beta}$ となります。

(参考)通常 $\alpha = \frac{1+\sqrt{5}}{2}$, $\beta = \frac{1-\sqrt{5}}{2}$ としますが体は複素数体 $\C$ の部分体である必要はありません。例えば、$a_n\pmod{11}$ に興味がある場合には、物事を体 $\F_{11}$ で考えると、因数分解 $(1-x-x^2) = (1-4x)(1-8x)$ から $a_n = \frac{1}{4}(8^n-4^n)$ が分かります。これと Fermat の小定理より、$a_n\pmod{11}$ は10の約数の周期を持つことも分かります。体が $\F_5$ なら、因数分解は $(1-3x)^2$ で、$a_n=2n\cdot3^n$ になり、周期 $20$ があることも分かります。

$a_n = 2^n$ とするとき、$b_n = \sum_{i=0}^na_i$ を求めよ。

ただの等比数列の和ですが、形式的べき級数で計算しましょう。$a_n$ の母関数は $\frac{1}{1-2x}$ です。よって $b_n$ の母関数は $\frac{1}{(1-2x)(1-x)} = \frac{2}{1-2x} – \frac{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}$ の線形結合は、$\frac{1}{1-x-x^2}$ と $\frac{x}{1-x-x^2}$ の線形結合です。よってこの部分は $x^{-1}A$ と $A$ の線形結合なので、$b_n$ は $a_n, a_{n+1}, 1$ の線形結合であると分かります。ここから $b_n = a_n+a_{n+1}-1$ という形の関係式を発見することもできます。


さて、ここまで見てきたように、母関数の有理式表示から第 $n$ 項の表示を得る際に、「有理式の分母から、いくつかの数列の線形結合であることを示す」「$a_0,a_1,a_2$ 等の値から線形結合の係数を得る」という手順をとることができます。有理式の分母さえ得られれば、あとは同じ手順なわけですね。

また、 $a_n$ を $n$ の式で表すことに固執するのも常に最適な手法とは言えません。Fibonacci数列の例のように無理数を含む表示になることも多く、増大速度などを探るのには便利でも、厳密値あるいは厳密値 $\pmod{p}$ の計算目的ではありがたみが薄いです。そもそも第 $n$ 項は $a_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}$ を持ちます。展開して $d$ 乗和の公式を調べて…としなくても$b_0,\ldots,b_{17}$ を愚直計算してしまえば、巨大な $N$ に対する $b_N$ が計算できることが分かります。

$x^N\pmod{(1-x)^{18}}$ の計算は、変数変換 $y = (x-1)$ によれば $(y+1)^N\pmod{y^{18}}$ を計算すればよく、小さい $k\leqq 17$ に対する二項係数 $\binom{N}{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 = 多項式 + \frac{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://math.stackexchange.com/questions/1348838/sum-and-product-of-linear-recurrences

これは正しいのですが、仕組みの説明もちょっと大変ですし、計算量の意味での利点も少ないように思います。

もっとも、$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 = 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)$ などで計算できます。

タイトルとURLをコピーしました