4
現代数学解説
文献あり

超幾何数列の基礎3:漸化式の解き方

192
0
$$\newcommand{a}[0]{\alpha} \newcommand{Aut}[0]{\operatorname{Aut}} \newcommand{b}[0]{\beta} \newcommand{C}[0]{\mathbb{C}} \newcommand{c}[0]{\cdot} \newcommand{d}[0]{\delta} \newcommand{D}[0]{\Delta} \newcommand{dis}[0]{\displaystyle} \newcommand{e}[0]{\varepsilon} \newcommand{F}[4]{{}_2F_1\left(\begin{matrix}#1,#2\\#3\end{matrix};#4\right)} \newcommand{farc}[2]{\frac{#1}{#2}} \newcommand{FF}[6]{{}_3F_2\left(\begin{matrix}#1,#2,#3\\#4,#5\end{matrix};#6\right)} \newcommand{G}[0]{\Gamma} \newcommand{g}[0]{\gamma} \newcommand{Gal}[0]{\operatorname{Gal}} \newcommand{H}[0]{\mathbb{H}} \newcommand{id}[0]{\operatorname{id}} \newcommand{Im}[0]{\operatorname{Im}} \newcommand{Ker}[0]{\operatorname{Ker}} \newcommand{l}[0]{\left} \newcommand{L}[0]{\Lambda} \newcommand{la}[0]{\lambda} \newcommand{La}[0]{\Lambda} \newcommand{Li}[0]{\operatorname{Li}} \newcommand{li}[0]{\operatorname{li}} \newcommand{M}[4]{\begin{pmatrix}#1& #2\\#3& #4\end{pmatrix}} \newcommand{N}[0]{\mathbb{N}} \newcommand{o}[0]{\omega} \newcommand{O}[0]{\Omega} \newcommand{ol}[1]{\overline{#1}} \newcommand{ord}[0]{\operatorname{ord}} \newcommand{P}[0]{\mathfrak{P}} \newcommand{p}[0]{\mathfrak{p}} \newcommand{q}[0]{\mathfrak{q}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{r}[0]{\right} \newcommand{R}[0]{\mathbb{R}} \newcommand{Re}[0]{\operatorname{Re}} \newcommand{s}[0]{\sigma} \newcommand{t}[0]{\theta} \newcommand{ul}[1]{\underline{#1}} \newcommand{vp}[0]{\varphi} \newcommand{vt}[0]{\vartheta} \newcommand{Z}[0]{\mathbb{Z}} \newcommand{z}[0]{\zeta} \newcommand{ZZ}[1]{\mathbb{Z}/#1\mathbb{Z}} \newcommand{ZZt}[1]{(\mathbb{Z}/#1\mathbb{Z})^\times} $$

はじめに

 この記事では 前回の記事 に引き続き超幾何数列の基本事項についてまとめていきます。
 前回の記事では
$$S(n)=\sum^n_{k=0}A(k)$$
という数列の閉形式の求め方、特に
$$T(n+1)-T(n)=A(n)$$
という漸化式を満たす超幾何数列の求め方について解説しましたが、今回の記事ではより一般に多項式係数の線形漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=0$$
を満たす超幾何数列の求め方について解説していきます。
 以下$p_0(n),\ldots,p_I(n)$は多項式であって、$p_0(n),p_I(n)$は(多項式として)$0$ではないものとします。

多項式による解

 まず非同次な漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
の多項式による解の求め方について考えていきましょう。$f(n)$が多項式であればこの左辺も多項式となるので、以下この右辺$g(n)$は多項式であるものとします。
 やることとしては適当に$d$を取り
$$f(n)=\sum^d_{k=0}c_kn^k$$
と展開することによって$d+1$個の未知数$c_0,\ldots,c_d$についての線型方程式に帰着させるだけなので、あとは$d$の上界を求めておけば機械的に処理することができます。

漸化式から差分方程式へ

 いま簡単のため$N$を前進作用素、つまり数列$a_n$に対して
$$Na_n=a_{n+1}$$
と定めると件の方程式は
$$L=\sum^I_{i=0}p_i(n)N^i$$
なる作用素を用いて
$$Lf(n)=g(n)$$
と表せます。
 また$\D$を差分作用素、つまり数列$a_n$に対して
$$\D a_n=a_{n+1}-a_n$$
と定めると$\D=N-1$より$L$$\D$を用いて
\begin{align} L &=\sum^I_{i=0}p_i(n)(\D+1)^i\\ &=\sum^I_{i=0}p_i(n)\sum^i_{j=0}\binom ij\D^j\\ &=\sum^I_{j=0}\l(\sum^I_{i=j}\binom ijp_i(n)\r)\D^j \end{align}
と表せます。
 したがって件の方程式は
$$q_j(n)=\sum^I_{k=i}\binom ijp_i(n)$$
なる多項式を係数に持つ差分方程式
$$\sum^I_{j=0}q_j(n)(\D^jf)(n)=g(n)$$
に変形できます。

次数の推定

 いま$f(n)$の次数を$d$とおき
$$f(n)=cn^d+\cdots$$
と展開すると、繰り返しこの差分を取ることで
$$(\D^jf(n))=cd^{\ul j}n^{d-j}+\cdots$$
が成り立ちます。ただし$x^{\ul j}$は下降階乗
$$x^{\ul j}=x(x-1)(x-2)\cdots(x-j+1)$$
としました。
 したがって
$$q_j(n)=\la_jn^{d_j}+\cdots\qquad(d_j=\deg q_j)$$
および
$$b=\max_{0\leq j\leq I}(\deg q_j-j)$$
とおくと
$$Lf(n)=\sum^I_{j=0}q_j(n)(\D^jf)(n)$$
の次数は高々$b+d$であり、また$n^{b+d}$の係数は
$$c\sum_{\deg q_j-j=b}\la_jd^{\ul j}$$
と表せます。
 これによって$d$は次のいずれかの条件を満たすことがわかります。

  • $b+d<0$のとき、$d\leq-b-1$
  • $\deg(Lf(n))=b+d$のとき、$d=\deg g-b$
  • $\deg(Lf(n))< b+d$のとき、多項式
    $$r(x)=\sum_{\deg q_j-j=b}\la_jx^{\ul j}$$
    に対し$r(d)=0$

まとめ

 以上より漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
の多項式解は次のようなアルゴリズムによって網羅的に求めることができます。

  1. $j=0,1,\ldots,I$に対し
    $$q_j(n)=\sum^I_{i=j}\binom ijp_i(n)$$
    によって定まる多項式$q_j(n)$について、その次数$\deg q_j$と最高次数の係数$\la_j$を求める。
  2. 整数$b$と多項式$q_j(n),r(x)$
    \begin{align} b&=\max_{1\leq j\leq I}(\deg q_j-j)\\ r(x)&=\sum_{\deg q_j-j=b}\la_jx(x-1)\cdots(x-j+1) \end{align}
    によって定め
    $$d=\max(\{\deg g-b,-b-1\}\cup\{d'\in\Z_{\geq0}\mid r(d')=0\})$$
    とおく。
  3. $d<0$であれば多項式解は存在せず、$d\geq0$であれば
    $$f(n)=\sum^d_{k=0}c_kx^k$$
    とおき
    $$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
    の両辺を係数比較することによって得られる$c_0,\ldots,c_d$についての線形方程式を解く。
    この方程式が解を持たない場合も多項式解は存在しない。

 ちなみに 前回の記事 Gosper's algorithmのステップ2として
$$a(n)x(n+1)-b(n-1)x(n)=c(n)$$
という漸化式の多項式解$x(n)$の求め方を紹介しましたが、それはこのアルゴリズムの特殊な例($I=1$)となっています。

超幾何数列による解

 次に上の結果を用いて同次漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=0$$
の超幾何数列による解の求め方について考えていきましょう。
 いま超幾何数列$f(n)$に対し
$$r(n)=\frac{f(n+1)}{f(n)}$$
とおくと$f(n)$
$$f(n)=f(0)\prod^{n-1}_{k=0}r(n)$$
のように表せるので、件の方程式は有理関数$r(n)$についての方程式
\begin{align} &\sum^I_{i=0}p_i(n)\frac{f(n+i)}{f(n)}\\ ={}&\sum^I_{i=0}p_i(n)\prod^{i-1}_{j=0}r(n+j)=0 \end{align}
に帰着できます。

$r(n)$の因数

 ここで 前回の記事 の定理5から
$$r(n)=\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}z$$
なるモニック多項式$a(n),b(n),c(n)$と定数$z$であって

  1. 任意の非負整数$h$に対し$a(n)$$b(n+h)$は互いに素である。
  2. $a(n)$$c(n)$は互いに素である。
  3. $b(n)$$c(n+1)$は互いに素である。

