(一次式)/(一次式)型漸化式の解法とその裏側
例題
$${a_1=1，a_n=\dfrac{2a_{n-1}+1}{3a_{n-1}+4}(n=2,3,4\cdots)}$$を満たす数列$${\{a_n\}}$$の一般項を求めよ．
解答
$${b_n=\dfrac{3a_n-1}{a_n+1}}$$とおいて数列$${\{b_n\}}$$の漸化式を求めると，
$$
\begin{array}{}b_n &=& \dfrac{3\cdot\dfrac{2a_{n-1}+1}{3a_{n-1}+4}-1}{\dfrac{2a_{n-1}+1}{3a_{n-1}+4}+1}\\
\\
&=&\dfrac{1}{5}\cdot\dfrac{3a_{n-1}-1}{a_{n-1}+1}=\dfrac{1}{5}b_{n-1}\end{array}(n=2,3,4\cdots)
$$
よって，数列$${\{b_n\}}$$は公比$${\dfrac{1}{5}}$$の等比数列であり，初項は$${b_1=1}$$．したがって，$${b_n=\left(\dfrac{1}{5}\right)^{n-1}}$$である．よって，
$$
\dfrac{3a_n-1}{a_n+1}=\left(\dfrac{1}{5}\right)^n(n=1,2,3\cdots)\\\\\Leftrightarrow a_n=\dfrac{5^{n-1}+1}{3\cdot5^{n-1}-1}(n=1,2,3\cdots)
$$
ツッコミどころ
まあ，まずツッコミたいのは
「$${b_n=\dfrac{3a_n-1}{a_n+1}}$$よ，お前は何者だ！」
ってことである．確かに，新たに定義したこの数列$${\{b_n\}}$$を媒介することで数列$${\{a_n\}}$$の一般項が分かる．が，じゃあお前はどっからきたんだよ．
私が授業の参考にしている長岡亮介先生の総合的研究数学II+B（旺文社）には，実は行列やら固有値やらが裏にあると記載されている．
大学以降の数学が入ってくるので，生徒にはどうせ話はできないわけだが，なんとなくこのままこの問題を流すと負けた気がするので（何に？），久しぶりに本棚から線形代数の本を引っ張り出して考えてみました．もちろん我らが対馬龍司先生の線形代数学講義（共立出版）．以下，その説明です．
裏で起こってること
一般化して漸化式$${a_n=\dfrac{pa_{n-1}+q}{ra_{n-1}+s} (p,q,r,s\in\mathbb{R})}$$で表される数列$${\{a_n\}}$$の一般項を求める．
この漸化式を解くことは，連立漸化式
$$
\left\{\begin{array}{}x_n=px_{n-1}+qy_{n-1}\\\\y_n=rx_{n-1}+sy_{n-1}\end{array}\right.
$$
を解くことと同じです($${a_n=\dfrac{x_n}{y_n}}$$と定義すれば元の漸化式に戻る)．
まずは，行列$${\bm{A}=\begin{pmatrix}p&q\\r&s\end{pmatrix}}$$の固有値と固有ベクトルを求めます．行列Aの固有方程式
$$
\begin{array}{ll}0&=\left|\begin{pmatrix}p&q\\r&s\end{pmatrix}-\lambda\bm{I}\right|\\\\&=\lambda^2-(p+s)\lambda+ps-qr\end{array}
$$
の解$${\lambda_1,\lambda_2}$$が固有値です．それぞれの固有値の固有ベクトルを$${\bm{v}_1,\bm{v}_2}$$として$${\bm{P}=(\bm{v}_1\bm{v}_2)}$$とおいておく．これより，
$$
\begin{array}{ll}\bm{A}\bm{P}=(\bm{A}\bm{v}_1 \bm{A}\bm{v}_2)=(\lambda_1\bm{v}_1 \lambda_2\bm{v}_2)=\bm{P}\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}\\\Longleftrightarrow\bm{P}^{-1}\bm{A}=\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}\bm{P}^{-1}\end{array}
$$
となるので，件の連立漸化式の両辺の左から行列$${\bm{P}^{-1}}$$をかければ，
$$
\bm{P}^{-1}\begin{pmatrix}x_n\\y_n\end{pmatrix}=\bm{P}^{-1}\bm{A}\begin{pmatrix}x_{n-1}\\y_{n-1}\end{pmatrix}=\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}\bm{P}^{-1}\begin{pmatrix}x_{n-1}\\y_{n-1}\end{pmatrix}
$$
最後に，$${\begin{pmatrix}X_n\\Y_n\end{pmatrix}=\bm{P}^{-1}\begin{pmatrix}x_n\\y_n\end{pmatrix}}$$
とおけば，連立漸化式
$$
\begin{pmatrix}X_n\\Y_n\end{pmatrix}=\begin{pmatrix}\lambda_1&0\\0&\lambda_2\end{pmatrix}\begin{pmatrix}X_{n-1}\\Y_{n-1}\end{pmatrix}
$$
が得られます．こいつが謎の数列$${\{b_n\}}$$の正体だ！
最後に，上記の例題で具体的にやってみます．$${\bm{A}=\begin{pmatrix}2&1\\3&4\end{pmatrix}}$$なので，各量は以下の通り．
$$
\lambda_1=1,\lambda_2=5,\bm{v}_1=\begin{pmatrix}1\\-1\end{pmatrix},\bm{v}_2=\begin{pmatrix}1\\3\end{pmatrix},\bm{P}^{-1}=\dfrac{1}{4}\begin{pmatrix}3&-1\\1&1\end{pmatrix}
$$
$${a_n=\dfrac{x_n}{y_n},b_n=\dfrac{X_n}{Y_n}}$$とおけば，謎の数列$${\{b_n\}}$$とその漸化式は
$$
\begin{array}{l}\begin{pmatrix}X_n\\Y_n\end{pmatrix}=\bm{P}^{-1}\begin{pmatrix}x_n\\y_n\end{pmatrix}\Leftrightarrow\begin{pmatrix}X_n\\Y_n\end{pmatrix}=\dfrac{1}{4}\begin{pmatrix}3x_n-y_n\\x_n+y_n\end{pmatrix}\Leftrightarrow b_n=\dfrac{3a_n-1}{a_n+1}\\\\ \begin{pmatrix}X_n\\Y_n\end{pmatrix}=\begin{pmatrix}1&0\\0&5\end{pmatrix}\begin{pmatrix}X_{n-1}\\Y_{n-1}\end{pmatrix}\Leftrightarrow b_n=\dfrac{1}{5}b_{n-1}\end{array}
$$
と導出されるわけです．あー終わった．