漸化式

漸化式（ぜんかしき）とは、各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式。

概要

ある種の漸化式はしばしば差分方程式と呼ばれ、差分方程式という言葉を単に「漸化式」と同義なものとして扱うことも多い。
漸化式を解くとは、 添字に関する非再帰的な関数として一般項を表す式を得ることをいう。

数値解析で微分方程式の近似解を求める場合にも用いられる。例えば

${\frac {dy}{dx}}=3y+2$

という微分方程式は、

${\frac {Y_{n}-Y_{n-1}}{\Delta x}}=3Y_{n-1}+2$

という漸化式で近似することができ、この結果得られる$Y_{n}$は、$x$を$\Delta x$刻みで変化させた時の$y$の値の近似値として得ることができる。

解く上での考え方

まず漸化式を解く上で必要な前提知識だが、四則演算はもちろん、 分数や指数・累乗、階乗なども登場する漸化式があるのでここら辺は押さえておきたい。 総和(Σ)も必須と言っても過言ではないだろう。対数や総積(Π)、行列・ベクトルを使うと便利なものもある。

また、特性方程式なる式も多々登場するが、この式は別の簡単な形に帰着させるための手法を定型化したようなものである。 なので、突き詰めれば特性方程式を知らずともよく意味を考えることで解けるが、公式のように覚えると楽だというものである。

そして、この「別の簡単な形に帰着させる」・「既知の方法に書き換える」という考え方は大変重要である。 何故なら、漸化式を解くのは微分方程式を解くように複雑で汎用的な方法はないし、複雑な場合は解ける保証もない。 行列のn乗のように複雑さを別のところに丸投げするというのもあるが、これも行列という研究されている別分野の問題に帰着させているのである。

解法

以下の様々な漸化式の解法を示していく。
$A_{n}$を求める数列として、とくに断りのない限りnは1から始めるとする。 初期値などの定数は小文字で書いて、計算の仮定で導入する数列は大文字で書いて、両者を区別する。
また、ある漸化式は他の漸化式を包含している。 以下ではとくに断りのない限り一般の係数対してに解いているが、実際には特定の係数ではより簡単に解く方法もある。 例えば、階差数列で解いている数列は、係数を特定の値にすれば等差数列も表している。そのようなときは等差数列の解法で解いた方が簡単だろう。

等差数列

• $A_{n+1}=A_{n}+d$
• $A_{1}=a$(初期値)

この形の漸化式で表される数列は、初項a,公差dの等差数列と呼ばれる。

${\begin{aligned}A_{n}&=A_{1}+\sum _{k=2}^{n}\left(A_{k}-A_{k-1}\right)\left(\because \left(\sum _{k=2}^{n}A_{k-1}\right)+A_{n}=A_{1}+\left(\sum _{k=2}^{n}A_{k}\right)\right)\\&=a+\sum _{k=2}^{n}{d}\\&=a+(n-1)d\end{aligned}}$

等比数列

• $A_{n+1}=rA_{n}$
• $A_{1}=a$(初期値)

この形の漸化式で表される数列は、初項a,公比rの等比数列と呼ばれる。
a=0のときは常に0になるので、a≠0とする。また、r=0のとき第二項以降が常に0になるので、r≠0とする。

正攻法

${\begin{aligned}A_{n}&=A_{1}\prod _{k=2}^{n}{\frac {A_{k}}{A_{k-1}}}\left(\because \left(\prod _{k=2}^{n}A_{k-1}\right)A_{n}=A_{1}\left(\prod _{k=2}^{n}A_{k}\right)\right)\\&=a\prod _{k=2}^{n}{r}\\&=ar^{n-1}\end{aligned}}$

対数を使う解法　

数列が$A_{n}$が常に正(つまりa>0かつr>0)ならば対数を取ることで、等差数列に帰着できる。(とはいえ、そこまでするほど難しくないのでほとんどしない。)
つまり、

$B_{n}=\log \left(A_{n}\right)$

を導入すると、

• $B_{n+1}=B_{n}+\log(r)$
• $B_{1}=\log(a)$(初期値)

