(注意) 【～型】はパターンを意識するために勝手に呼んでるので，答案に書かないように。
ここでは，$n$ の$k$ 次式，特に $1$ 次式と $2$ 次式を含む漸化式の解法について扱います。出題頻度が高く，誘導なしで出題されることもあるため，自力で解く経験を積んでおきたいパターンです。難易度はやや高いので，繰り返し解いて確実に解けるようにしましょう。
【 $k$ 次式型】$a_{n+1}=pa_n+(n\text{ の }k\text{ 次式})$
(例)
$a_{n+1}=2a_n$ $+3n+1$ [$1$ 次式型]
$a_{n+1}=3a_n$ $+3n^2+n$ [$2$ 次式型]
(ほぼ[1次式]か[2次式]で出題されます)
【 $k$ 次式型】の解法
この型の解法は２パターンあります。
[1] {$a_n+$ $(n\text{ の }k\text{ 次式})$} が等比数列となるように変形
具体的に[1次式型]，[2次式型]のとき
{ $a_n+$ $\alpha n+\beta$ } が等比数列
{ $a_n+$ $\alpha n^2+\beta n+\gamma$ } が等比数列
となるように変形。
[2] $k$ 回階差をとる
誘導がある場合もあるので，どちらもできるようにしておくのが良い。誘導がない場合は，[1] の方が簡単に解けるので推奨（ただし，慣れが必要です）。
ちなみに，$p=1$ のときは【階差型】です。
(例) $a_{n+1}=a_n$ $+$ $n^2-1$
これは，$\left\{n^2-1\right\}$ が階差数列であることを用いて解けますね。
【$2$ 次式型】と見てはいけません！
【1次式型】【2次式型】の問題と解答
問題
(1) $a_1=1$，$a_{n+1}=2a_n+2n+1$
(2) $a_1=0$，$a_{n+1}=2a_n+n^2$
【東海大(医)(改)】
解説（解法[1]等比型に帰着させる）
まず，解法[1]で解いてみましょう。
(1) $a_{n+1}=2a_n$+ $2n+1$
$2n+1$ は 1次式であるから，まず【1次式型】と見なしましょう。
{$a_n+$ $(n\text{ の }1\text{ 次式})$}
すなわち {$a_n+$ $\alpha n+\beta$} が，
等比数列となるようになんとかして変形することを目指します。
以下のように考えて，理解しつつパターン化しましょう。
$2$ の部分は $a_n$ の係数をそのままもってくる(それ以外にすると，もとの漸化式と一致しなくなる）。式を暗記するのでなく，まず右辺を考えて，等比数列となるためには左辺がどうなれば良いかを考えて書くことが重要です。つまり，暗記すべき部分は $a_n+\alpha n+\beta$ だけで，左辺は「次の項となるように，$n$ を $n+1$ に書き換えたものを書く」と理解しておきましょう。さらに言うと，$a_n+$ $\alpha n+\beta$ の部分も，$a_n+$ $(n\text{ の }1\text{ 次式})$ で $n$ の $1$ 次式を $\alpha n+\beta$ と書いているだけと理解していれば，丸暗記していなくても書けますね。
ここまでは前置きで，今回の問題は，$$a_{n+1}+\alpha (n+1)+\beta=2(a_n+\alpha n+\beta)$$この式を書くことがスタート！
これがもとの漸化式と一致するように，$\alpha$，$\beta$ を定めます。
まず，もとの漸化式と係数比較するために，「$a_{n+1}=～$」の形に整理します。
$a_{n+1}=2a_n+$$\alpha$$ n+($$-\alpha+\beta$$)$
もとの漸化式
$a_{n+1}=2a_n$$+2$$n$$+1$
と係数を比較すると，
$\alpha=2$
$-\alpha+\beta=1$
これを解いて，$\alpha=2$，$\beta=3$
$\alpha$，$\beta$ を，スタートの式$$a_{n+1}+\alpha (n+1)+\beta=2(a_n+\alpha n+\beta)$$に代入すれば，
$a_{n+1}+2(n+1)-1$ $=$ $2$$(a_n+2n-1)$
となり，$a_n+2n-1$ をひとかたまりと見れば，$\left\{a_n+2n-1\right\}$ は公比 $2$ の等比数列と読みとれます（これができるように $\alpha$，$\beta$ を定めたのである）。初項は $n=1$ を代入したものなので $a_1+2\cdot1+3$ です。
よって，数列 $\left\{a_n+2n+3\right\}$ は，
初項 $a_1+2\cdot1+3=6$，公比 $2$ の等比数列より，
$a_n+2n+3$ $=$ $6$ $\cdot$ $2^{n-1}$ $=3\cdot2^n$
移項して，
$a_n=3\cdot2^n-2n-3$ (答)
(2) $a_{n+1}=2a_n+$ $n^2$
【$2$次式型】であるため，
$\left\{a_n+\alpha n^2+\beta n+\gamma\right\}$ が等比数列となるように変形するのが目標です。
よって，今回の問題は，
$a_{n+1}+\alpha(n+1)^2+\beta (n+1)+\gamma$
$=2(a_n+\alpha n^2+\beta n+\gamma)$
という式を書くことがスタート！
これがもとの漸化式と一致するように，$\alpha$，$\beta$，$\gamma$ を定めます。この式については，やはり暗記ではなく以下のように考えて書き出せるようにしましょう。（(1) と同じです)
(1)同様，整理してもとの漸化式と係数を比較します。
やや煩雑なので，慎重に計算しましょう。
$a_{n+1}=2a_n+$$\alpha$$ n^2+($$-2\alpha+\beta$$)n+($$-\alpha-\beta+\gamma$$)$
もとの漸化式
$a_{n+1}=2a_n+$$1$$n^2+$$0$$n+$$0$
と係数を比較して，
$\alpha=1$，
$-2\alpha+\beta=0$，
$-\alpha-\beta+\gamma=0$
これを解いて，$\alpha=1$，$\beta=2$，$\gamma=3$
求めた $\alpha$，$\beta$，$\gamma$ をスタートの式
$a_{n+1}+\alpha(n+1)^2+\beta (n+1)+\gamma$
$=2(a_n+\alpha n^2+\beta n+\gamma)$
に代入して，
$a_{n+1}+(n+1)^2+2(n+1)+3$
$=$ $2$$(a_n+n^2+2n+3)$ 【等比型】
を得ます。
$\left\{a_n+n^2+2n+3\right\}$ は，公比 $2$ の等比数列と見なすことができて，初項は $n=1$ を代入して $a_1+1^2+2\cdot1+3=6$ となるので，一般項 $a_n+n^2+2n+3$ が求められますね。
$\left\{a_n+n^2+2n+3\right\}$ は，
初項 $6$，公比 $2$ の等比数列より，
$a_n+2n+3$ $=$ $6$ $\cdot$ $2^{n-1}$ $=3\cdot2^n$
移項して，
$a_n=3\cdot2^{n}-n^2-2n-3$ (答)
解法[1]は，スタートの式の書き方さえ知識として覚えておけば，そこまで複雑な計算をせずに漸化式を解くことができます。もちろん，解法を理解していればの話です。【等比型】と見なして解くというのは，様々な場面で使います。何度も繰り返してしっかり理解しておきましょう。
答案（解法[1]等比型に帰着させる）
(1)
$a_{n+1}=2a_n$ $+2n+1$ [$1$次式型]
$a_{n+1}+\alpha(n+1)+\beta$
$=2(a_n+\alpha n+\beta)$ ･･･①
とおく。
整理して
$a_{n+1}=2a_n+\alpha n+(-\alpha+\beta)$
[もとの漸化式と比べるために「$a_{n+1}=～$」 とした]
もとの漸化式と係数を比較して，
$\begin{cases}\alpha=2\\-\alpha+\beta=1 \end{cases}$
これを解いて，
$\alpha=2$，$\beta=3$
これを①に代入して
$a_{n+1}+2(n+1)+3=$ $2$$(a_n+2n+3)$
よって，$\left\{a_n+2n+3\right\}$ は，
初項 $a_1+2\cdot1+3=6$，
公比 $2$ の等比数列より，
$a_n+2n+3$ $=$ $6$$\cdot$$2^{n-1}$ $=3\cdot2^n$
よって，
$a_n=3\cdot2^n-2n-3$ (答)
(2)
$a_{n+1}=2a_n+$ $n^2$ 【$2次式型$】
$a_{n+1}+\alpha(n+1)^2+\beta (n+1)+\gamma$
$=2(a_n+\alpha n^2+\beta n+\gamma)$ ･･･②
とおく。
整理して，
$a_{n+1}=2a_n+\alpha n^2$
$+(-2\alpha+\beta)n+(-\alpha-\beta+\gamma)$
もとの漸化式と，係数を比較して
$\begin{cases}\alpha=1\\-2\alpha+\beta=0\\-\alpha-\beta+\gamma=0 \end{cases}$
これを解いて
$\alpha=1$，$\beta=2$，$\gamma=3$
②に代入して
$a_{n+1}+(n+1)^2+2(n+1)+3$
$=$ $2$$(a_n+n^2+2n+3)$
よって，$\left\{a_n+n^2+2n+3\right\}$ は，
初項 $a_1+1^2+2\cdot1+3=6$，
公比 $2$ の等比数列より，
$a_n+n^2+2n+3$$=$$6$ $\cdot$ $2^{n-1}$$=3\cdot2^{n}$
よって，
$a_n=3\cdot2^{n}-n^2-2n-3$ (答)
別解の解説（解法[2]階差をとる）
次に，解法[2]で解いてみます。誘導された場合を除いて解法[2]を選択する理由はないため，何をしているか理解できれば十分です。
(1) $a_{n+1}=2a_n$ $+2n+1$
【1次式型】なので階差(隣り合う項の差)を 1 回とって考えます。
つまり， $a_{n+2}-a_{n+1}$ を計算します。
$a_{n+1}=2a_n$ $+2n+1$
$a_{n+2}=2a_{n+1}$ $+2(n+1)+1$ より
$a_{n+2}=2a_{n+1}+2n+3$ であるから，
$a_{n+2}-a_{n+1}$
$=$ $(2a_{n+1}+2n+3)$ $-$ $(2a_n$ $+2n+1)$
整理して，
$a_{n+2}-a_{n+1}$$=2$$(a_{n+1}-a_{n})$ $+2$
となります。
$a_{n+1}-a_{n}=b_n$ とおくと，
$b_{n+1}$ $=$ $2$$b_n$ $+$ $2$
となります。
解法[2]への誘導形式の場合「$a_{n+1}-a_{n}=b_n$ とおいて，$b_{n+1}$ を $b_n$ を用いて表せ」と問われるので，この式を答えることになりますね。
さて，$b_{n+1}$ $=$ $2$$b_n$ $+$ $2$ を見てどう解くかすぐに答えられますか？
即答できないとダメですよ？
【特殊解型】$a_{n+1}=pa_n+q$
なので，特殊解 $\alpha$ を求めて$\left\{b_n-\alpha \right\}$ の【等比型】で解く！ですね。特殊解型は漸化式最重要パターンです。怪しい人は確認しておきましょう。
初項 $b_1$ が必要になるため，求めておきましょう。
$b_1=a_2-a_1$ なので，まず $a_2$ を求める必要がありますね。
もとの漸化式 $a_{n+1}=2a_n+2n+1$ に $n=1$ を代入すれば，$a_2$ は求まります。
$a_2=2a_1+2\cdot1+1=2+2+1=5$
ですね。右辺に $n=2$ を代入しないように注意してください。代入しているのは $n=1$ です。
よって，$b_1=a_2-a_1=5-1=4$ です。
したがって，
$b_1=4$，$b_{n+1}$ $=$ $2$$b_n$ $+$ $2$【特殊解型】
から $b_n$ を求めましょう。
$\alpha=2\alpha+2$ を解くと $\alpha=-2$ より
$b_{n+1}+2=2(b_n+2)$
と変形できます。
よって，$\left\{b_n+2\right\}$ は
初項 $b_1+2=6$，公比 $2$ の等比数列より，
$b_n+2$ $=$ $6$ $\cdot$ $2^{n-1}$ $=$ $3\cdot 2^n$
$2$ を移項して，$b_n=3\cdot2^n-2$
ここで，$a_{n+1}=a_n$ $+$ $b_n$ より
$a_{n+1}=a_n$ $+$ $3\cdot2^n-2$
これも，見てすぐに気づかないとダメですよ？
【階差型】$a_{n+1}=a_n$ $+$ $(n\text{ の式})$
ですね。これは，階差数列から一般項を求める公式により瞬時に求められる型でしたね。
$a_{n+1}-a_{n}=b_n$ とおいた時点で，$\left\{b_n\right\}$ が階差数列になっていることを意識しておきましょう。
$n≧2$ のとき
$a_n=a_1+$ $\displaystyle\sum_{k=1}^{n-1}{(3\cdot2^k-2)}$
$\displaystyle\sum_{k=1}^{n-1}{3\cdot2^k}$ は，
初項 $6$，公比 $2$，項数 $n-1$ の等比数列の和として計算して，
$=1+6\cdot\displaystyle\frac{2^{n-1}-1}{2-1}-2(n-1)$
$=3\cdot2^n-2n-3$
$n=1$ のとき $a_1=3\cdot2-2\cdot1-3=1$
これは $n=1$ のときも成り立つ。
よって，
$a_n=3\cdot2^n-2n-3$ (答)
はい，できました。解法[1]と比べると面倒ですね。
次に (2) についてですが，前提として $2$ 次以上の場合は解法[2]を選択すべきではありません。もし，解法[2]に誘導される場合は，仕掛けがあると思ってください。その仕掛けというのは「前問の結果が使える」ということです（東海大(医)の本来の問題は，解法[2]へ誘導した出題となっています)。とは言え，珍しいケースであるため，余力がある人だけが取り組みましょう。
実際の解答については，次の答案の項目を確認してください。
別解の答案（解法[2]階差をとる）
(1)
$a_{n+1}=2a_n$ $+2n+1$ より
$a_{n+2}=2a_{n+1}$ $+2(n+1)+1$
$a_{n+2}=2a_{n+1}+2n+3$
$a_{n+2}$ $-$ $a_{n+1}$ (階差) を計算すると
$a_{n+2}$ $-$ $a_{n+1}$
$=$ $(2a_{n+1}+2n+3)$ $-$ $(2a_n$ $+2n+1)$
よって，
$a_{n+2}-a_{n+1}$$=2$$(a_{n+1}-a_{n})$ $+2$
$a_{n+1}-a_n=b_n$ とおくと
$b_{n+1}=2b_n+2$ 【特殊解型】
[$\alpha=2\alpha+2$ を解くと $\alpha=-2$]
$b_{n+1}+2=2(b_n+2)$
ここで，$a_2=2a_1+2\cdot1+1=5$ であるから，
$b_1=5-1=4$
よって $\left\{b_n+2\right\}$ は，
初項 $b_1+2=6$，公比 $2$ の等比数列である。
したがって，
$b_n+2=6\cdot2^{n-1}=3\cdot2^n$
∴ $b_n=3\cdot2^n-2$
∴$a_{n+1}-a_n=3\cdot2^n-2$ [階差型]
よって，$n≧2$ のとき
$a_n=a_1+$ $\displaystyle\sum_{k=1}^{n-1}{b_k}$
$=1+$ $\displaystyle\sum_{k=1}^{n-1}{(3\cdot2^k-2)}$
$=1+6\cdot\displaystyle\frac{2^{n-1}-1}{2-1}-2(n-1)$
$=3\cdot2^n-2n-3$
これは $n=1$ のときも成り立つ。
よって，
$a_n=3\cdot2^n-2n-3$ (答)
$a_{n+1}=2a_n+n^2$
$a_{n+2}=2a_{n+1}+(n+1)^2$
$=2a_{n+1}+n^2+2n+1$
$a_{n+2}-a_{n+1}$ [階差(1回目)]
$=(2a_{n+1}+n^2+2n+1)-(2a_n+n^2)$
$=2$$(a_{n+1}-a_{n})$$+2n+1$
$a_{n+1}-a_{n}=b_n$ とおくと，
$b_{n+1}=2b_n+2n+1$ 【$1次式型$】
[本来は $b_{n+2}-b_{n+1}$ [階差(2回目)] をとることによって【特殊解型】に帰着させて解くが…]
ここで，$a_2=2a_1+1^2=1$ より
$b_1=a_2-a_1=1-0=1$
よって，
$b_1=1$，$b_{n+1}=2b_n+2n+1$
となり，$\left\{b_n\right\}$ は (1) の $\left\{a_n\right\}$ と一致する。
したがって，
$b_n=3\cdot2^n-2n-3$
よって，$n≧2$ のとき
$a_n=a_1+$ $\displaystyle\sum_{k=1}^{n-1}{b_k}$
$=0+$ $\displaystyle\sum_{k=1}^{n-1}{(3･2^k-2k-3)}$
$=6\cdot\displaystyle\frac{2^{n-1}-1}{2-1}$
$-2\cdot\displaystyle\frac{1}{2}(n-1)n-3(n-1)$
$=3\cdot2^{n}-n^2-2n-3$
これは $n=1$ のときも成り立つ。
よって，
$a_n=3\cdot2^{n}-n^2-2n-3$ (答)
(参考) (1) の結果を利用しない場合
$b_{n+1}=2b_n+2n+1$ 【$1$ 次式型】
$b_{n+2}-b_{n+1}$ [階差(2回目)]
$=2b_{n+1}+2(n+1)+1-(2b_n+2n+1)$
$=2(b_{n+1}-b_{n})+2$
$b_{n+1}-b_{n}=c_n$ とおくと
$c_{n+1}=2c_n+2$ 【特殊解型】
$b_2=2b_1+2\cdot1+1=5$ より
$c_1=b_2-b_1=5-1=4$
$c_n$ を求め，階差数列から一般項を求める公式により $b_n$ を求める。
さらに，階差数列から一般項を求める公式により $a_n$ を求める。
（非常にメンドウ）
$n$ の1次式や2次式を含む漸化式がこれで「解ける！」
【 $k$ 次式型】$a_{n+1}=pa_n+(n\text{ の }k\text{ 次式})$
