漸化式

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

概要

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

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

${\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項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} に構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^n} をかければ、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が得られる。

階乗を含む漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=pnA_{n}+q(n!)}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a} (初期値)

n!で割って、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{A_{n+1}}{n!}=p\frac{A_{n}}{(n-1)!}+q}

ここで、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\frac{A_{n}}{(n-1)!}}

を導入すると、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n+1}=pB_{n}+q}

となって、これは、p=1のときには等差数列、p≠1のときは(階乗を含まない)2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} に(n-1)!をかければ、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が得られる。

分数型の漸化式1

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=\frac{A_{n}}{pA_{n}+q}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a} (初期値)

数列が構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が常に非零ならば逆数を取ることで、等差数列あるいは2項間漸化式に帰着できる。
つまり、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\frac{1}{A_{n}}}

を導入すると、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n+1}=qB_{n}+p}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{1}=\frac{1}{a}} (初期値)

となって、これはq=1のときは等差数列、q≠1のときは2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} の逆数を取ることで、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が得られる。

分数型の漸化式2

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=\frac{A_{n}+p}{qA_{n}+r}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a} (初期値)

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x=\frac{x+p}{qx+r}} (つまり、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle qx^2+(r-1)x-p=0} )

を解いて、その解を構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha,\beta} とおく。(重解の場合は構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha} のみ。)

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha,\beta=\frac{1-r\pm\sqrt{(1-r)^2+4pq}}{2q}}

よって、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}-\alpha=\frac{(1-\alpha q)(A_{n}-\alpha)}{q(A_{n}-\alpha)+(r+q\alpha)}}

(ここでは構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha} を使用したが、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha} と構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \beta} のどちらでも可)
ここで、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=A_{n}-\alpha}

を導入すると、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n+1}=\frac{(1-\alpha q)B_{n}}{qB_{n}+(r+q\alpha)}}

となって、分母分子を構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1-\alpha q)} で割ると、分数型の漸化式1 に帰着できる。そうして得た 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} に構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha} を加えることで、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が得られる。

次数の異なる漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=p(A_{n})^q}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a} (初期値)

数列が構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が常に正(つまりa>0かつp>0)ならば対数を取ることで、等差数列に帰着できる。
つまり、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\log \left(A_{n}\right)}

を導入すると、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n+1}=qB_{n}+\log(p)}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{1}=\log(a)} (初期値)

となって、これはp=1のときは等比数列、p≠1のときは2項間漸化式の形になるので、それぞれの解法に帰着できる。 そうして得た 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} を対数から戻して、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が得られる。

連立漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=pA_{n}+qB_{n}} (1)式
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n+1}=rA_{n}+sB_{n}} (2)式
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a,B_{1}=b} (初期値)

行列を使う解法

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} }

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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)式について構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} を等比数列として解いて、その結果を(2)式に代入して構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} を累乗を含む漸化式として解ける。
同様に、r=0のときも構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} と構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} を逆にして求まる。
q≠0かつr≠0のときは、(1)式より

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=pA_{n}+qB_{n}}

より

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\frac{1}{q}A_{n+1}-\frac{p}{q}A_{n}}

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}}

整理して、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{1}{q}A_{n+2}=\frac{s+p}{q}A_{n+1}+\frac{rq-ps}{q}A_{n}}

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+2}=(s+p)A_{n+1}+(rq-ps)A_{n}}

となって、これは3項間漸化式に帰着する。
構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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とする。
連立特性方程式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p+rx=y}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle q+sx=xy}

を解いて、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x,y)=(\alpha,\beta)} とおく。
上の式を下に代入して、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle q+sx=x(p+rx)} (つまり、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle rx^2+(p-s)x-q=0} )

よって、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha=\frac{s-p\pm\sqrt{(s-p)^2+qr}}{2r}} (構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (s-p)^2+qr} ≠0であり重解でないとする)

したがって、

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\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)} (複号同順)

よって、(構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\alpha,\beta)} の複号を添え字として)

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}+\alpha_{+} B_{n+1}=\beta_{+}(A_{n}+\alpha_{+} B_{n})}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}+\alpha_{-} B_{n+1}=\beta_{-}(A_{n}+\alpha_{-} B_{n})}

ここで、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_{n}=A_{n}+\alpha_{+} B_{n}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D_{n}=A_{n}+\alpha_{-} B_{n}}

を導入すると、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_{n+1}=\beta_{+}C_{n}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_{1}=A_{1}+\alpha_{+} B_{1}=a+\alpha_{+} b} (初期値)
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D_{n+1}=\beta_{-}D_{n}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D_{1}=A_{1}+\alpha_{-} B_{1}=a+\alpha_{-} b} (初期値)

