漸化式って何？数学的な定義は？必ず一般項は存在するの？
はじめに
どうも.
突然ですが, 以下の式は漸化式でしょうか？
\begin{equation}
a_{n+1} = a_n + 3
\end{equation}
これはどう見たって漸化式ですね.
続いて, 以下の式は漸化式でしょうか？
\begin{equation}
a_{n+1} = a_n + 2n - 1
\end{equation}
これもまぁ…, $n$の値によって漸化式そのものも変わりますが, 漸化式と言えるでしょう.
他にも, 以下の式は漸化式でしょうか？
\begin{equation}
a_{n+2} = a_{n+1} + a_n
\end{equation}
これは有名なFibonacci数列がみたす, れっきとした漸化式ですね.
最後に, 以下の式は漸化式でしょうか？
\begin{equation}
a_{n+1} = \sum_{i=0}^{n}a_i + n
\end{equation}
これも漸化式と言えるでしょうね.
我々は, 具体的な式を見たときに, それが「漸化式であるかどうか」を判断できます. しかしながら, 「漸化式とは何か？」と言われると少し返答に戸惑うのではないでしょうか？「前の項と項番号から値が決まる関係式」のように言葉では説明できるかもしれませんが, 漸化式の「数学的な定義」とは一体何なのでしょうか？
そこで, ここでは具体例を踏まえて漸化式を「定義」し, 初項と漸化式が与えられたとき, 必ず一意的な一般項をもつことを示していきましょう.
漸化式を定義しよう
漸化式を定義する上で, まず我々が「漸化式だと認識できるもの」をいくつか見ていき, それを一般化することを考えます. 前章で挙げた4つの例を元に, 漸化式を定義していきましょう.
用語や記号の定義
漸化式を定義する前に, 以降用いる用語や記号を定義します.
集合$X, Y$に対して, 集合$Y^X$を,
\begin{equation}
Y^X := \{f \mid f : X \to Y \}
\end{equation}
と定める. すなわち, $Y^X$とは, $X$から$Y$への写像全体の集合であり, 配置集合と呼ぶ.
$A$を非空集合とする. $f$が$A$上の点列であるとは, $f \in A^{\mathbb{N}_0}$であることを言う. ただし, $\mathbb{N}_0 := \{0\} \cup \mathbb{N}$である.
$f \in A^{\mathbb{N}_0}$が各$n \in \mathbb{N}_0$に対し, $f(n) = a_n$をみたすとき, $f$を$(a_n)_n$や$(a_m)_m$等とも書く.
点列の数学的な定義は写像なので, ここでもその立場を取ります. 添え字集合として$0$を含めているのは, 後に用いる自然数論の定理の都合なので, 気にしなくて大丈夫です. 以降, 点列の記号としては, 見やすさを重視して$(a_n)_n$や$(a_m)_m$等を用いますが, あくまで写像であることには注意してください.
漸化式の定義は写像？
ところで, 自然数論には次の定理があります. ここでは証明は省きます.
$A$を非空集合とする. このとき, 任意に与えられた$a \in A$と$\varphi \in A^A$に対して, ある一意的な点列$(a_n)_n \in A^{\N_0}$が存在して,
\begin{equation}
a_0 = a, \quad a_{n+1} = \varphi(a_n) \; (\forall n \in \N_0)
\end{equation}
をみたす.
この定理を噛み砕いて見てみると, $\varphi$が漸化式を表しているように見えてきます. 例えば, $A=\mathbb{R},\ a=1,\, \varphi : \mathbb{R} \ni x \mapsto x+3 \in \mathbb{R}$として上の定理を適用すると, ある一意的な$\mathbb{R}$上の点列$(a_n)_n$が存在して,
\begin{equation}
a_0 = 1, \quad a_{n+1} = a_n + 3 \; (\forall n \in \N_0)
\end{equation}
をみたすことがわかります. これは上で挙げた最初の漸化式の例を, $\varphi$が担っているということを表しています. この定理を元に, 写像で漸化式を表現することを考えてみましょう.
具体例から定義を考察
ここでは前章の漸化式の例を表す写像を考察してみます. 点列は$\R$上のものとします.
最初に挙げた漸化式の例
\begin{equation}
a_{n+1} = a_{n} + 3
\end{equation}
を表現する写像は, 前節で見たように$\varphi_1 : \mathbb{R} \ni x \mapsto x + 3\in \mathbb{R}$でした.
続いて挙げた漸化式の例,
\begin{equation}
a_{n+1} = a_n + 2n - 1
\end{equation}
はどうでしょうか？実のところ, この漸化式はいかなる$\R^\R$の元でも表現することができません(よければ考えてみてください). 先ほどとの違いは漸化式の中に項番号$n$が表れていることで, これを解消するためにちょっとした工夫をします. 具体的には,
\begin{equation}
\varphi_2 : \N_0 \times \R \ni (n, x) \mapsto x + 2n -1 \in \R
\end{equation}
として, 写像の始域に項番号の成分を加えることで, $\varphi_2$は漸化式を表していると言えそうです.
他に挙げたFibonacci数列の漸化式
\begin{equation}
a_{n+2} = a_{n+1} + a_{n}
\end{equation}
も, 明らかに$\R^\R$の元では表現できませんが, これの解消は簡単で,
\begin{equation}
\varphi_3 : \R^2 \ni (x, y) \mapsto y + x \in \R
\end{equation}
とすれば, $\varphi_3$は漸化式を表していると言えるでしょう.
ここまでの議論を踏まえて, ふと, 「写像$\varphi$が集合$A$上の漸化式である」とは, 「ある$k \in \N$が存在して, $\varphi : \N_0 \times A^k \to A$をみたすことである」と, 定義できそうに思えます. 項番号を成分に加える必要がない漸化式もありますが, その場合はその成分に関して定数であるような写像を選べばいいので問題ないですね. $k$は, 点列の決定に最初の高々$k$項を与えればよいこと, 及び直前の高々$k$項で次の項が決まることを指し, 例えばFibonacci数列だと$k=2$となります.
しかしながら, この定義だとうまくいかないが, 我々が漸化式だと認識できるものがあります. それは最初の例の
\begin{equation}
a_{n+1} = \sum_{i=0}^{n}a_i + n
\end{equation}
になります. この漸化式, 何が曲者って, 直前の何項を使うかが, 項番号$n$によって変わるんですよね. 具体的には, $a_1$を決めるには$a_0$の$1$項のみを用いますが, $a_2$を決めるには$a_0, a_1$の$2$項が必要で, 一般に, $a_{n+1}$を決めるには$a_0, \cdots, a_n$の$n+1$項が必要になります. つまり, 上で挙げた$k$としてどんなに大きな値を用いても, この漸化式は表現できないことになります. 直感的には$k = \infty$ですね. この直感を元に, どうにか表現できないでしょうか.
ところで, もちろんこれは真の意味で正しくはありませんが,
\begin{equation}
A \sub \N_0 \times A \sub \N_0 \times A^2 \sub \N_0 \times A^3 \sub \cdots
\end{equation}
のようにみなすことはできるでしょう. 今はこの$\cdots$の先を, いわば$\N_0 \times A^{\infty}$のようにしてどうにか定義したいわけです. そんなとき, 定義1で導入した記号が役に立ちます. $\infty$の代わりに$\mathbb{N}_0$を用いて, $\N_0 \times A^{\N_0}$を考えるわけです. 「写像$\varphi$が$A$上の漸化式である」とは,「$\varphi : \N_0 \times A^{\N_0} \to A$をみたすことである」のように考えてみましょう.
試しに, 漸化式
\begin{equation}
a_{n+1} = \sum_{i=0}^{n}a_i + n
\end{equation}
を元に考えてみます. 写像$\varphi_4 : \N_0 \times \R^{\N_0} \to \R$を,
\begin{equation}
\varphi_4(n; (a_m)_m) = \sum_{i=0}^n a_i + n
\end{equation}
で定めます. この写像$\varphi_4$は, どうやら漸化式を表現できていそうです. これまで扱ってきた$\varphi_j\; (j=1,2,3)$も, 始域を$\N_0 \times \R^{\N_0}$に書き換えて, それぞれ$\hat{\varphi}_j\; (j=1, 2, 3)$として下に書き下しておきますね:
\begin{align}
& \hat{\varphi}_1 : \N_0 \times \R^{\N_0} \ni (n; (a_m)_m) \mapsto a_n + 3 \in \R. \\
& \hat{\varphi}_2 : \N_0 \times \R^{\N_0} \ni (n; (a_m)_m) \mapsto a_n + 2n -1 \in \mathbb{R}. \\
& \hat{\varphi}_3 : \N_0 \times \R^{\N_0} \ni (n; (a_m)_m) \mapsto a_{n+1} + a_n \in \R.
\end{align}
漸化式の定義
さて, 前節での考察を踏まえて, 今から漸化式を定義していきます. 前節と比べていくらか定義の条件が増えていますが, その意味も少し考えればわかるはずです.
ここから先では, 漸化式やその派生概念を定義しますが, これらの定義は一般的に浸透しているものでは決してなく, 私がオリジナルで考えたものです. このことを留意してから続きを読んでください.
$A$を非空集合とする. 写像$\varphi$が$A$上の漸化式であるとは, 以下の(i), (ii)をみたすことを言う.
- $\varphi$は$\N_0 \times A^{\N_0}$から$A$への写像である. すなわち, $\varphi : \N_0 \times A^{\N_0} \to A$である.
- ある$k \in \mathbb{N}$が存在して, 次をみたす: 各$n\in\N_0$を固定する毎に, 写像$A^{\N_0} \ni (a_m)_m \mapsto \varphi(n; (a_m)_m) \in A$は, 最初の$n+k$個の成分のみに依存する.
(ii)の$k\in\N$の最小値$k_0$を, 漸化式$\varphi$の階(order)と言い, このとき$\varphi$は$k_0$階の漸化式であると言う.
定義の(i)は前節で触れたとおりです. 定義の(ii)は, 例えば$k=1$を考えるとわかりやすいです. ラフに言えば, $\varphi$の具体的な表示に$a_{n+1}, a_{n+2}, \cdots$が出てこないことを指し, 理にかなっていると言えるでしょう. 前節で触れたFibonacci数列の漸化式$\hat{\varphi}_3$は$2$階の漸化式ですね.
(ii)の部分を論理式で正確に記述すると, 次のようになります.
\begin{align}
\exists k \in \N \; &\forall n \in \Nn \; \forall (a_m)_m, (b_m)_m \in A^\Nn \; \\
&\left[\, \left(\, \forall l \in \{0, \cdots , n+k-1\} \; [\, a_l=b_l \,]\, \right) \to \varphi(n; (a_m)_m) = \varphi(n; (b_m)_m) \,\right].
\end{align}
これで晴れて漸化式の定義ができました. 次章では, どんな漸化式にも, その階の数だけ項を与えれば, 一意的な一般項をもつことを示しましょう.
一般項の一意的存在性
後の都合上, 漸化式から派生する2つの概念を定義しておきます.
$A$を非空集合, $\varphi$を$A$上の$k$階の漸化式とする. $\varphi$の拡大漸化式を,
\begin{align}
& \Phi : \N_0 \times A^{\N_0} \ni (n; (a_m)_m) \mapsto (n+1; (b^{(n)}_m)_m) \in \N_0 \times A^{\N_0}, \\
& \text{where }b^{(n)}_m :=
\begin{cases}
\varphi(n; (a_l)_l) \; ; \; m=n+k \\
a_m \; ; \; \text{otherwise}
\end{cases}
\quad (m \in \mathbb{N}_0)
\end{align}
で定まる写像$\Phi$として定める.
拡大漸化式は, その名の通り漸化式の終域を拡大したものです. 上で述べた定理1では, 始域と終域が一致するような写像に対して適用できるため, このような概念を導入します.
$\Phi$の直感的な意味としては, 時刻$n$に第$n+k$成分のみを$\varphi$によって更新する, といった感じです. $\Phi$のイメージ図は, 後に述べる定理2の証明の中に載せておきました.
余談ですが, 拡大漸化式を単に漸化式として定義しようか迷いました.
$A$を非空集合, $\varphi$を$A$上の$k$階の漸化式とする. 点列$(a_m)_m \in A^{\N_0}$が漸化式$\varphi$をみたすとは, 任意の$n \in \N_0$に対して,
\begin{equation}
a_{n+k} = \varphi(n; (a_m)_m)
\end{equation}
をみたすことを言う.
漸化式をみたすという概念もここで定義しておきます. これがないと話ができないですからね.
さて, 準備ができたので, 本題の一般項の一意的存在性に入っていきます.
$A$を非空集合とし, $A$上の漸化式$\varphi$を任意に与え, その階を$k$とする. また, $A$の$k$個の元$\alpha_0, \cdots, \alpha_{k-1}$を任意に与える. このとき, ある一意的な点列$(a_n)_n \in A^{\N_0}$が存在して, 次の(i), (ii)をみたす.
- 任意の$j=0, \cdots, k-1$に対して, $a_j = \alpha_j$である.
- 点列$(a_n)_n$は漸化式$\varphi$をみたす.
$\varphi$の拡大漸化式を$\Phi$とする. また, 各$n\geqq k$に対して, $\alpha_{n} := \alpha_{k-1}$と定めて, 点列$(\alpha_n)_n \in A^{\N_0}$ を定める.
まず存在性を示す. このとき, 定理1より, ある$F\in(\N_0 \times A^{\N_0})^{\N_0}$をとれて,
\begin{equation}
F(0) = (0; (\alpha_m)_m), \quad F(n+1) = \Phi(F(n)) \; (\forall n \in \N_0)
\end{equation}
をみたす. このとき, 点列$(a_n)_n \in A^{\N_0}$を,
\begin{equation}
a_n =
\begin{cases}
\alpha_n \; ; \; 0\leqq n \leqq k-1 \\
\mathrm{pr}_n^{(2)}(F(n-k+1)) \; ; \; n\geqq k
\end{cases}
\quad (n\in\N_0)
\end{equation}
で定めればよい(これはある種の対角線論法である). ただし, 各$n \in \N_0$に対して, $\mathrm{pr}^{(2)}_n : \N_0 \times A^{\N_0} \ni (l; (x_m)_m) \mapsto x_n \in A$は射影である.
![!FORMULA[151][-1353467236][0]に対するイメージ図(!FORMULA[152][36494569][0])](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FTF2JQcTIEVBFeyZYCeOp.png?alt=media)
$\hat{\varphi}_1:\Nn \times \mathbb{R}^\Nn \ni (n; (x_m)_m) \mapsto x_n+3$に対するイメージ図($k=1$)
次に一意性を示す. 点列$(a_n)_n, (b_n)_n \in A^{\N_0}$を定理の条件をみたすものとする. $F, G : \N_0 \to \N_0 \times A^{\N_0}$を,
\begin{align*}
&F(n) = (n; (a^{(n)}_m)_m) \quad (n\in\N_0), \\
& \text{where }a^{(n)}_m :=
\begin{cases}
a_m\; ; \; 0\leqq m \leqq n+k-1 \\
\alpha_{k-1} \; ; \; m\geqq n+k
\end{cases}
\quad (m \in \mathbb{N}_0),
\end{align*}
\begin{align*}
&G(n) = (n; (b^{(n)}_m)_m) \quad (n\in\N_0), \\
& \text{where }b^{(n)}_m :=
\begin{cases}
b_m\; ; \; 0\leqq m \leqq n+k-1 \\
\alpha_{k-1} \; ; \; m\geqq n+k
\end{cases}
\quad (m \in \mathbb{N}_0)
\end{align*}
で定めれば, $(0; (\alpha_m)_m)$と$\Phi$に対する定理1より, $F=G$である. よって, 任意の$n\in\N_0$に対して,
\begin{equation}
a_n = \mathrm{pr}_n^{(2)}(F(n)) = \mathrm{pr}_n^{(2)}(G(n)) = b_n
\end{equation}
であるから, $(a_n)_n=(b_n)_n$である. $\blacksquare$
ついでに, 度々用いる系も述べておきます.
$A$を非空集合とする. 任意に与えた写像$\widetilde{\varphi}$は終域が$\mathscr{A} := 2^A \setminus \{ \varnothing \}$であって, $A$上の漸化式の定義のうち終域以外をすべてみたしているとして, その階を$k$とする. また, $A$の$k$個の元$\alpha_0, \cdots, \alpha_{k-1}$を任意に与える. このとき, ある点列$(a_n)_n \in A^{\N_0}$が存在して, 次の(i), (ii)をみたす.
- 任意の$j=0, \cdots, k-1$に対して, $a_j = \alpha_j$である.
- 任意の$n\in\mathbb{N}_0$に対して, $a_{n+k} \in \widetilde{\varphi}(n; (a_m)_m)$をみたす.
選択公理より, ある$f \in A^\mathscr{A}$をとれて, 任意の$X \in \mathscr{A}$に対して, $f(X)\in X$をみたす. よって, $\varphi := f \circ\widetilde{\varphi}$に対して定理2を用いればよい. $\blacksquare$
漸化式の集合バージョンですね. 証明には選択公理を使います.
最後に連立漸化式についても見てみましょう.
$\Lambda$を空でない集合とし, $(A_\lambda)_{\lambda\in\Lambda}$を空でない集合からなる集合族とする. $A := \prod_{\lambda\in\Lambda} A_\lambda$とおき, $A$上の漸化式$\varphi$を任意に与え, その階を$k$とする. また, 各$\lambda\in\Lambda$に対して, $A_\lambda$の$k$個の元$\alpha^{(\lambda)}_0, \cdots, \alpha^{(\lambda)}_{k-1}$を任意に与える. このとき, ある一意的な点列の族$((a^{(\lambda)}_n)_n)_{\lambda\in\Lambda} \in \prod_{\lambda\in\Lambda} {A_\lambda}^{\N_0}$が存在して, 次の(i), (ii)をみたす.
- 各$\lambda\in\Lambda$と任意の$j\in\{0, \cdots, k-1\}$に対して, $a^{(\lambda)}_j = \alpha^{(\lambda)}_j$である.
- 各$\lambda\in\Lambda$と任意の$n\in\N_0$に対して, $a^{(\lambda)}_{n+k} = \mathrm{pr}_{\lambda}(\varphi(n;((a^{(\mu)}_m)_{\mu\in\Lambda})_m))$をみたす. ただし, 各$\lambda\in\Lambda$に対して, $\mathrm{pr}_\lambda : A \ni (x_\mu)_{\mu\in\Lambda} \mapsto x_\lambda \in A_\lambda$は射影である.
選択公理より, $A\neq\varnothing$である. あとは定理2より明らか. $\blacksquare$
定理を使ってみよう
せっかく定理を作ったんだし, 使いましょう.
実数列$(a_n)_n \in \mathbb{R}^\Nn$が与えられているとする. $\mathbb{R}$上の漸化式$\varphi : \Nn \times \mathbb{R}^\Nn \to \Nn$を,
\begin{equation}
\varphi(n; (x_m)_m) = x_n + a_{n+1} \quad ((n; (x_m)_m) \in \Nn \times \mathbb{R}^\Nn)
\end{equation}
で定める. このとき, $\varphi$は$1$階の漸化式であるため, $\varphi$と$a_0\in\mathbb{R}$に対して定理2を用いれば, ある一意的な点列$(S_n)_n \in \mathbb{R}^\Nn$をとれて,
\begin{equation}
S_0 = a_0, \quad S_{n+1} = S_n + a_{n+1} \; \left(\forall n\in\Nn \right)
\end{equation}
をみたす. そこで, 各$n\in\mathbb{N}_0$に対して,
\begin{equation}
\sum_{i=0}^n a_i := S_n
\end{equation}
と定める.
$A$を無限集合とし, $a\in A$とする. $\widetilde{\varphi} : \Nn \times A^\Nn \to 2^A\setminus \{\varnothing\}$を,
\begin{equation}
\widetilde{\varphi}(n; (x_m)_m) = A\setminus \bigcup_{i=0}^n \{x_i\} \quad ((n; (x_m)_m) \in \Nn \times A^\Nn)
\end{equation}
で定める. このとき, $\widetilde{\varphi}$は$1$階の漸化式の集合バージョンであるため, $\widetilde{\varphi}$と$a\in A$に対して定理2 系1を用いれば, ある点列$(a_n)_n \in A^\Nn$をとれて,
\begin{equation}
a_0 = a, \quad a_{n+1} \in A \setminus \bigcup_{i=0}^n \{a_i\} \; \left(\forall n\in\Nn \right)
\end{equation}
をみたす. このとき, $(a_n)_n \in A^\Nn$は単射だから, $|\Nn| \leqq |A|$である.
$A := [0, +\infty[$とし $a, b \in A$とする. $A^2$上の漸化式$\varphi : \Nn \times (A^2)^\Nn \to A^2$を,
\begin{equation}
\varphi(n; ((x_m, y_m))_m) = \left(\frac{x_n+y_n}{2}, \sqrt{x_ny_n} \right) \quad ((n; ((x_m, y_m))_m) \in \Nn \times (A^2)^\Nn)
\end{equation}
で定める. このとき, $\varphi$は$1$階の漸化式であるため, $\varphi$と$(a, b) \in A^2$に対して定理2 系2を用いれば, ある一意的な$((a_n)_n, (b_n)_n)\in(A^\Nn)^2$をとれて,
\begin{gather*}
a_0 = a,\quad b_0=b,\\
a_{n+1} = \frac{a_n+b_n}{2},\quad b_{n+1} = \sqrt{a_nb_n} \; \left(\forall n\in\Nn \right)
\end{gather*}
をみたす.
おわりに
ここまで読んでくれてありがとうございます. まぁ正直, 漸化式があったらそりゃ一般項はあるんですけど, 満足いく結果が得られたのでよかったです. 私は漸化式を上のように定義しましたが, 中には$\bigcup_{n\in\Nn} A^{\{0, \cdots, n\}}$から$A$への写像を漸化式とする定義もあるようです. 本質的に私のものと変わりませんが, こっちの方が綺麗ですね(負けた…).
数学を勉強し始めてから半年以上経ちましたが, どの分野も楽しすぎて無限にやばいなと思っています. もっと色々勉強したいですね.
この記事を高評価した人
この記事に送られたバッジ
投稿者
