漸化式

    更新日時 2022/04/17

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

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

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

    攪乱順列の公式

    1,2,⋯ ,n1, 2,\cdots, n を並び替えてできる順列のうち，全ての i=1,2,⋯ ,ni=1, 2, \cdots, n に対して ii 番目が ii でないものの個数 ana_n は，以下の式で表される：

    an=n!∑k=2n(−1)kk!a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}

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

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

    フィボナッチ数列とは，1,1,2,3,5,8,13,21 のように，各項が「前の2つを足した値」になるような数列のこと。

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

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

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

    カタラン数

    cn=1n+12nCn=2nCn−2nCn−1c_n=\dfrac{1}{n+1}{}_{2n}\mathrm{C}_{n}={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}

    で定義されるカタラン数は場合の数の問題で頻繁に登場する。

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

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

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

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

    数列 ana_n に対して，その母関数を

    f(x)=∑k=0∞akxkf(x)=\displaystyle\sum_{k=0}^{\infty}a_kx^k

    と定義する。

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

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

    sinのn乗，cosのn乗の積分公式

    sin⁡nx,cos⁡nx\sin^n x, \cos^n x の定積分は部分積分と漸化式を使って求めることができる。

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

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

    → sinのn乗，cosのn乗の積分公式

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

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

    an+1=pan+f(n)a_{n+1}=pa_n+f(n)

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

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

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

    三項間漸化式：

    an+2=pan+1+qana_{n+2}=pa_{n+1}+qa_n

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

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

    例題として，a1=1,a2=1,an+2=5an+1−6ana_1=1,a_2=1,a_{n+2}=5a_{n+1}-6a_n を解きます。

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

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

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

    x,f(x),f(f(x)),f(f(f(x)))⋯x,f(x),f(f(x)),f(f(f(x)))\cdots のみの関数方程式は漸化式を用いると解けることがある

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

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

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

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

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

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

    漸化式で表される数列の極限を求めるタイプの入試問題は頻出です。問題の背景にはバナッハの不動点定理と呼ばれる素敵な定理があります。

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

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

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

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

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

    この記事の編集者
    マスオ

    高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！

      人気記事