Find Linear Recurrence with Polynomial Coefficients

ある数列 $(a_0, a_1, a_2, \dots)$ が P-recursive (holonomic) であった場合に、$\sum_{i=0}^{k} f_{i}(n) \cdot a_{n-i} = 0$ ($n \ge k$) を満たすような($d$ 次以下の)多項式係数 $f_0, \cdots, f_k$ を見つける方法です。

求め方

多項式係数 $f_0, f_1, \dots, f_k$ の最大の次数が $d$ 以下となるような order $k$ の漸化式を検出したいとします。

このとき、$$\sum_{i=0}^k f_i(n) \cdot a_{n-i} = 0$$ が成り立ちます。ここで、定数 $c_{i,j}$ ($j = 0, \dots, d$) を用いて $f_i(n) = \sum_{j=0}^d c_{i,j} (n-i)^j$ と書き直すことができるので、$$\sum_{i=0}^k \sum_{j=0}^d c_{i,j} \cdot (n-i)^ja_{n-i} = 0$$ を満たす $c_{i,j}$ を求める問題となります。

これは、$(M_{i,(d+1) j + l}):= (i+j)^l a_{i+j}$ ($0 \le i \le m -1$, $0 \le j \le k$, $0 \le l \le d$) とする $(m-1) \times m$ 行列 $M$ から線形従属な列の組を発見する問題と見なせるので、(漸化式が存在するならば)ガウスの消去法で(多くの場合)解けます。ここで、$m := (k + 1) \cdot (d + 1)$ です。

最大の添え字は $(k + 1)(d + 2)-3$ となるため、少なくとも連続する $(k + 1)(d + 2) - 2$ 項を入力として与える必要があります。

実装的な補足

  • 入力として $n$ 項与えられた際に、$k := \left\lfloor\frac{n+2}{d+2}\right\rfloor - 1$ とすると、計算の手間が省けます。

ソースコード

説明した方法を実装したコードです。いくつかの数列について、例を載せています。


不明点 & 解けない場合

  • 数列 $(a_0, \dots, a_n)$ に対して order $k$ の(多項式係数の次数が $d$ 以下の)漸化式が存在する(検出できる)ことが保証されている場合でも、先に order $k'$ ($k' < k$) の不正な漸化式を発見してしまって(Error 落ちして)order $k$ の漸化式が発見できない、という例が存在するかもしれないです。
    • 多項式係数の次数を $0$ にした(linear-recursive な)場合は、おそらく、この問題は発生しないと思います。
  • 素数 $p$ が小さい場合、order $0$ の漸化式 (?) を発見し、解けない場合があります。例えば、$(0, 1, 0, 1, 0, 1, \dots)$ のような数列に対して、$(n + 1) \cdot a_n \equiv 0 \pmod{2}$ を検出しますが、この漸化式では $a_n$ は必ずしも一意に定まりません。

例題

これ以外の問題でも、数列が P-recursive となっている場合があるかもしれません。

その他

  • 数列 $(f_n), (g_n)$ が P-recursive であるとき、数列 $(\alpha f_n + \beta g_n)$, $(f_n g_n)$ も P-recursive となります。
  • Richard P Stanley さんの著書 Enumerative Combinatorics: Volume 2 に、この辺りの内容が詳しく書かれています。