を満たすようなものを取ると
$$\prod^{i-1}_{j=0}r(n+j)=\l(\prod^{i-1}_{j=0}\frac{a(n+j)}{b(n+j)}\r)\frac{c(n+i)}{c(n)}z^i$$
が成り立つので件の方程式はさらに多項式の恒等式
$$\sum^I_{i=0}p_i(n)\l(\prod^{i-1}_{j=0}a(n+j)\prod^{I-1}_{j=i}b(n+i)\r)c(n+i)z^i=0$$
に帰着されます。
 いまこの左辺の第$i=0,I$項に注目すると
\begin{align} a(n)&\mid p_0(n)\l(\prod^{I-1}_{j=0}b(n+i)\r)c(n)z^i\\ b(n+I-1)&\mid p_I(n)\l(\prod^{I-1}_{j=0}a(n+I)\r)c(n+I)z^I \end{align}
が成り立つことがわかり、特に$a(n),b(n),c(n)$の取り方から
$$a(n)\mid p_0(n),\quad b(n)\mid p_I(n-I+1)$$
となることがわかります。これにより$a(n),b(n)$の候補は$p_0(n),p_i(n-I+1)$の因数という高々有限個に絞ることができます。

多項式解への帰着

 そこで$p_0(n),p_i(n-I+1)$のモニックな因数を任意に取って$a(n),b(n)$とおき、件の方程式