となって、これは、初項log(a),公差log(r)の等差数列であるので、

$B_{n}=\log(a)+(n-1)\log(r)$

対数を戻して、

$A_{n}=ar^{n-1}$

よって、上記の解法と答えが一致する。

階差数列

• $A_{n+1}=A_{n}+(pn+q)$
• $A_{1}=a$(初期値)

この形の漸化式で表される数列は、階差数列と呼ばれる。

${\begin{aligned}A_{n}&=A_{1}+\sum _{k=2}^{n}\left(A_{k}-A_{k-1}\right)\left(\because \left(\sum _{k=2}^{n}A_{k-1}\right)+A_{n}=A_{1}+\left(\sum _{k=2}^{n}A_{k}\right)\right)\\&=a+\sum _{k=2}^{n}{(pk+q)}\\&=a+p\sum _{k=2}^{n}{k}+q\sum _{k=2}^{n}{1}\\&=a+p\left({\frac {n(n+1)}{2}}-1\right)+q(n-1)\\&=a+p\left({\frac {n^{2}+n-2}{2}}\right)+q(n-1)\end{aligned}}$

より一般には、

• $A_{n+1}=A_{n}+f(n)$
• $A_{1}=a$(初期値)

に対して、

${\begin{aligned}A_{n}&=A_{1}+\sum _{k=2}^{n}\left(A_{k}-A_{k-1}\right)\left(\because \left(\sum _{k=2}^{n}A_{k-1}\right)+A_{n}=A_{1}+\left(\sum _{k=2}^{n}A_{k}\right)\right)\\&=a+\sum _{k=2}^{n}{f(n)}\end{aligned}}$

であって、f(n)の総和が求まるならば解が出る。

階比数列

• $A_{n+1}=pnA_{n}$
• $A_{1}=a$(初期値)

この形の漸化式で表される数列は、階比数列と呼ばれる。
a=0のときは常に0になるので、a≠0とする。また、p=0のとき第二項以降が常に0になるので、p≠0とする。

${\begin{aligned}A_{n}&=A_{1}\prod _{k=2}^{n}{\frac {A_{k}}{A_{k-1}}}\left(\because \left(\prod _{k=2}^{n}A_{k-1}\right)A_{n}=A_{1}\left(\prod _{k=2}^{n}A_{k}\right)\right)\\&=a\prod _{k=2}^{n}{pn}\\&=ap^{n-1}n!\end{aligned}}$

より一般には、

• $A_{n+1}=f(n)A_{n}$
• $A_{1}=a$(初期値)

に対して、(やはり、a=0のときは常に0になるので、a≠0とする。また、f(n)=0になるようなnが存在すれば、それ以降は0になるのでそうでない範囲を考える。)

${\begin{aligned}A_{n}&=A_{1}\prod _{k=2}^{n}{\frac {A_{k}}{A_{k-1}}}\left(\because \left(\prod _{k=2}^{n}A_{k-1}\right)A_{n}=A_{1}\left(\prod _{k=2}^{n}A_{k}\right)\right)\\&=a\prod _{k=2}^{n}{f(n)}\end{aligned}}$

であって、f(n)の総積が求まるならば解が出る。

2項間漸化式

• $A_{n+1}=pA_{n}+q$
• $A_{1}=a$(初期値)

特性方程式

$x=px+q$

を解いて、その解を$\alpha$とおく。 p=1のときは等差数列なのでp≠1として

$\alpha ={\frac {q}{1-p}}$

よって、

$A_{n+1}-\alpha =p(A_{n}-\alpha )$

ここで、

$B_{n}=A_{n}-\alpha$

を導入すると、

• $B_{n+1}=pB_{n}$
• $B_{1}=a-\alpha$(初期値)

となって、これは、初項(a-$\alpha$),公比pの等比数列であるので、

$B_{n}=(a-\alpha )p^{n-1}$

$A_{n}$に戻して、

$A_{n}=(a-\alpha )p^{n-1}+\alpha$

$\alpha$をp,qに戻せば、

$A_{n}=\left(a-{\frac {q}{1-p}}\right)p^{n-1}+{\frac {q}{1-p}}$