となって、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_{n},D_{n}} ともに等比数列に帰着する。よって、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_{n}=(a+\alpha_{+} b)\beta_{+}^{n-1}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle D_{n}=(a+\alpha_{-} b)\beta_{-}^{n-1}}

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n},B_{n}} に戻して、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}+\alpha_{+} B_{n}=(a+\alpha_{+} b)\beta_{+}^{n-1}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}+\alpha_{-} B_{n}=(a+\alpha_{-} b)\beta_{-}^{n-1}}

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

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\frac{(a+\alpha_{+} b)\beta_{+}^{n-1}-(a+\alpha_{-} b)\beta_{-}^{n-1}}{\alpha_{+}-\alpha_{-}}}

また、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} を消去して

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}=\frac{\alpha_{-}(a+\alpha_{+} b)\beta_{+}^{n-1}-\alpha_{+}(a+\alpha_{-} b)\beta_{-}^{n-1}}{\alpha_{-}-\alpha_{+}}}

また、対称性から構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n},B_{n}} を逆にするような解き方でも同様。 (つまり、連立特性方程式の段階から構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n},B_{n}} や係数がすべて入れかえた解き方。)

応用

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

エルミート多項式

エルミート多項式構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H_{n}(x)=(-1)^n e^{x^2} \frac{d^n}{d^nx} e^{-x^2}} は、漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H_{n+1}(x)=2xH_{n}(x)-2nH_{n-1}(x)}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{d}{dx} H_{n}(x)=2nH_{n-1}(x)}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{d}{dx} H_{n}(x)=2xH_{n}(x)-H_{n+1}(x)}

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

ルジャンドル多項式

ルジャンドル多項式 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P_{n}(x)=2^n \sum_{k=0}^{n}x^k{\dbinom {n}{k}} \begin{pmatrix} \frac{n+k+1}{2} \\ n \end{pmatrix} } は、ボネの漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (n+1)P_{n+1}(x)=(2n+1)xP_{n}(x)-nP_{n-1}(x)}

を満たす。

二項係数

二項係数構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \dbinom {n}{k}=\frac{n!}{k!(n-k)!}} のnを固定してkについて数列とみると、漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \dbinom {n}{k}=\frac{n+1-k}{k} \dbinom {n}{k-1}}

を満たす。 他にも

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \dbinom {n}{k}=\dbinom {n-1}{k-1} + \dbinom {n-1}{k}} (パスカルの法則)
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \dbinom {n}{k}=\frac{n}{k} \dbinom {n-1}{k-1}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{n-2k}{n} \dbinom {n}{k}=\dbinom {n-1}{k} - \dbinom {n-1}{k-1}}

などを満たす。

指数タワー

漸化式

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=a^{A_{n}}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a} (初期値)

は、指数に構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} がある形である。
この解は、入れ子構造になって指数タワー(タワー関数)になる。

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}= a^{a^{n^{. ^{.^{.}}}}}} (n回の累乗)

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

コラッツ予想

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

これを漸化式で表せば、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}={\begin{cases}\frac{A_{n}}{2} &{\mbox{if }}A_{n}\equiv0 \\3A_{n}+1 &{\mbox{if }}A_{n}\equiv 1\end{cases}}{\pmod {2}}}

は、 任意の初期値構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{1}=a} に対して、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{N}=1} を満たすようなNが存在するということである。 (このとき、1→4→2→1というループになることは明らか)

ここで、「構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が奇数なら構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} に3を掛けて1を足す」についてだが、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が奇数なら3構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} +1は偶数なので、 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}} は偶数になって次の処理は偶数の「構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が偶数なら構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} を2で割る」である。 また、コラッツ予想は途中の値ではなく最終的に1に到達するかが重要なので、途中の値をショートカットしても良さそうである。
よって、コラッツ予想はショートカットした形式の

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}={\begin{cases}\frac{A_{n}}{2} &{\mbox{if }}A_{n}\equiv0 \\ \frac{3A_{n}+1}{2} &{\mbox{if }}A_{n}\equiv 1\end{cases}}{\pmod {2}}}

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

だた、この漸化式は場合分けが入っていてそのまま解けそうにはない。そこで漸化式の書き換えを試みよう。
構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} が偶数のときに上の処理、奇数のときに下の処理を実行する漸化式にしたいので、

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=(1-B_{n}) \frac{A_{n}}{2} + B_{n} \frac{3A_{n}+1}{2}}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}={\begin{cases}0 &{\mbox{if }}A_{n}\equiv0 \\1 &{\mbox{if }}A_{n}\equiv 1\end{cases}}{\pmod {2}}}

とすれば良い。ここで、以上のような構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} の例として構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\frac{1-(-1)^{A_{n}}}{2}} などがある。 この例で、漸化式を整理すると

• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n+1}=\frac{1}{2} \left( A_{n} + 2A_{n}B_{n} + B_{n} \right)}
• 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}=\frac{1-(-1)^{A_{n}}}{2}}

となる。
ここで、上の式は構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} にかかわらず成立する式である。 一方で下の式は構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B_{n}} に依存し、指数に構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A_{n}} がある形であり解くことが困難である。

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

関連項目

• 微分方程式