一般論

• 一般項を求めても、行列累乗でも計算量が変わらないこともある
  • 一般項にk乗の形が出てきたら、結局 log k の計算量がかかる。

漸化式一覧

参考: 漸化式の全パターン紹介 | おいしい数学

• 等差数列の漸化式 $x_{n+1} = x_n + d$
• 等比数列の漸化式 $x_{n+1} = rx_n$
• アフィン $x_{n+1} = a x_n + b$
• 連立漸化式 $x_{n+1} = a x_n + b y_n,\ y_{n+1} = c x_n + d y_n$
• 3項間漸化式 $x_{n+2} = ax_{n+1} + bx_n$
• 階差型 $x_{n+1} = x_n + f(n)$
• 指数型 $x_{n+1} = a x_n + b r^n$
• $x_{n+1} = a x_n + bn$
• $x_{n+1} = a x_n + bn^2$
• $x_{n+1} = a x_n + bnr^n$
• 階乗を含む漸化式
• $x_{n+1} = p{x_n}^q$
• $\displaystyle x_{n+1} = \frac{n+2}{n} x_n$
• $\displaystyle x_{n+1} = \frac{p x_n}{q x_n + r}$
• 一次分数変換 $\displaystyle x_{n+1} = \frac{px_n + q}{r x_n + s}$