3項間漸化式

• $A_{n+2}=pA_{n+1}+qA_{n}$
• $A_{1}=a,A_{2}=b$(初期値)

フィボナッチ数列は3項間漸化式の例である。

特性方程式を使う解法

特性方程式

$x^{2}=px+q$

を解いて、その解を$\alpha ,\beta$とおく。(重解の場合は$\alpha$のみ。)

$\alpha ,\beta ={\frac {p\pm {\sqrt {p^{2}+4q}}}{2}}$

よって、

• $A_{n+2}-\alpha A_{n+1}=\beta (A_{n+1}-\alpha A_{n})$
• $A_{n+2}-\beta A_{n+1}=\alpha (A_{n+1}-\beta A_{n})$

ここで、

• $B_{n}=A_{n+1}-\alpha A_{n}$
• $C_{n}=A_{n+1}-\beta A_{n}$

を導入すると、

• $B_{n+1}=\beta B_{n}$
• $B_{1}=A_{2}-\alpha A_{1}=b-\alpha a$(初期値)
• $C_{n+1}=\beta C_{n}$
• $C_{1}=A_{2}-\beta A_{1}=b-\beta a$(初期値)

となって、$B_{n},C_{n}$ともに等比数列に帰着する。よって、

• $B_{n}=(b-\alpha a)\beta ^{n-1}$
• $C_{n}=(b-\beta a)\alpha ^{n-1}$

$A_{n}$に戻して、

• $A_{n+1}=\alpha A_{n}+(b-\alpha a)\beta ^{n-1}$
• $A_{n+1}=\beta A_{n}+(b-\beta a)\alpha ^{n-1}$

重解でないとき($p^{2}+4q\neq 0$)は、2式の差より

$(\alpha -\beta )A_{n}=(b-\beta a)\alpha ^{n-1}-(b-\alpha a)\beta ^{n-1}$

よって、

$A_{n}={\frac {(b-\beta a)\alpha ^{n-1}-(b-\alpha a)\beta ^{n-1}}{\alpha -\beta }}$

一方で、以上の方法は重解のとき($p^{2}+4q=0$)に$\alpha =\beta$となるので0割りになってしまい使えない。 そのため、重解のときは

• $A_{n+1}=\alpha A_{n}+(b-\alpha a)\alpha ^{n-1}$

を累乗を含む漸化式として再度解く必要がある。

行列を使う解法

$A_{n+2}=pA_{n+1}+qA_{n}$

より

• $A_{n+2}=pA_{n+1}+qA_{n}$
• $A_{n+1}=1A_{n+1}+0A_{n}$

を連立漸化式とみなして、行列を用いた解法に帰着できる。(連立漸化式を3項間漸化式に帰着させる方法もあるが、こちらは循環してしまうので注意。)

${\begin{pmatrix}A_{n+2}\\A_{n+1}\end{pmatrix}}={\begin{pmatrix}p&q\\1&0\end{pmatrix}}\cdot {\begin{pmatrix}A_{n+1}\\A_{n}\end{pmatrix}}$

よって、

${\begin{pmatrix}A_{n+1}\\A_{n}\end{pmatrix}}={\begin{pmatrix}p&q\\1&0\end{pmatrix}}^{n-1}\cdot {\begin{pmatrix}b\\a\end{pmatrix}}$

n項間漸化式

• $A_{n+3}=pA_{n+2}+qA_{n+1}+rA_{n}$
• $A_{1}=a,A_{2}=b,A_{3}=c$(初期値)

上記は、4項間漸化式で、3項間漸化式をさらに拡張したような形式である。 このようなn項間漸化式を解く際には、3項間漸化式の行列を使う解法と同様の方法が使える。

$A_{n+3}=pA_{n+2}+qA_{n+1}+rA_{n}$

より

• $A_{n+3}=pA_{n+2}+qA_{n+1}+rA_{n}$
• $A_{n+2}=1A_{n+2}+0A_{n+1}+0A_{n}$
• $A_{n+1}=0A_{n+2}+1A_{n+1}+0A_{n}$

