- 目次
- 理解
- 事例
- コード
- まとめ
【理解】漸化式の解法を解説
基礎的な漸化式について
$a_{n+1} = a_n$【定数型】
→ $a_n=a_1$
[custom_content_widget post_id="38601"]
$a_{n+1} = a_n+d$【等差型】
→ $a_n=a_1 + (n-1)d$
[custom_content_widget post_id="38597"]
以上より, $\{a_n\}$ が等差数列と分かるので一般項の形を導くことができる.
$a_{n+1} = ra_n$【等比型】
→ $a_n=a_1r^{n-1}$
[custom_content_widget post_id="37270"]
以上より, $\{a_n\}$ が等比数列と分かるので一般項の形を導くことができる.
$a_{n+1} = a_n+f(n)$【階差型】
→ $\displaystyle a_n=a_1 + \sum_{k=1}^{n-1}f(k)$ $(n\geq 2)$
$b_n=f(n)$ が階差数列とすると分かりやすく考えられる。
[custom_content_widget post_id="41905"]
$a_{n+1} = g(n)a_n$【階比型】
→ $\displaystyle a_n=a_1 \times \prod_{k=1}^{n-1}g(k)$ $(n\geq 2)$
$b_n=g(n)$ が階比数列とすると分かりやすく考えられる。
[custom_content_widget post_id="41936"]
標準的な漸化式について
$a_{n+1} = pa_n+q$
※ $a_{n+1} - x = p(a_n-x)$ と変形して等比型の漸化式に帰着させる。
[custom_content_widget post_id="35985"]
$a_{n+1} = pa_n+r^n$
※ $\displaystyle b_n=\frac{a_n}{r^n}$ などと置く。
[custom_content_widget post_id="36441"]
$\displaystyle a_{n+1} = \frac{ra_n}{pa_n+1}$
※ $\displaystyle b_n=\frac{1}{a_n}$ などと置く。
[custom_content_widget post_id="36468"]
$\displaystyle a_{n+1} =ra_n+(pn+q)$
※ $b_n=a_{n+1}-a_n$（階差数列）を利用する。
[custom_content_widget post_id="36492"]
$\displaystyle a_{n+1} =ra_n+(pn+q)$
※ $b_n=a_n+(sn+t)$（一次式）を利用する。
[custom_content_widget post_id="36730"]
三項間漸化式（2階の漸化式）について
$a_{n+2} = pa_{n+1} + qa_n$
[custom_content_widget post_id="42258"]
$a_{n+2} = 2a_{n+1}-a_n$
$a_{n+2} = 2a_{n+1}-a_n$ $\Longleftrightarrow$ $a_{n+2} - a_{n+1} = a_{n+1}-a_n$.
[custom_content_widget post_id="38597"]
以上より, $\{a_n\}$ が等差数列と分かるので一般項の形を導くことができる.
$\displaystyle S_n$ を含む漸化式
※ $a_{n+1}=S_{n+1} - S_n$ を利用する。
[custom_content_widget post_id="36489"]
【事例】漸化式の具体例
$a_{n+2} = a_{n+1}+a_n$ ※フィボナッチ数列
[custom_content_widget post_id="36240"]
$a_{n+1} = (1+r)a_n+a$ ※複利法
[custom_content_widget post_id="36288"]
$a_{n+1} = 2a_n+1$ ※ハノイの塔🗼
［ゲームのルール］
ハノイの塔🗼を用意する。すべての円盤を他の杭に動かすことができればゲームクリア
- 円盤は1回に1枚ずつどれかの杭に移動させることができる
- 小さな円盤の上には大きな円盤をのせることはできない
- 補助として B を用いてもよい
$\vdots$
【数学としてゲーム】
$n$ 枚の円盤でゲームをクリアする最少手数を求めてください。
$\displaystyle a_{n+1} =\frac{1}{2}\left(a_n + \frac{x}{a_n}\right)$ ※平方根の値の近似
[custom_content_widget post_id="37783"]
$\mathbf{P}_{i, j}(t) = (1-t) \mathbf{P}_{i, j-1}(t) + t \mathbf{P}_{i+1, j-1}(t)$ ※ベジェ曲線
[custom_content_widget post_id="40912"]
$\{ c \in \mathbb{C}\mid \lim_{n \to \infty} |z_{n}|<\infty\}$, $z_{n+1} = z_n^2 +c$ ※マンデルブロ集合
[custom_content_widget post_id="42383"]
$a^n + b^n$ を基本対称式 $a+b$ と $ab$ で表す
[custom_content_widget post_id="38578"]
$a^n + b^n+c^n$ を基本対称式 $a+b+c$ と $ab+bc+ca$, $abc$ で表す
[custom_content_widget post_id="38659"]
【コード】Pythonで漸化式から数列を出力
$a_{n+1}=f(a_n)$ の形の漸化式から一般項の出力.append(seq[i-1]の式)
[custom_content_widget post_id="42191"]
$a_{n+2} = pa_{n+1} + qa_{n}$ の形の漸化式から一般項の出力.append(seq[i-1]とseq[i-2]の式)
たとえば、漸化式が $a_{n+2}=a_{n+1}+a_n$ である
[custom_content_widget post_id="36566"]
まとめノート
「数列の漸化式」とは
各項とそれ以前の項との関係を表す式のこと。
基本
漸化式の形から, どんな数列であるか判断し, 一般項を導出する.
A. 基礎的な漸化式
- $a_{n+1} =a_n$ ならば, 数列 $\{ a_n \}$ は定数列.
- $a_{n+1} = a_n + d$ ならば, 数列 $\{ a_n \}$ は公差 $d$ の等差数列.
- $a_{n+1} = r a_{n}$ ならば, 数列 $\{ a_n \}$ は公比 $r$ の等比数列.
- $a_{n+1} = a_n + f(n)$ ならば, 数列 $\{ a_n \}$ の階差数列が $\{ f(n) \}$.
- $a_{n+1} = g(n) a_n$ ならば, 数列 $\{ a_n \}$ の階比数列が $\{ g(n) \}$
B. 特性型の漸化式
- $a_{n+1} = pa_n + q$ のときは, $x=px+q$ の解 $\alpha$ を利用する.
- $a_{n+2} = pa_{n+1} + q a_n$ のときは, $x^2 = px + q$ の解 $\alpha$, $\beta$ を利用する.
ポイント解説
B(1)
与式は
$a_{n+1} - \alpha = p(a_n - \alpha)$
に変形できる。数列 $\{ a_n - \alpha \}_n$ が公比 $p$ の等比数列だと分かることを利用して導く。
B(2)
与式は次の２つの式に変形することができる：$$\begin{aligned}
a_{n+2} - \alpha a_{n+1} &= \beta (a_{n+1} - \alpha a_n) \\
a_{n+2} - \beta a_{n+1} &= \alpha (a_{n+1} - \beta a_n)
\end{aligned}$$ $\{ a_{n+1} - \alpha a_{n} \}_n$ と $\{ a_{n+1} - \beta a_{n} \}_n$ はそれぞれ等比数列と分かる。$$\begin{aligned}
a_{n+1} - \alpha a_n &= (a_2 - \alpha a_1) \cdot \beta^{n-1} \\
a_{n+1} - \beta a_n &= (a_2 - \beta a_1) \cdot \alpha^{n-1}
\end{aligned}$$この２式を連立して, $a_n$ の式を作ります。
