漸化式
フィボナッチ数列の7つの性質(一般項・黄金比・互いに素)
フィボナッチ数列とは,1,1,2,3,5,8,13,21 のように,各項が「前の2つを足した値」になるような数列のこと。
この記事では, フィボナッチ数列の意味 を解説した後, フィボナッチ数列の美しい性質を7つ 紹介します。
カタラン数の意味と漸化式
で定義されるカタラン数は場合の数の問題で頻繁に登場する。
なお,カタラン数を表す は小文字,二項係数を表す は大文字です。
は二項係数の定義と簡単な計算で示すことができます。
数列の母関数の意味とその応用例
数列 に対して,その母関数を
と定義する。
数列に対する母関数の定義はいくつかありますが,上記の定義が一般的で,通常型母関数とも言います。
sinのn乗,cosのn乗の積分公式
の定積分は部分積分と漸化式を使って求めることができる。
乗の積分を求める際に部分積分を用いて漸化式を導く方法は頻出です。実際に定積分を求める解法を説明します。
また定積分を求める過程で三角関数の積分に関する一般的な公式( と の対称性)について説明します。
f(n)を含む二項間漸化式の2通りの解法
が多項式のとき二項間漸化式
を解く方法を2通り紹介します。2つ目の方法「一般項を予想する」というのが計算量が少ないのでオススメです!
三項間漸化式の3通りの解き方
三項間漸化式:
の3通りの解法と,それぞれのメリットデメリットを解説します。
- 特性方程式を用いた解法
- 答えを気合いで予想する
- 行列の 乗を求める方法
例題として, を解きます。
特性方程式の解が重解になる場合は最後に補足します。
漸化式を用いた関数方程式の解法
のみの関数方程式は漸化式を用いると解けることがある
このテクニックを用いる問題の出題頻度は高くありませんが,もし出題された場合に漸化式による解法を知らないと厳しいので一応知っておいた方がよいと思います。