を連立漸化式とみなして、行列を用いた解法に帰着できる。

${\begin{pmatrix}A_{n+3}\\A_{n+2}\\A_{n+1}\end{pmatrix}}={\begin{pmatrix}p&q&r\\1&0&0\\0&1&0\end{pmatrix}}\cdot {\begin{pmatrix}A_{n+2}\\A_{n+1}\\A_{n}\end{pmatrix}}$

よって、

${\begin{pmatrix}A_{n+2}\\A_{n+1}\\A_{n}\end{pmatrix}}={\begin{pmatrix}p&q&r\\1&0&0\\0&1&0\end{pmatrix}}^{n-1}\cdot {\begin{pmatrix}c\\b\\a\end{pmatrix}}$

なお、n項間漸化式で使用する行列は(n-1)次の正方行列になるので、nが増加すると問題は複雑になっていく。

累乗を含む漸化式

• $A_{n+1}=pA_{n}+qr^{n}$
• $A_{1}=a$(初期値)

r=0のときは等比数列なのでr≠0として、$r^{n+1}$で割って、

${\frac {A_{n+1}}{r^{n+1}}}={\frac {p}{r}}{\frac {A_{n}}{r^{n}}}+{\frac {q}{r}}$

ここで、

$B_{n}={\frac {A_{n}}{r^{n}}}$

を導入すると、

$B_{n+1}={\frac {p}{r}}B_{n}+{\frac {q}{r}}$

となって、これは、p=rのときには等差数列、p≠rのときは(累乗を含まない)2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た$B_{n}$に$r^{n}$をかければ、$A_{n}$が得られる。

階乗を含む漸化式

• $A_{n+1}=pnA_{n}+q(n!)$
• $A_{1}=a$(初期値)

n!で割って、

${\frac {A_{n+1}}{n!}}=p{\frac {A_{n}}{(n-1)!}}+q$

ここで、

$B_{n}={\frac {A_{n}}{(n-1)!}}$

を導入すると、

$B_{n+1}=pB_{n}+q$

となって、これは、p=1のときには等差数列、p≠1のときは(階乗を含まない)2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た$B_{n}$に(n-1)!をかければ、$A_{n}$が得られる。

分数型の漸化式1

• $A_{n+1}={\frac {A_{n}}{pA_{n}+q}}$
• $A_{1}=a$(初期値)

数列が$A_{n}$が常に非零ならば逆数を取ることで、等差数列あるいは2項間漸化式に帰着できる。
つまり、

$B_{n}={\frac {1}{A_{n}}}$

を導入すると、

• $B_{n+1}=qB_{n}+p$
• $B_{1}={\frac {1}{a}}$(初期値)

となって、これはq=1のときは等差数列、q≠1のときは2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た $B_{n}$の逆数を取ることで、$A_{n}$が得られる。

分数型の漸化式2

• $A_{n+1}={\frac {A_{n}+p}{qA_{n}+r}}$
• $A_{1}=a$(初期値)

q=0かつr=1のときは等差数列、q=0かつr≠1のときは2項間漸化式なので、q≠0とする。
特性方程式

$x={\frac {x+p}{qx+r}}$(つまり、$qx^{2}+(r-1)x-p=0$)

を解いて、その解を$\alpha ,\beta$とおく。(重解の場合は$\alpha$のみ。)

$\alpha ,\beta ={\frac {1-r\pm {\sqrt {(1-r)^{2}+4pq}}}{2q}}$

よって、

$A_{n+1}-\alpha ={\frac {(1-\alpha q)(A_{n}-\alpha )}{q(A_{n}-\alpha )+(r+q\alpha )}}$

(ここでは$\alpha$を使用したが、$\alpha$と$\beta$のどちらでも可)
ここで、

$B_{n}=A_{n}-\alpha$

を導入すると、

$B_{n+1}={\frac {(1-\alpha q)B_{n}}{qB_{n}+(r+q\alpha )}}$

となって、分母分子を$(1-\alpha q)$で割ると、分数型の漸化式1 に帰着できる。そうして得た $B_{n}$に$\alpha$を加えることで、$A_{n}$が得られる。