$$\sum^I_{i=0}p_i(n)\l(\prod^{i-1}_{j=0}a(n+j)\prod^{I-1}_{j=i}b(n+i)\r)c(n+i)z^i=0$$
$c(n),z$についての方程式として解いてみましょう。
 このときこの最高次の係数に注目することで$z$についての代数方程式(明示形については後述)
$$\sum^I_{i=0}\a_iz^i=0$$
が得られるので、この代数方程式の解$z_0$を任意に取り$z=z_0$とすることで残すは線形漸化式の多項式解$c(n)$を求めるだけとなります。そしてそれは前節で紹介したアルゴリズムによって解決することができます。

Petkivšek's Algorithm

 以上より漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=g(n)$$
の超幾何数列による解は次のようなアルゴリズムによって網羅的に求めることができます。

  1. $p_0(n),p_I(n-I+1)$のモニックな因数を任意に取りそれぞれ$a(n),b(n)$とおく。
  2. このとき
    \begin{align} P_i(n)&=p_i(n)\prod^{i-1}_{j=0}a(n+j)\prod^{I-1}_{j=i}b(n+i)\\ m&=\max_{0\leq i\leq I}\deg P_i \end{align}
    とおき、$P_i(n)$における$n^m$の係数を$\a_i$とする。
  3. 代数方程式
    $$\sum^I_{i=0}\a_iz^i=0$$
    の各解$z$に対して、漸化式
    $$\sum^I_{i=0}z^iP_i(z)c(n+i)=0$$
    の多項式解$c(n)$を求める。
  4. もし多項式$c(n)$が求まれば
    $$\frac{f(n+1)}{f(n)}=\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}z$$
    によって定まる数列$f(n)$が求める超幾何数列となる。
  5. ステップ1において$p_0(n),p_I(n-I+1)$の因数の取り方を変えて同じ操作を繰り返す。

 見ての通りこのアルゴリズムは計算量が半端ではありません。実際"A=B"によると最悪の場合この計算量は$p_0(n),p_I(n)$の次数に関して指数的なオーダーとなるらしいです。そのため少しでも計算量を減らす工夫として以下のテクニックを覚えておくといいでしょう。

