（注意）【～型】はパターンを意識するためであり，当サイト独自の表現です。答案などに書かないようにしてください。
ここでは，隣接３項間型漸化式について扱います。難易度はかなり高く，習得を諦めてしまう人も少なくない問題です。しかし，入試においては重要で，大学のレベルが上がるにつれて重要度は増す。特に，理系の場合は習得が必須です。繰り返し解いて，ぜひ習得を目指しましょう。
【隣接３項間型】$a_{n+2}+pa_{n+1}+qa_n=0$
(例) $a_{n+2}+6a_{n+1}+5a_n=0$
(例) $a_{n+2}-4a_{n+1}+4a_n=0$
【隣接３項間型】漸化式の解法
この型の漸化式は解き方が決まっているため，パターンとして暗記してしまうのが良い。しかし，難易度が高く解答も長いため，すべて覚えようとすると習得にかなりの時間を要します。
ポイントは，全体を丸暗記するのではなく，暗記しておかないと発想しにくい部分のみを覚え，他はその場で考えることです。覚えるべき部分は以下で，詳細は問題の解説で説明しますが，以下の①～③を流れの軸として覚えることが，隣接３項間型漸化式習得の近道です！
【隣接３項間型】の問題と解説
問題
(1) $a_1=0$，$a_2=1$,
$a_{n+2}-a_{n+1}-6a_n=0$
(2) $a_1=1$，$a_2=4$,
$a_{n+2}-6a_{n+1}+9a_n=0$
解説（授業）
(1) $a_1=0,a_2=1$,
$a_{n+2}-a_{n+1}-6a_n=0$
まず $x^2-x-6=0$ を解く。【暗記１】
$x=3,-2$
この $2$ 解を
$a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_n)$【暗記２】
に代入することで，漸化式を変形します。(代入する値を入れ替えて $2$ 式作成)
①，②から
$\left\{a_{n+1}-3a_n\right\}$，$\left\{a_{n+1}+2a_n\right\}$
の一般項を【等比型】として求める。【暗記３】
ここまでが，暗記を含めて覚える部分になります。
以降は，暗記ではなく考えて解き進めます。
まず①を【等比型】と見て，$\left\{a_{n+1}-3a_n\right\}$ の一般項 $a_{n+1}-3a_n$ を求めます。
$a_{n+2}-3a_{n+1}$ $=$ $-2$$(a_{n+1}-3a_n)$ 【等比型】･･･①
①より $\left\{a_{n+1}-3a_n\right\}$ は
初項 $a_2-3a_1=1$，公比 $-2$ の等比数列
よって $a_{n+1}-3a_n$ $=$ $1$ $\cdot$ $(-2)^{n-1}$
∴ $a_{n+1}-3a_n$ $=$ $(-2)^{n-1}$ ･･･ ③
次に②を【等比型】と見て，$\left\{a_{n+1}+2a_n\right\}$ の一般項 $a_{n+1}+2a_n$ を求めます。
$a_{n+2}+2a_{n+1}$ $=$ $3$$(a_{n+1}+2a_n)$ 【等比型】･･･②
②より $\left\{a_{n+1}+2a_n\right\}$ は，
初項 $a_2+2a_1=1$，公比 $3$ の等比数列
よって $a_{n+1}+2a_n$ $=$ $1$ $\cdot$ $3^{n-1}$
∴ $a_{n+1}+2a_n$ $=$ $3^{n-1}$ ･･･④
$\begin{cases}a_{n+1}-3a_n=(-2)^{n-1} \enspace \cdots \text{③}\\a_{n+1}+2a_n=3^{n-1}\enspace \cdots \text{④}\end{cases}$
③と④の差をとれば，$a_{n+1}$ が消え，$a_n$ が求まります。
$a_n$ の係数が正となるように，④ $-$ ③とするのが良さそうですね。
④ $-$ ③とすると
$5a_n=3^{n-1}-(-2)^{n-1}$
よって，$5$ で割って
$a_n=\displaystyle\frac{1}{5}\left\{3^{n-1}-(-2)^{n-1}\right\}$ (答)
(2) $a_1=1,a_2=4$,
$a_{n+2}-6a_{n+1}+9a_n=0$
$x^2-6x+9=0$ を解くと，
$(x-3)^2=0$
$x=3$ (重解)
重解となるとき，少し困ったことが起きます。ひとまず (1) と同じように進めてみましょう。
$\alpha=3$，$\beta=3$ として，
$a_{n+2}-\alpha a_{n+1}=\beta(a_{n+1}-\alpha a_n)$
に代入すると，
(1) は代入する値を入れ替えてもう $1$ つの式を作りましたが，重解の場合，値を入れ替えても同じ式になってしまい，$2$ つ目の式を立てることができません。つまり，この①のみで $a_n$ を求めなくてはならないのです。(1) と同様に，【等比型】と見てまず $\left\{a_{n+1}-3a_n\right\}$ の一般項を求めましょう。
①より $\left\{a_{n+1}-3a_n\right\}$ は，
初項 $a_2-3a_1=1$，公比 $3$ の等比数列なので，
$a_{n+1}-3a_n$ $=$ $1$ $\cdot$ $3^{n-1}$ $=3^{n-1}$
$a_{n+1}=～$ の形にすると，
$a_{n+1}=3a_n+3^{n-1}$
となり，
【$○^n$ 型】$a_{n+1}=pa_n+q^n$
が姿を現しますね。
この型は，$q^{n+1}$ で割って，$\displaystyle\frac{a_n}{q^{n}}=b_n$ とおくでしたね。忘れている場合は以下の記事を確認しておこう。
$a_{n+1}=3a_n+3^{n-1}$【$○^n$ 型】
両辺を $3^{n+1}$ で割って
$\displaystyle\frac{a_{n+1}}{3^{n+1}}=\displaystyle\frac{3a_n}{3^{n+1}}+\displaystyle\frac{3^{n-1}}{3^{n+1}}$
整理して，
$\displaystyle\frac{a_{n+1}}{3^{n+1}}=\displaystyle\frac{a_n}{3^{n}}+\displaystyle\frac{1}{9}$
$\displaystyle\frac{a_n}{3^{n}}=b_n$ とおくと，
$b_{n+1}$ $=$ $b_n$ $+\displaystyle\frac{1}{9}$
これは，【等差型】なので，等差数列の一般項の公式により，瞬時に求めましょう。
等差数列の一般項は「初項」と「公差」が必要でした。
$\left\{b_n\right\}$ は，
初項 $b_1=\displaystyle\frac{a_1}{3^{1}}=\displaystyle\frac{1}{3}$，
公差 $\displaystyle\frac{1}{9}$ の等差数列より，
$b_n$ $=$ $\displaystyle\frac{1}{3}$ $+$ $(n-1)\cdot\displaystyle\frac{1}{9}$
$=\displaystyle\frac{1}{9}n+\displaystyle\frac{2}{9}$
$=(n+2)\cdot\displaystyle\frac{1}{9}$
あとは，$\displaystyle\frac{a_n}{3^{n}}=b_n$ から $a_n=3^nb_n$ として $a_n$ を求めましょう。
$a_n=3^n \cdot \left\{(n+2)\cdot\displaystyle\frac{1}{9}\right\}$
$=(n+2)\cdot3^{n-2}$ (答)
なんとか解けましたね。(1)が基本で，$2$ 式を連立して解きますが，最初の $2$ 次方程式の解が重解となる場合は，$1$ つの式から求めるため，面倒になります。ちなみに，(1) も (2) と同じ方法，すなわち $1$ つの式から求めることも可能ですが，$2$ 式作ることができる場合は，連立して求めた方が簡単なので，重解かそうでないかで違う手順で解くのが無難でしょう。
解説を入れながらだと長くなりますが，実際の解答はシンプルです。
上のことを理解しながら，自力で次の答案が書けるようにしっかり練習しましょう。
答案
(1) $a_{n+2}-a_{n+1}-6a_n=0$
$\begin{cases}a_{n+2}-3a_{n+1}\\ =-2(a_{n+1}-3a_n)\cdots\text{①}\\ \\a_{n+2}+2a_{n+1}\\ =3(a_{n+1}+2a_n)\cdots\text{②}\end{cases}$
$\begin{cases}a_2-3a_1=1\\a_2+2a_1=1\end{cases}$ [初項の確認]
より，
$\begin{cases}a_{n+1}-3a_n=(-2)^{n-1}･･･③\\ \\a_{n+1}+2a_n=3^{n-1} ･･･④\end{cases}$
④ $-$ ③とすると
$5a_n=3^{n-1}-(-2)^{n-1}$
よって，
$a_n=\displaystyle\frac{1}{5}\left\{3^{n-1}-(-2)^{n-1}\right\}$ (答)
(2) $a_{n+2}-6a_{n+1}+9a_n=0$
$a_{n+2}-3a_{n+1}$ $=$ $3$ $(a_{n+1}-3a_n)$･･･①
①より $\left\{a_{n+1}-3a_n\right\}$ は，
初項 $a_2-3a_1=1$，公比 $3$ の等比数列である。
よって，
$a_{n+1}-3a_n$ $=$ $1$ $･$ $3^{n-1}$ $=3^{n-1}$
したがって，
$a_{n+1}=3a_n+3^{n-1}$ 【$○^n$ 型】
両辺を $3^{n+1}$ で割って
$\displaystyle\frac{a_{n+1}}{3^{n+1}}=\displaystyle\frac{3a_n}{3^{n+1}}+\displaystyle\frac{3^{n-1}}{3^{n+1}}$
よって，
$\displaystyle\frac{a_{n+1}}{3^{n+1}}=\displaystyle\frac{a_n}{3^{n}}+\displaystyle\frac{1}{9}$
$\displaystyle\frac{a_n}{3^{n}}=b_n$ とおくと，
$b_{n+1}$ $=$ $b_n$ $+\displaystyle\frac{1}{9}$ 【等差型】
$\left\{b_n\right\}$ は，
初項 $b_1=\displaystyle\frac{a_1}{3^{1}}=\displaystyle\frac{1}{3}$，
公差 $\displaystyle\frac{1}{9}$ の等差数列より，
$b_n$ $=$ $\displaystyle\frac{1}{3}$ $+$ $(n-1)\cdot\displaystyle\frac{1}{9}$
$=\displaystyle\frac{1}{9}n+\displaystyle\frac{2}{9}$
$=(n+2)\cdot\displaystyle\frac{1}{9}$
$\displaystyle\frac{a_n}{3^{n}}=b_n$ より $a_n=3^nb_n$ であるから，
$a_n=(n+2)\cdot3^{n-2}$ (答)
【隣接３項間型】漸化式がこれで「解ける！」
【隣接３項間型】$a_{n+2}+pa_{n+1}+qa_n=0$