次数の異なる漸化式

• $A_{n+1}=p(A_{n})^{q}$
• $A_{1}=a$(初期値)

数列が$A_{n}$が常に正(つまりa>0かつp>0)ならば対数を取ることで、等差数列に帰着できる。
つまり、

$B_{n}=\log \left(A_{n}\right)$

を導入すると、

• $B_{n+1}=qB_{n}+\log(p)$
• $B_{1}=\log(a)$(初期値)

となって、これはp=1のときは等比数列、p≠1のときは2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た $B_{n}$を対数から戻して、$A_{n}$が得られる。

連立漸化式

• $A_{n+1}=pA_{n}+qB_{n}$(1)式
• $B_{n+1}=rA_{n}+sB_{n}$(2)式
• $A_{1}=a,B_{1}=b$(初期値)

行列を使う解法

上の様な漸化式は、行列を使うと次の様に書ける。

${\begin{pmatrix}A_{n+1}\\B_{n+1}\end{pmatrix}}={\begin{pmatrix}p&q\\r&s\end{pmatrix}}\cdot {\begin{pmatrix}A_{n}\\B_{n}\end{pmatrix}}$

この式は、行列の等比数列の様な式になっているので、数の等比数列と同じ様に、次の式で解くことができる。

${\begin{pmatrix}A_{n}\\B_{n}\end{pmatrix}}={\begin{pmatrix}p&q\\r&s\end{pmatrix}}^{n-1}\cdot {\begin{pmatrix}a\\b\end{pmatrix}}$

行列のn乗を(一般的に)求める方法として、対角化などがある。

3項間漸化式などに帰着する解法

q=0のときは(1)式について$A_{n}$を等比数列として解いて、その結果を(2)式に代入して$B_{n}$を累乗を含む漸化式として解ける。
同様に、r=0のときも$A_{n}$と$B_{n}$を逆にして求まる。
q≠0かつr≠0のときは、(1)式より

$A_{n+1}=pA_{n}+qB_{n}$

より

$B_{n}={\frac {1}{q}}A_{n+1}-{\frac {p}{q}}A_{n}$

これを(2)式に代入して

${\frac {1}{q}}A_{n+2}-{\frac {p}{q}}A_{n+1}=rA_{n}+{\frac {s}{q}}A_{n+1}-{\frac {ps}{q}}A_{n}$

整理して、

${\frac {1}{q}}A_{n+2}={\frac {s+p}{q}}A_{n+1}+{\frac {rq-ps}{q}}A_{n}$

$A_{n+2}=(s+p)A_{n+1}+(rq-ps)A_{n}$

となって、これは3項間漸化式に帰着する。
$A_{n}$と$B_{n}$を逆にして同様の計算を実行することにより、$B_{n}$も3項間漸化式に帰着する。

• $A_{n+2}=(s+p)A_{n+1}+(rq-ps)A_{n}$
• $B_{n+2}=(s+p)B_{n+1}+(rq-ps)B_{n}$

ここで、$A_{n}$と$B_{n}$で漸化式は同じになっていて、初期値だけが違うことがわかる。 なお、3項間漸化式を解くには最初の2項が初期値として必要なので、第2項は漸化式から計算しておく必要がある。 そして、3項間漸化式の係数は行列 $R={\begin{pmatrix}p&q\\r&s\end{pmatrix}}$(行列なので慣例的に大文字で表記した) のトレースと行列式になっていることがわかる。
つまり、

• $A_{n+2}=tr(R)A_{n+1}-\det(R)A_{n}$
• $B_{n+2}=tr(R)B_{n+1}-\det(R)B_{n}$

2つの等比数列に帰着する解法

r=0のときは、3項間漸化式などに帰着する解法 に記した通りなのでr≠0とする。
連立特性方程式

• $p+rx=y$
• $q+sx=xy$

を解いて、$(x,y)=(\alpha ,\beta )$とおく。
上の式を下に代入して、

$q+sx=x(p+rx)$(つまり、$rx^{2}+(p-s)x-q=0$)

よって、