テクニック

  1. $c(n)$についての漸化式の係数はそれぞれ$a(n)b(n+I)$で割り切れるので、これにより係数となる多項式の次数を減らすことができる。
  2. ステップ2において定めた多項式$P_i(n)$の次数は$d(a,b)=\deg b-\deg a$を用いて
    $$\deg P_i=\deg p_i+I\deg b-id(a,b)$$
    と求まる。特に
    $$m'=\max_{0\leq i\leq I}(\deg p_i-id(a,b))$$
    および$p_i$の最高次数の係数を$\a_i$とおくと、$z$についての代数方程式は
    $$\sum_{\deg p_i-id(a,b)=m'}\a_iz^i=0$$
    と表せる。ここでこの方程式は$d(a,b)$の値のみによって定まるので各$-\deg p_0\leq d(a,b)\leq\deg p_I$に対しこの方程式およびその解を求めることで、事前に$z$として取り得る値を列挙しておくことができる。
  3. また$z$の取り方から$z\neq0$であることに注意すると上の方程式が$\a_{i_0}z^{i_0}=0$という形になる場合、つまり$\deg p_i-id(a,b)$がただ一つの$i$において最大値を取るような場合は無視することができる。
  4. 例えば$\deg p_I=\deg p_0\geq\deg p_i$が成り立つ場合、$d(a,b)\neq0$であれば$\deg p_i-id(a,b)$$i=0$$i=I$でのみ最大値を取るので不適であり、したがって$\deg a=\deg b$でなければならないことがわかる(このとき$z$についての方程式はただ一つに求まることにも注意したい)。
  5. $a(n),b(n)$は条件「(i) 任意の非負整数$h$に対し$a(n)$$b(n+h)$は互いに素である」を満たすように取れたので、これを満たさないような場合は無視することができる。

計算例

 百聞は一見に如かず、ということで今回も"A=B"に掲載されているいくつかの計算例を見ていくこととしましょう。

 三項間漸化式
$$3f(n+2)-nf(n+1)+(n-1)f(n)=0$$
の多項式解を全て求めよ。

解説

$$p_2(n)=3,\quad p_1(n)=-n,\quad p_0(n)=n-1$$
より
\begin{alignat}{3} q_2(n)&=p_2(n)&&=3\\ q_1(n)&=2p_2(n)+p_1(n)&&=6-n\\ q_0(n)&=p_2(n)+p_1(n)+p_0(n)&&=2 \end{alignat}
と求まる。
 したがって
$$\deg q_j-j=-2,0,0\qquad(j=2,1,0)$$
つまり$b=0$および
$$r(x)=-x+2$$
と求まり、$\deg g=-\infty$に注意すると$d=2$を得る。
 いま
$$f(n)=An^2+Bn+C$$
とおくと
\begin{align} 3f(n+2)&=3(An^2+(4A+B)n+(4A+2B+C))\\ -nf(n+1)&=-(An^3+(2A+B)n^2+(A+B+C)n)\\ (n-1)f(n)&=An^3-(A-B)n^2-(B-C)n-C \end{align}
より
$$\begin{pmatrix} 3A-(2A+B)-(A-B)\\ 3(4A+B)-(A+B+C)-(B-C)\\ 3(4A+2B+C)-0-C \end{pmatrix} =\begin{pmatrix} 0&0&0\\ 11&1&0\\ 12&6&2 \end{pmatrix}\begin{pmatrix} A\\B\\C \end{pmatrix}=\begin{pmatrix} 0\\0\\0 \end{pmatrix}$$
という方程式に帰着する。これを解くことで
$$f(n)=A(n^2-11n+27)\qquad(A\mbox{は任意})$$
を得る。

 三項間漸化式
$$(n-1)f(n+2)-(n^2+3n-2)f(n+1)+2n(n+1)f(n)=0$$
の超幾何数列による解を全て求めよ。

解説

$$p_2(n)=n-1,\quad p_1(n)=-(n^2+3n-2),\quad p_0(n)=2n(n+1)$$
なのでテクニック(5)に注意すると$a(n),b(n)$の候補は
$$(a(n),b(n))=(1,1),(n,1),(n+1,1),(n(n+1),1)$$
の四通りに絞られる。

$(a(n),b(n))=(1,1)$のとき

 このとき$z$の満たす方程式は
$$-z+2=0$$
つまりその解は$z=2$と求まり、$c(n)$の満たす漸化式は
\begin{align} &z^2\frac{p_2(n)}{b(n+1)}a(n+1)c(n+2)+zp_1(n)c(n+1)+\frac{p_0(n)}{a(n)}b(n)c(n)\\ ={}&4(n-1)c(n)-2(n^2+3n-2)c(n)+2n(n+1)c(n)\\ ={}&0 \end{align}
となる。これを解くと$c(n)=A$つまり$f(n)=A2^n$が得られる($A$は任意)。

$(a(n),b(n))=(n+1,1)$のとき

 このとき$z$の満たす方程式は
$$z^2-z=0$$
つまりその解は$z=1$と求まり、$c(n)$の満たす漸化式は
$$(n-1)(n+2)c(n+2)-(n^2+3n-2)c(n+1)+2nc(n)=0$$
となる。これを解くと$c(n)=B$つまり$f(n)=Bn!$が得られる($B$は任意)。

結論

 これにて二つの線形独立な解が得られたので、残る$(a(n),b(n))$の候補を確かめずとも
$$(n-1)f(n+2)-(n^2+3n-2)f(n+1)+2n(n+1)f(n)=0$$
の解は
$$f(n)=A2^n+Bn!\qquad(A,B\mbox{は任意})$$
で尽くされることがわかる。

 アペリー数
$$f(n)=\sum^n_{k=0}\binom nk^2\binom{n+k}k^2$$
は三項間漸化式
$$(n+2)^3f(n+2)-(2n+3)(17n^2+51n+39)f(n+1)+(n+1)^3f(n)=0$$
を満たすことが知られている。このことから$f(n)$は閉形式に表せないことを示せ。

解説

 テクニック(4),(5)に注意すると$a(n),b(n)$の候補は
$$(a(n),b(n))=(1,1)$$
の一通りに絞られる。このとき$z$の満たす方程式は
$$z^2-34z+1=0$$
つまりその解は$z=17\pm12\sqrt2$と求まり、$c(n)$の満たす漸化式は
$$z^2(n+2)^3c(n+2)-z(2n+3)(17n^2+51n+39)c(n+1)+(n+1)^3c(n)=0$$
となる。しかしこれを解くとこのような多項式は存在しないことがわかる。
 したがって$f(n)$が満たす漸化式は超幾何数列による解を持たず、$f(n)$は閉形式に表せないことが示された(cf. 前々回の記事 の定理6)。

 やはり計算量が大変なことになってしまうので、やむを得ず多項式解を計算する過程は省略しました。

追記:d'Alembertian数列による解

 上では漸化式の超幾何数列による解の求め方について解説してきましたが、"閉じた形(closed form)"の解釈をもう少し広げ
$$f(n) =A_0(n)\sum^{n-1}_{n_1=0}A_1(n_1)\sum^{n_1-1}_{n_n=0}A_2(n_2)\cdots\sum^{n_{d-1}-1}_{n_d=0}A_d(n_d)$$
と表せるような解について考えてみましょう。

 数列$f(n)$d'Alembertianであるとは、ある有理関数係数の一階作用素
$$L_k=p_k(n)N+q_k(n)\qquad(k=0,1,\ldots,d)$$
(ただし$N$は前進作用素$Nf(n)=f(n+1)$)が存在して
$$L_dL_{d-1}\cdots L_0f(n)=0$$
が成り立つことを言う。

 例えば超幾何数列$A_0(n),A_1(n)$を用いて
$$f(n)=A_0(n)\sum^n_{k=0}A_1(k)$$
と表せるような数列は
$$\l(N-\frac{A_0(n+2)A_1(n+2)}{A_0(n+1)A_1(n+1)}\r)\l(N-\frac{A_0(n+1)}{A_0(n)}\r)f(n)=0$$
という漸化式を満たします。
 ここでこの漸化式は$f(n)=A_0(n)$も解に持つことに注意しましょう。

漸化式の階数下げ

 いま与えられた漸化式のd'Alembertian数列による解を考える上で重要な事実として次のような命題が成り立ちます(証明については気が向いたら書きます)。

 d'Alembertian数列$f(n)\neq0$が多項式係数の線形漸化式
$$\sum^I_{i=0}p_i(n)f(n+i)=0$$
を満たすとき、同じ漸化式
$$\sum^I_{i=0}p_i(n)A(n+i)=0$$
を満たすような超幾何数列$A(n)$が存在する。

 このような$A(n)$に対して
$$g(n)=\frac{f(n)}{A(n)},\quad h(n)=g(n+1)-g(n)$$
とおくとこの漸化式の階数を下げることができます。実際これにより
\begin{align} &\phantom{={}}\sum^I_{i=0}p_i(n)f(n+i)\\ &=p_I(n)A(n+I)g(n+I)+\sum^{I-1}_{i=0}p_i(n)A(n+i)g(n+i)\\ &=\l(-\sum^{I-1}_{i=0}p_i(n)A(n+i)\r)g(n+I)+\sum^{I-1}_{i=0}p_i(n)A(n+i)g(n+i)\\ &=\sum^{I-1}_{i=0}p_i(n)A(n+i)(g(n+i)-g(n+I))\\ &=\sum^{I-1}_{i=0}p_i(n)A(n+i)\sum^{I-1}_{j=i}(g(n+j)-g(n+j+1))\\ &=\sum^{I-1}_{j=0}\l(\sum^j_{i=0}p_i(n)A(n+i)\r)(g(n+j)-g(n+j+1))\\ \end{align}
と変形できるので$h(n)$$I-1$階の漸化式
$$\sum^{I-1}_{j=0}\l(\sum^j_{i=0}p_i(n)\frac{A(n+i)}{A(n)}\r)h(n+j)=0$$
を満たすことがわかります。
 また$f(n)$がd'Alembertianであれば$h(n)$も再びd'Alembertianとなるのでこれが$0$でなければ$h(n)$についての漸化式にも超幾何数列による解$A'(n)$が存在することになります。このようにして超幾何数列による解が求まらなくなるまで階数を下げていくことで
\begin{align} f(n)={} &A(n),\\ &A(n)\sum^{n-1}_{n_1=0}A'(n_1),\\ &A(n)\sum^{n-1}_{n_1=0}A'(n_1)\sum^{n_1-1}_{n_2=0}A''(n_2),\\ &\quad\vdots \end{align}
といった形の解が得られることとなります。

計算例

 やはりこれも百聞は一見に如かず、ということで計算例をいくつか紹介しておきましょう。

 三項間漸化式
$$f(n+2)=(n+1)(f(n+1)+f(n))$$
の解を全て求めよ。

解説

 まずは超幾何数列による解を一つ求める。
 いま$a(n)=n+1,b(n)=1$とおくと$z$についての方程式は
$$z^2-z=0$$
つまり$z=1$と求まり、$c(n)$についての方程式は
$$(n+2)c(n+2)-(n+1)x(n+1)-c(n)=0$$
となる。これを解くと$c(n)=A$つまり$f(n)=An!$が得られる($A$は任意)。
 ここで
$$g(n)=\frac{f(n)}{n!},\quad h(n)=g(n+1)-g(n)$$
とおくと問題の漸化式は
\begin{align} (n+2)g(n+2)&=(n+1)g(n+1)+g(n)\\ (n+2)h(n+1)&=-h(n) \end{align}
と変形できるので
$$h(n)=B\frac{(-1)^n}{(n+1)!}$$
つまり
$$f(n)=Bn!\sum^n_{k=0}\frac{(-1)^k}{k!}$$
という解が得られる($B$は任意)。
 したがって求める解は
$$f(n)=n!\l(A+B\sum^n_{k=0}\frac{(-1)^k}{k!}\r)$$
で尽くされることとなる。

 ちなみにこの階数下げのテクニックは単に超幾何数列による解を求める場合にも役に立ちます。

 三項間漸化式
$$(n-1)f(n+2)-(n^2+3n-2)f(n+1)+2n(n+1)f(n)=0$$
の解を全て求めよ。

解説

 問題2として解説したように、これは
$$f(n)=A2^n+Bn!$$
という解を持つのであった。ここで$f(n)=2^n$という解を既知としてもう一方の解$f(n)=n!$を導出してみよう。
 いま
$$g(n)=2^{-n}f(n),\quad h(n)=g(n+1)-g(n)$$
とおくと問題の方程式は
\begin{align} 2(n-1)g(n+2)-(n^2+3n-2)g(n+1)+n(n+1)g(n)&=0\\ 2(n-1)h(n+1)-n(n+1)h(n)&=0 \end{align}
と変形できるので
$$h(n)=\frac{n(n-1)}{2(n-2)}h(n-1)=\frac{(n-1)n!}{2^n}B$$
つまり$B=1$とすると
$$f(n)=2^n\sum^{n-1}_{k=0}\frac{(k-1)k!}{2^k}$$
という解が得られる。
 ここでこのcreative telescopingを考えると
$$\frac{(n-1)n!}{2^{n+1}}=\frac{(n+1)!}{2^{n+1}}-\frac{n!}{2^n}$$
が成り立つので結局
$$f(n)=2^n\cdot\frac{n!}{2^n}=n!$$
という解が得られることとなる。

 このようにd'Alembertian数列による解
$$f(n)=A(n)\sum^n_{k=0}A'(k)$$
が得られても、$A'(n)$がGosper総和可能であれば
$$T(n+1)-T(n)=A'(k)$$
なる超幾何数列$T(n)$を用いて
$$f(n)=A(n)T(n+1)-A(n)T(0)$$
という閉形式が得られることにも注意しなければなりません。
 ちなみに問題4の場合は
$$A'(n)=\frac{(-1)^n}{n!}$$
がGosper総和可能ではないのであれが最善の結果となっています。

追記:三項間漸化式の一般解

 よくよく考えると三項間漸化式は解が一つ求まれば次のような解の公式を作れることに気付いたので簡単に書いておきます。

 $A(n),B(n)\neq0$
$$p(n)A(n+2)+q(n)A(n+1)+r(n)A(n)=0$$
および
$$\frac{B(n+1)}{B(n)}=\frac{r(n)}{p(n)}$$
を満たす数列とすると、三項間漸化式
$$p(n)f(n+2)+q(n)f(n+1)+r(n)f(n)=0$$
の一般解は
$$f(n)=A(n)\l(C_1+C_2\sum^{n-1}_{k=0}\frac{B(k)}{A(k)A(k+1)}\r)$$
と表せる($C_1,C_2$は任意)。

証明

$$g(n)=\frac{f(n)}{A(n)},\quad h(n)=g(n+1)-g(n)$$
とおくと問題の漸化式は
\begin{align} 0&=p(n)A(n+2)g(n+2)+q(n)A(n+1)g(n+1)+r(n)A(n)g(n)\\ &=p(n)A(n+2)g(n+2)-(p(n)A(n+2)+r(n)A(n))g(n+1)+r(n)A(n)g(n)\\ &=p(n)A(n+2)h(n+1)-r(n)A(n)h(n) \end{align}
と変形でき、これは
\begin{align} h(n+1) &=\frac{r(n)A(n)}{p(n)A(n+2)}h(n)\\ &=C\frac{B(n+1)}{A(n+1)A(n+2)} \end{align}
と解ける($C$は任意)。
 また
$$\frac{f(n+1)}{A(n+1)}-\frac{f(n)}{A(n)}=h(n)=C_2\frac{B(n)}{A(n)A(n+1)}$$
であったので
$$f(n)=A(n)\l(C_1+C_2\sum^{n-1}_{k=0}\frac{B(k)}{A(k)A(k+1)}\r)$$
を得る($C_1,C_2$は任意)。

 例えばこれにより上の問題1の一般解も簡単に求めることができます。

 三項間漸化式
$$3f(n+2)-nf(n+1)+(n-1)f(n)=0$$
の解を全て求めよ。

解説

 問題1として解説したようにこれは
$$f(n)=n^2-11n+27$$
という解を持つのであった。したがって上の公式より
$$f(n)=(n^2-11n+27)\l(C_1+C_2\sum^{n-1}_{k=2}\frac{(k-2)!}{3^k(k^2-11k+27)(k^2-9k+17)}\r)$$
が求める一般解となる($C_1,C_2$は任意)。

参考文献

[1]
M. Petkivšek, H. Wilf, D. Zeilberger, A=B, 1997
投稿日:315
更新日:3日前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

子葉
子葉
872
161411
主に複素解析、代数学、数論を学んでおります。 私の経験上、その証明が簡単に探しても見つからない、英語の文献を漁らないと載ってない、なんて定理の解説を主にやっていきます。 同じ経験をしている人の助けになれば。最近は自分用のノートになっている節があります。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中