変形階差型漸化式

階差型漸化式 $a_{n+1}=a_n+f(n)$ と似ているが， $a_n$ の前に係数 $p(p\neq1)$ がかかった形，つまり

\[a_{n+1}=pa_n+f(n)\]

という形をしている漸化式の解法について考えてみよう．

このようなタイプの漸化式は $f(n)$ の形により，解法を分類しておくのがよい．

以下，次の2タイプに分けて考えてみよう．

\begin{cases} f(n)=r^n&(指数タイプ)\\ f(n)=n^k\quad(k\in\text{N})&(k次式タイプ) \end{cases}