$\alpha ={\frac {s-p\pm {\sqrt {(s-p)^{2}+qr}}}{2r}}$($(s-p)^{2}+qr$≠0であり重解でないとする)

したがって、

$(\alpha ,\beta )=\left({\frac {s-p\pm {\sqrt {(s-p)^{2}+qr}}}{2r}},p+r{\frac {s-p\pm {\sqrt {(s-p)^{2}+qr}}}{2r}}\right)$(複号同順)

よって、($(\alpha ,\beta )$の複号を添え字として)

• $A_{n+1}+\alpha _{+}B_{n+1}=\beta _{+}(A_{n}+\alpha _{+}B_{n})$
• $A_{n+1}+\alpha _{-}B_{n+1}=\beta _{-}(A_{n}+\alpha _{-}B_{n})$

ここで、

• $C_{n}=A_{n}+\alpha _{+}B_{n}$
• $D_{n}=A_{n}+\alpha _{-}B_{n}$

を導入すると、

• $C_{n+1}=\beta _{+}C_{n}$
• $C_{1}=A_{1}+\alpha _{+}B_{1}=a+\alpha _{+}b$(初期値)
• $D_{n+1}=\beta _{-}D_{n}$
• $D_{1}=A_{1}+\alpha _{-}B_{1}=a+\alpha _{-}b$(初期値)

となって、$C_{n},D_{n}$ともに等比数列に帰着する。よって、

• $C_{n}=(a+\alpha _{+}b)\beta _{+}^{n-1}$
• $D_{n}=(a+\alpha _{-}b)\beta _{-}^{n-1}$

$A_{n},B_{n}$に戻して、

• $A_{n}+\alpha _{+}B_{n}=(a+\alpha _{+}b)\beta _{+}^{n-1}$
• $A_{n}+\alpha _{-}B_{n}=(a+\alpha _{-}b)\beta _{-}^{n-1}$

2式の差より(先に重解でないと仮定したが、重解だとここで0割りになる)

$B_{n}={\frac {(a+\alpha _{+}b)\beta _{+}^{n-1}-(a+\alpha _{-}b)\beta _{-}^{n-1}}{\alpha _{+}-\alpha _{-}}}$

また、$B_{n}$を消去して

$A_{n}={\frac {\alpha _{-}(a+\alpha _{+}b)\beta _{+}^{n-1}-\alpha _{+}(a+\alpha _{-}b)\beta _{-}^{n-1}}{\alpha _{-}-\alpha _{+}}}$

また、対称性から$A_{n},B_{n}$を逆にするような解き方でも同様。 (つまり、連立特性方程式の段階から$A_{n},B_{n}$や係数がすべて入れかえた解き方。)

応用

漸化式は数(実数や複素数)だけでなく、#解法の連立漸化式のようにベクトルの間にも考えられた。 さらには、関数や多項式、行列の間にも同様の考え方ができる。

エルミート多項式

エルミート多項式$H_{n}(x)=(-1)^{n}e^{x^{2}}{\frac {d^{n}}{d^{n}x}}e^{-x^{2}}$は、漸化式

• $H_{n+1}(x)=2xH_{n}(x)-2nH_{n-1}(x)$
• ${\frac {d}{dx}}H_{n}(x)=2nH_{n-1}(x)$
• ${\frac {d}{dx}}H_{n}(x)=2xH_{n}(x)-H_{n+1}(x)$

を満たす。 多項式の漸化式なので、四則演算だけでなく微分演算も使用できる。

ルジャンドル多項式

ルジャンドル多項式 $P_{n}(x)=2^{n}\sum _{k=0}^{n}x^{k}{\dbinom {n}{k}}{\begin{pmatrix}{\frac {n+k+1}{2}}\\n\end{pmatrix}}$ は、ボネの漸化式

• $(n+1)P_{n+1}(x)=(2n+1)xP_{n}(x)-nP_{n-1}(x)$

を満たす。

二項係数

二項係数${\dbinom {n}{k}}={\frac {n!}{k!(n-k)!}}$のnを固定してkについて数列とみると、漸化式

