漸化式

漸化式（ぜんかしき）についてわかりやすく解説します。漸化式の意味から，解き方12パターンをすべて紹介します。

→ 漸化式の解き方12パターンと応用例まとめ

→ 攪乱順列（完全順列）の個数を求める公式

この記事では， フィボナッチ数列の意味 を解説した後， フィボナッチ数列の美しい性質を8つ 紹介します。

→ フィボナッチ数列の8つの性質（一般項・黄金比・互いに素）

なお，カタラン数を表す $c$ は小文字，二項係数を表す $C$ は大文字です。

$\dfrac{1}{n+1}{}_{2n}\mathrm{C}_{n}={}_{2n}\mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}$ は二項係数の定義と簡単な計算で示すことができます。

→ カタラン数の意味と漸化式

数列に対する母関数の定義はいくつかありますが，上記の定義が一般的で，通常型母関数とも言います。

→ 数列の母関数の意味とその応用例

$n$ 乗の積分を求める際に部分積分を用いて漸化式を導く方法は頻出です。実際に定積分を求める解法を説明します。

また定積分を求める過程で三角関数の積分に関する一般的な公式（$\sin$ と $\cos$ の対称性）について説明します。

→ ウォリス積分～sinのn乗，cosのn乗の積分公式

$f(n)$ が多項式のとき二項間漸化式

$a_{n+1}=pa_n+f(n)$

を解く方法を2通り紹介します。2つ目の方法「一般項を予想する」というのが計算量が少ないのでオススメです！

→f(n）を含む二項間漸化式の２通りの解法

三項間漸化式：

$a_{n+2}=pa_{n+1}+qa_n$

の3通りの解法と，それぞれのメリットデメリットを解説します。

1. 特性方程式を用いた解法
2. 答えを気合いで予想する
3. 行列の $n$ 乗を求める方法

例題として，$a_1=1,a_2=1,a_{n+2}=5a_{n+1}-6a_n$ を解きます。

特性方程式の解が重解になる場合は最後に補足します。

→ 三項間漸化式の3通りの解き方

このテクニックを用いる問題の出題頻度は高くありませんが，もし出題された場合に漸化式による解法を知らないと厳しいので一応知っておいた方がよいと思います。

→ 漸化式を用いた関数方程式の解法

一般項を求めるのが難しそうな漸化式を，三角関数を用いて求めることができる例を2つ紹介します。

→ ロジスティック写像と漸化式

→ 漸化式で表される数列の極限

確率漸化式は「漸化式を利用して確率を求める」ような問題です。

この記事では，例題3問を通じて確率漸化式の解き方・考え方を説明します。

→ 確率漸化式の解き方と例題