## 概要

**漸化式のラスボス**。これをスラスラ解けるようになると、心が晴れやかになる。

$3$ つの項の間に成り立つ漸化式を三項間漸化式といい、特に $p$ と $q$ を定数とした、

$$a_{n+2}=pa_{n+1}+qa_n$$

の形は**ノーヒントで解けるようにしておく必要**がある。

この漸化式は、$a_{n+2}$ を $\alpha^2$ に、$a_{n+1}$ を $\alpha$ に、$a_{n}$ を $1$ に置き換えた方程式

$$\alpha^2=p\alpha+q$$

の解（$m,n$ とおく）を用いて、

$$
\begin{cases}
a_{n+2}-ma_{n+1}=n(a_{n+1}-ma_{n})\\\\
a_{n+2}-na_{n+1}=m(a_{n+1}-na_{n})
\end{cases}
$$

と書き換えられる。ここから等比数列の一般項を用いて、数列 $\lbrace a_{n+1}-ma_{n}\rbrace$ の一般項と、数列 $\lbrace a_{n+1}-na_{n}\rbrace$ の一般項を出して、連立して $a_{n+1}$ を消すことで、一般項 $a_{n}$ が計算できる。

**ちょっと何を言っているかわからない**人は、下の例で確認しよう。

## 例

漸化式

$$a_1=1, \ a_2=1, \ a_{n+2}=5a_{n+1}-6a_n$$

を解く。そのためにまずは

$$\alpha^2=5\alpha-6$$

を解くと、$\alpha=2, \ 3$ なので、与えられた漸化式は

$$
\begin{cases}
a_{n+2}-2a_{n+1}=3(a_{n+1}-2a_{n})\cdots(1)\\\\
a_{n+2}-3a_{n+1}=2(a_{n+1}-3a_{n})\cdots(2)
\end{cases}
$$

と変形できる。

$(1)$より、数列 $\lbrace a_{n+1}-2a_n\rbrace$ は、初項 $-1$$(=a_2-2a_1)$、公比 $3$ の等比数列なので、一般項は、

$$
\begin{align}
a_{n+1}-2a_n&=-1\cdot 3^{n-1}\\\\
&=-3^{n-1}\cdots(1)'
\end{align}
$$

となる。

また、$(2)$ より、数列 $\\\\{a_{n+1}-3a_n\\\\} $ は、初項 $-2$$(=a_2-3a_1)$、公比 $2$ の等比数列なので、一般項は、

$$
\begin{align}
a_{n+1}-3a_n&=-2\cdot 2^{n-1}\\\\
&=-2^n\cdots(2)'
\end{align}
$$

となる。$(1)'$ から $(2)'$ を引くと、

$$
a_n=-3^{n-1}+2^n
$$

と一般項 $a_{n}$ が計算できる。[「等比数列」の辞書を復習したい方はこちらから](https://dic.okedou.app/words/%E7%AD%89%E6%AF%94%E6%95%B0%E5%88%97)。

## 証明

なぜいきなりこのような方程式

$$\alpha^2=p\alpha+q$$

が出てきたのかについて考える。

与えられた三項間漸化式を、 **ある文字 $m,n$ を使って**

$$
\begin{cases}
a_{n+2}-ma_{n+1}=n(a_{n+1}-ma_{n})\\\\
a_{n+2}-na_{n+1}=m(a_{n+1}-na_{n})
\end{cases}
$$

**という等比数列の漸化式の形に変形して、解ける形にしたいなあ**、というのが出発点。これを変形すると、

$$a_{n+2}=(m+n)a_{n+1}-mna_{n}$$

となるので、これが、元の漸化式と等しくなるためには、

$$
\begin{cases}
m+n=p\\\\
mn=-q
\end{cases}
$$

となるような $m,n$ を見つければ良い。

[解と係数の関係](https://dic.okedou.app/words/p/ZWIilMjwxvqVZ)より、$m, \ n$ は、とある $\alpha$ についての方程式

$$
\begin{align} 
\alpha^2-p\alpha-q&=0\\\\
\Leftrightarrow \ \alpha^2&=p\alpha+q
\end{align} 
$$

という方程式の解になる（これが突如現れた二次方程式の正体！）。

なので、この方程式を解けば、解の $\alpha$ を使ってうまく上のように変形できるという、なんだか答えありきな感じで出てきた方程式であった（特に $\alpha$ である必要もないのだが、よく $\alpha$ を使う）。

文章じゃよくわからん！とプンスカしている方は、例えば[ぶおとこばってんの動画](https://okedou.app/videos/CdZ9cPv0h7M)を見てみよう。

## 方程式が重解を持つ場合

上の二次方程式が重解を持つ場合は、解が1種類しか出てこないので、漸化式を1種類にしか変形しかできないことになる。ただその場合でも、頑張って解くことはできる。

例えば、漸化式

$$a_1=1, \ a_2=1, \ a_{n+2}=4a_{n+1}-4a_n$$

を解いてみる。このとき特性方程式

$$\alpha^2=4\alpha-4$$

を解くと、$\alpha=2$ の重解なので、与えられた漸化式は

$$
a_{n+2}-2a_{n+1}=2(a_{n+1}-2a_{n})
$$

と変形できる。よって、数列 $\lbrace a_{n+1}-2a_n\rbrace$ は、初項 $-1$$(=a_2-2a_1)$、公比 $2$ の等比数列なので、一般項は、

$$
\begin{align}
a_{n+1}-2a_n&=-1\cdot 2^{n-1}\\\\
&=-2^{n-1}
\end{align}
$$

となる。

次のステージとして、**この漸化式を直接解いて、数列 $\lbrace a_n\rbrace$ の一般項を求めにいく。**

上の漸化式の両辺 $2^{n+1}$ で割ると、

$$
\frac{a_{n+1}}{2^{n+1}}-\frac{a_n}{2^n}=-\frac{1}{4}
$$

となるので、

$$\frac{a_n}{2^n}=b_n$$

とおけば、

$$
b_{n+1}-b_n=-\frac{1}{4}
$$

を得る。

これはつまり数列 $\lbrace b_n \rbrace$ が[等差数列](https://dic.okedou.app/words/p/NxOSY3nyPtopg)であることを意味していて、この一般項は簡単に求められる。初項 $\displaystyle\frac{1}{2}$$\left(=\displaystyle\frac{a_1}{2}\right)$ であることを踏まえると、

$$
\begin{align}
b_n&=\frac{1}{2}-\frac{1}{4}(n-1)\\\\
&=-\frac{n-3}{4}
\end{align}
$$

と求められる。よって、求める数列 $\lbrace a_n\rbrace$ の一般項は、

$$
\begin{align}
a_n&=2^nb_n\\\\
&=-2^{n-2}\left(n-3\right)
\end{align}
$$

となる。

### 補足

漸化式を解く際は、自分で $a_2, \ a_3$ を計算してみて、 **一般項の答えがあってそうかどうか確認できる**ので、安心感がある。

[二項間漸化式](https://dic.okedou.app/words/p/PFcFWfS18t51m)のときと同様、方程式

$$\alpha^2=p\alpha+q$$

は、**特性方程式**とも呼ばれる。

三項間漸化式

概要

例

証明

方程式が重解を持つ場合

補足

タグ