• ${\dbinom {n}{k}}={\frac {n+1-k}{k}}{\dbinom {n}{k-1}}$

を満たす。 他にも

• ${\dbinom {n}{k}}={\dbinom {n-1}{k-1}}+{\dbinom {n-1}{k}}$(パスカルの法則)
• ${\dbinom {n}{k}}={\frac {n}{k}}{\dbinom {n-1}{k-1}}$
• ${\frac {n-2k}{n}}{\dbinom {n}{k}}={\dbinom {n-1}{k}}-{\dbinom {n-1}{k-1}}$

などを満たす。

指数タワー

漸化式

• $A_{n+1}=a^{A_{n}}$
• $A_{1}=a$(初期値)

は、指数に$A_{n}$がある形である。
この解は、入れ子構造になって指数タワー(タワー関数)になる。

$A_{n}=a^{a^{n^{.^{.^{.}}}}}$(n回の累乗)

このタワー関数はa=2などでは指数や階乗に比べて急速に増大する。

コラッツ予想

コラッツ予想は、任意の正の整数nに対して、 nが偶数ならnを2で割り、 nが奇数ならnに3を掛けて1を足す。 このとき、どんな初期値nから始めても有限回の操作ので1に到達する（そして1→4→2→1というループに入る）という予想である。

これを漸化式で表せば、

• $A_{n+1}={\begin{cases}{\frac {A_{n}}{2}}&{\mbox{if }}A_{n}\equiv 0\\3A_{n}+1&{\mbox{if }}A_{n}\equiv 1\end{cases}}{\pmod {2}}$

は、 任意の初期値$A_{1}=a$に対して、$A_{N}=1$を満たすようなNが存在するということである。 (このとき、1→4→2→1というループになることは明らか)

ここで、「$A_{n}$が奇数なら$A_{n}$に3を掛けて1を足す」についてだが、$A_{n}$が奇数なら3$A_{n}$+1は偶数なので、 $A_{n+1}$は偶数になって次の処理は偶数の「$A_{n}$が偶数なら$A_{n}$を2で割る」である。 また、コラッツ予想は途中の値ではなく最終的に1に到達するかが重要なので、途中の値をショートカットしても良さそうである。
よって、コラッツ予想はショートカットした形式の

• $A_{n+1}={\begin{cases}{\frac {A_{n}}{2}}&{\mbox{if }}A_{n}\equiv 0\\{\frac {3A_{n}+1}{2}}&{\mbox{if }}A_{n}\equiv 1\end{cases}}{\pmod {2}}$

と書ける。(上記の漸化式とは個々の項は対応していないので注意。ループも4がスキップされて、1→2→1になる)

だた、この漸化式は場合分けが入っていてそのまま解けそうにはない。そこで漸化式の書き換えを試みよう。
$A_{n}$が偶数のときに上の処理、奇数のときに下の処理を実行する漸化式にしたいので、

• $A_{n+1}=(1-B_{n}){\frac {A_{n}}{2}}+B_{n}{\frac {3A_{n}+1}{2}}$
• $B_{n}={\begin{cases}0&{\mbox{if }}A_{n}\equiv 0\\1&{\mbox{if }}A_{n}\equiv 1\end{cases}}{\pmod {2}}$

とすれば良い。ここで、以上のような$B_{n}$の例として$B_{n}={\frac {1-(-1)^{A_{n}}}{2}}$などがある。 この例で、漸化式を整理すると

• $A_{n+1}={\frac {1}{2}}\left(A_{n}+2A_{n}B_{n}+B_{n}\right)$
• $B_{n}={\frac {1-(-1)^{A_{n}}}{2}}$

となる。
ここで、上の式は$B_{n}$にかかわらず成立する式である。 一方で下の式は$B_{n}$に依存し、指数に$A_{n}$がある形であり解くことが困難である。

しかしながら、この方法では初期値を任意の正の整数に限る必要がなくなる。なぜなら偶数や奇数といった表現を使っていないからである。 そのため、整数に限らず複素数全体を初期値にすることができる。さらに行列指数関数を利用することで正方行列も入れることができる。

関連項目

• 微分方程式