漸化式を解く問題の中で，最も基礎的なタイプである $a_{n+1}=pa_n+q$ 型の解き方を３つ紹介します．
初項 $a$ と漸化式 $a_{n+1}=pa_n+q$ によって定まる数列 $\{a_n\}$ の一般項の求め方を考えてみましょう．ここで，$p,q$ は $n$ によらない定数です． 初項と，隣り合う $2$ 項の関係式 (隣接二項間漸化式) が与えられているので，数列 $\{a_n\}$ はただ一通りに決まります．
また，$p=1$ の場合は $\{a_n\}$ は等差数列になり，$q=0$ 場合は等比数列になります．したがってそのような特別な場合は一般項がすぐに求まるので，以下では $p \neq 1，q \neq 0$ として議論を進めます．
特に，ここでは以下の具体的な問題を解くことを例にして考えます．
問 次の条件によって定められる数列 $\{a_n\}$ の一般項を求めよ． $$a_1=4，a_{n+1}=2a_n-3$$
念のためですが，上の条件は，『$a_1=4$ であり，全ての自然数 $n=1,2,3,\cdots$ について，$a_{n+1}=2a_{n}-3$ が成り立つ』という意味です．
特性方程式とは，一言で言えば漸化式を解くためのひとつの道具です．漸化式 $a_{n+1}=pa_n+q$ についてはその特性方程式は $\alpha=p\alpha+q$ です．より一般的な漸化式に対しても特性方程式を考えることができますが，なぜそのような方程式を考えることで漸化式が解けるのかという原理を説明するには，やや高度な数学が必要になるのでここでは深入りしません．
解法
$a_{n+1}=2a_{n}-3$ の特性方程式は $\alpha=2\alpha-3$ です．この $2$ 式を辺々引くと， \begin{array}{ccc} &a_{n+1}&=2a_{n}-3 \\ -&\alpha&=2\alpha-3 \\ \hline &a_{n+1}-\alpha&=2(a_{n}-\alpha) \end{array} となって，定数項 $3$ が消えます．また，$\alpha=2\alpha-3$ を解くと，$\alpha=3$ なので， $$a_{n+1}-3=2(a_{n}-3)$$ です．ここで，$b_n=a_n-3$ とおくと， $$b_1=1，b_{n+1}=2b_{n}$$ です．つまり，数列 $\{b_n\}$ は初項 $1$，公比 $2$ の等比数列で，その一般項は $$b_n=2^{n-1}$$ よって，$a_n=b_n+3=2^{n-1}+3$ となります．
要するに，特性方程式を考えることにより，$a_{n+1}-3=2(a_{n}-3)$ という上手な式変形を見つけ出すことができます．そしてこの式はかたまりで見ると，等比数列の漸化式になっているから簡単に解けるということです．
検討
この記事で紹介する $3$ つの解法の中でこの解き方が最もスタンダードな方法です．慣れれば，$a_{n+1}=2a_n-3$ を見た瞬間に $a_{n+1}-3=2(a_{n}-3)$ という式変形が思いつくことでしょう．実践向きです．
漸化式 $a_{n+1}=2a_{n}-3$ はすべての自然数 $n=1,2,3,\cdots$ に対して成立する式でした．したがって当然，すべての然数 $n=1,2,3,\cdots$ に対して，添字をひとつずらした $$a_{n+2}=2a_{n+1}-3$$ というも成立します．
解法
漸化式 $$a_{n+1}=2a_n-3 \cdots ①$$ において，$n$ の代わりに $n+1$ とおくと $$a_{n+2}=2a_{n+1}-3 \cdots ②$$ ②ー①より， $$a_{n+2}-a_{n+1}=2(a_{n+1}-a_{n})$$ 数列 $\{a_n\}$ の階差数列を $\{b_n\}$ とすると，$b_n=a_{n+1}-a_{n}$ より， $$b_1=1，b_{n+1}=2b_{n}$$ つまり，数列 $\{b_n\}$ は初項 $1$，公比 $2$ の等比数列で，その一般項は $$b_n=2^{n-1}$$ よって，$a_n=b_n+3=2^{n-1}+3$ となります．
検討
特性方程式を用いる方法と似ていますね．邪魔な定数項を消して，かたまりで見るとより簡単な漸化式になるようにするという発想です．特に，添字の $n$ に何か別の文字式を代入してみるというアイデアは漸化式を解く問題に限らず，よく使います．
冒頭でも述べたように，今回の問題は，求めるべき数列がただひとつしかないことがあらかじめわかっています．よって，適当に探してきた数列が，$a_1=4，a_{n+1}=2a_n-3$ という条件を満たしていれば，それが答えであると言って良いのです．
解法
$$a_1=4，a_{n+1}=2a_{n}-3$$ において，$n=1,2,3,…$ と代入していくことにより， 数列 $\{a_n\}$ は， $$4，5，7，11，19，35，\cdots$$ となっていることがわかります．このことから， $$a_1=1+3$$ $$a_2=2+3$$ $$a_3=2^2+3$$ $$a_4=2^3+3$$ $$\vdots$$ となっていることに気づけば，$a_n=2^{n-1}+3$ となっているのではないかという予想が立ちます．この予想が本当に正しいかどうかを確かめるには，もとの漸化式にこの一般項を代入すればよいです．すなわち，$2a_{n}-3$ に，$a_n=2^{n-1}+3$ を代入して計算した結果が， $a_{n+1}=2^n+3$ となれば，予想が正しかったことになります．実際， $$2a_{n}-3=2(2^{n-1}+3)-3=2^n+3$$ となるので，予想は正しいです．よって，$a_n=b_n+3=2^{n-1}+3$ となります．
検討
$a_{n+1}=pa_n+q$ 型のように，その解き方がよく知られている問題については，わざわざ一般項を予想して解くというようなある種ギャンブル的な解き方はお勧めしません．しかし，この一般項を予想して，実際に漸化式に代入して確証を得るというアイデアは非常に重要です．全く見たこともないような漸化式を解く場合には有効な方法である場合が多いです．
$a_{n+1}=pa_n+q$ 型の漸化式によって定まる数列の解き方を $3$ 通り紹介しました．ここで紹介した解法のアイデアはその他の漸化式を解く上でもよく用いられる基本的なものです．また，多くの漸化式を解く問題が，式変形や変数変換などによって，結局は $a_{n+1}=pa_n+q$ 型の漸化式を解く問題に帰着されます．
