漸化式ぜんかしきの類型るいけいと解法方針かいほうほうしん

date2026-07-14document_iddoc_a7663c3941d54809a359d4360a750164description漸化式を階数と線型性によって分類し、差分、平衡点、特性多項式、状態ベクトルによる解法選択を証明つきで整理する講義。prerequisites数列と漸化式 / 等差数列と等比数列 / シフト作用素と漸化式 / 数学的帰納法type講義content_typelecturestatusactive

mathsequencerecurrenceshift-operatorexam-strategylecture

1導入どうにゅう

漸化式ぜんかしきの解法かいほうは、公式こうしきの選択せんたくではなく、依存いぞんする過去かこの項数こうすうと式しきの構造こうぞうの識別しきべつから開始かいしする。本講義ほんこうぎでは、まず階数かいすうと線型性せんけいせいを定義ていぎし、その後ごに各類型かくるいけいを単純たんじゅんな数列すうれつまたは作用素方程式さようそほうていしきへ帰着きちゃくする。

2分類用語ぶんるいようご

$a_{n + k}$ を $a_{n}, \dots, a_{n + k - 1}$ から定さだめる漸化式ぜんかしきで、実際じっさいに必要ひつような最大さいだいの添字差そえじさを階数かいすうorderという。例たとえば $a_{n + 1} = p a_{n} + q$ は 1 階かいである。 $a_{n + 2} = s a_{n + 1} + t a_{n}$ は $t \neq 0$ のとき 2 階かいであり、 $t = 0$ なら 1 階かいへ低下ていかする。

線型漸化式せんけいぜんかしきlinear recurrenceとは、未知列みちれつの各かくシフトの線型結合せんけいけつごうとして表現ひょうげんされ、係数けいすうと右辺うへんが未知列みちれつに依存いぞんしない漸化式ぜんかしきである。未知項みちこうどうしの積せき、冪べき、または未知項みちこうの非線型関数ひせんけいかんすうを含ふくむものは線型せんけいではない。定数係数ていすうけいすう $c_{j}$ に対たいする

c_{0} a_{n} + c_{1} a_{n + 1} + \dots + c_{k} a_{n + k} = f (n)

が標準例ひょうじゅんれいである。 $c_{k} \neq 0$ なら、添字そえじが増加ぞうかする方向ほうこうについて $k$ 階かいである。 $f = 0$ を同次どうじ、 $f \neq 0$ を非同次ひどうじという。シフト作用素さようそ $(E a)_{n} = a_{n + 1}$ を使用しようすれば、この式しきは $P (E) a = f$ と表現ひょうげんできる。

3判定手順はんていてじゅん

構造こうぞう	導入量どうにゅうりょう	帰着先きちゃくさき
$a_{n + 1} - a_{n} = f (n)$	$Δ a_{n}$	有限和ゆうげんわ
$a_{n + 1} = r a_{n}$	そのまま	等比数列とうひすうれつ
$a_{n + 1} = p a_{n} + q$	$a_{n} - α$	等比数列とうひすうれつ
$a_{n + 1} = p a_{n} + f (n)$	$a_{n} / p^{n - 1}$	差分型さぶんがた
$a_{n + 2} - a_{n + 1} = r (a_{n + 1} - a_{n})$	$b_{n} = a_{n + 1} - a_{n}$	等比数列とうひすうれつ
部分和ぶぶんわ $S_{n}$ を含ふくむ	$S_{n + 1} - S_{n} = a_{n + 1}$	$S_{n}$ の消去しょうきょ
$a_{n + 1} = r_{n} a_{n}$	有限積ゆうげんせき	積型せきがた
$a_{{n + 1}^{- 1}} = a_{n^{- 1}} + d$	$b_{n} = 1 / a_{n}$	等差数列とうさすうれつ
$a_{n + 1} = [PARSE ERROR: Undefined("Command(\"dfrac\")")] A a_{n} + B C a_{n} + D$	固定点こていてんとの交比こうひ	等比数列とうひすうれつ
定数係数高階線型ていすうけいすうこうかいせんけい	$P (E)$	特性多項式とくせいたこうしき
複数状態ふくすうじょうたいの線型系せんけいけい	状態じょうたいベクトル	行列反復ぎょうれつはんぷく
合同ごうどう・不等式ふとうしき	剰余じょうよ・不変集合ふへんしゅうごう	性質せいしつの帰納法きのうほう

4命題めいだい 1：差分さぶんの総和そうわ

$n \geq 1$ で $a_{n + 1} - a_{n} = f (n)$ が成立せいりつするなら、

[PARSE ERROR: Undefined("Command(\"boxed\")")] a_{n} = a_{1} + \sum_{k = 1}^{n - 1} f (k)

が成立せいりつする。 $n = 1$ では空和くうわを 0 とする。 $n \geq 2$ では仮定かていを $k = 1, \dots, n - 1$ について総和そうわすると、左辺さへんが望遠和ぼうえんわ $a_{n} - a_{1}$ となるため、結論けつろんを得える。 $f (n) = d$ は等差数列とうさすうれつを与あたえる。

5命題めいだい 2：一次非同次型いちじひどうじがた

$a_{n + 1} = p a_{n} + q$ とする。 $p = 1$ なら命題めいだい 1 により

a_{n} = a_{1} + (n - 1) q

である。 $p \neq 1$ なら平衡点へいこうてん $α = q / (1 - p)$ を定義ていぎし、 $b_{n} = a_{n} - α$ とする。 $α = p α + q$ より

b_{n + 1} = p a_{n} + q - α = p (a_{n} - α) = p b_{n} .

したがって、

[PARSE ERROR: Undefined("Command(\"boxed\")")] a_{n} = α + (a_{1} - α) p^{n - 1}

が成立せいりつする。 $p = 1$ の分離ぶんりは、零れいによる除算じょざんを回避かいひするために必須ひっすである。

6命題めいだい 3：変化係数法へんかけいすうほう

$p \neq 0$ かつ $a_{n + 1} = p a_{n} + f (n)$ とする。 $b_{n} = a_{n} / p^{n - 1}$ と定義ていぎすると、

b_{n + 1} - b_{n} = \frac{f (n)}{p^{n}} .

命題めいだい 1 を適用てきようして、

[PARSE ERROR: Undefined("Command(\"boxed\")")] a_{n} = p^{n - 1} (a_{1} + \sum_{k = 1}^{n - 1} \frac{f (k)}{p^{k}})

を得える。 $p = 0$ では $a_{n + 1} = f (n)$ が直接ちょくせつ $a_{2}, a_{3}, \dots$ を決定けっていするため、別途処理べっとしょりする。

7命題めいだい 4：階差数列かいさすうれつ

$a_{n + 2} - a_{n + 1} = r (a_{n + 1} - a_{n})$ とし、 $b_{n} = a_{n + 1} - a_{n}$ と定義ていぎする。すると $b_{n + 1} = r b_{n}$ であるから、 $b_{n} = (a_{2} - a_{1}) r^{n - 1}$ である。命題めいだい 1 により、

a_{n} = a_{1} + (a_{2} - a_{1}) \sum_{k = 0}^{n - 2} r^{k}

となる。 $r = 1$ では和わが $n - 1$ 、 $r \neq 1$ では $(1 - r^{n - 1}) / (1 - r)$ である。

8命題めいだい 5：定数係数二階線型型ていすうけいすうにかいせんけいがた

a_{n + 2} - s a_{n + 1} - t a_{n} = 0

を体たい $K$ 上じょうで考察こうさつする。 $t = 0$ なら階数かいすうが低下ていかする。特とくに $s = t = 0$ なら $a_{n + 2} = 0$ であり、 $a_{1}, a_{2}$ は任意にんい、 $n \geq 3$ では $a_{n} = 0$ である。以下いか、 $t \neq 0$ とする。特性多項式とくせいたこうしきを $χ (x) = x^{2} - s x - t$ とする。 $χ$ が分解ぶんかいする拡大体かくだいたい $L$ で相異そういなる根ね $α, β$ をもつなら、 $L$ 値ちのすべての解かいは

[PARSE ERROR: Undefined("Command(\"boxed\")")] a_{n} = A α^{n - 1} + B β^{n - 1}

である。実際じっさい、 $x = α, β$ を代入だいにゅうすれば各列かくれつが漸化式ぜんかしきを満みたす。また、 $a_{1}, a_{2}$ を一致いっちさせる $A, B$ は一意いちいに存在そんざいする。差さを取とった解かいは初はじめの 2 項こうが零れいであり、漸化式ぜんかしきによる帰納法きのうほうで全項ぜんこうが零れいとなるため、これが全解ぜんかいである。

$χ$ が非零ひれいの重根じゅうこん $α$ をもつなら、全解ぜんかいは

[PARSE ERROR: Undefined("Command(\"boxed\")")] a_{n} = (A + B (n - 1)) α^{n - 1}

である。これは $(E - α I)^{2}$ を $α^{n - 1}$ と $(n - 1) α^{n - 1}$ に作用さようさせて零れいとなることを直接計算ちょくせつけいさんし、同おなじ初期値一意性しょきちいちいせいを用もちいて証明しょうめいできる。

9高階こうかいと状態じょうたいベクトル

$k$ 階かいの定数係数同次線型漸化式ていすうけいすうどうじせんけいぜんかしきは $P (E) a = 0$ と表現ひょうげんできる。非零ひれいの特性根とくせいこん $λ$ の重複度ちょうふくどが $m$ なら、 $λ^{n}, n λ^{n}, \dots, n^{m - 1} λ^{n}$ に対応たいおうする解かいが現あらわれる。零根れいこんは階数かいすうの低下ていかまたは有限初期部分ゆうげんしょきぶぶんに関係かんけいするため、原式げんしきと初期値しょきちから処理しょりする。完全かんぜんな結論けつろんには $P$ の分解体ぶんかいたいを指定していする必要ひつようがある。

また、 $k$ 階かいの定数係数同次線型漸化式ていすうけいすうどうじせんけいぜんかしきは $v_{n} = (a_{n + k - 1}, \dots, a_{n})^{T}$ を導入どうにゅうして $v_{n + 1} = M v_{n}$ と 1 階かいの行列漸化式ぎょうれつぜんかしきへ変換へんかんできる。この操作そうさは階数かいすうを消去しょうきょするのではなく、過去かこ $k$ 項こうを一ひとつの状態じょうたいに統合とうごうする。

10追加類型ついかるいけい

部分和ぶぶんわ $S_{n} = \sum_{j = 1}^{n} a_{j}$ を含ふくむ式しきでは、 $n + 1$ の式しきと $n$ の式しきの差さを形成けいせいし、 $S_{n + 1} - S_{n} = a_{n + 1}$ によって部分和ぶぶんわを消去しょうきょする。

積型せきがた $a_{n + 1} = r_{n} a_{n}$ は $a_{n} = a_{1} \prod_{j = 1}^{n - 1} r_{j}$ となる。逆数型ぎゃくすうがた $1 / a_{n + 1} = 1 / a_{n} + d$ は、すべての対象項たいしょうこうが非零ひれいであるとき $b_{n} = 1 / a_{n}$ により等差型とうさがたへ帰着きちゃくする。

メビウス型がた $T (x) = (A x + B) / (C x + D)$ で $A D - B C \neq 0$ とし、相異そういなる有限固定点ゆうげんこていてん $α, β$ があり、分母ぶんぼおよび $a_{n} - β$ が非零ひれいであるとする。このとき、ある定数ていすう $ρ$ により

\frac{T (x) - α}{T (x) - β} = ρ \frac{x - α}{x - β}

が成立せいりつするため、 $z_{n} = (a_{n} - α) / (a_{n} - β)$ は等比数列とうひすうれつとなる。

線型連立せんけいれんりつ $w_{n + 1} = M w_{n}$ は状態じょうたいベクトルの行列反復ぎょうれつはんぷくである。対称二変数系たいしょうにへんすうけい

x_{n + 1} = a x_{n} + b y_{n}, y_{n + 1} = b x_{n} + a y_{n}

では、 $u_{n} = x_{n} + y_{n}$ 、 $v_{n} = x_{n} - y_{n}$ により $u_{n + 1} = (a + b) u_{n}$ 、 $v_{n + 1} = (a - b) v_{n}$ と分離ぶんりできる。

整数列せいすうれつで $q_{n} \in Z$ かつ $a_{n + 1} = a_{n - 1} + q_{n} a_{n}$ が成立せいりつするなら、

[PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n + 1}, a_{n}) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n - 1} + q_{n} a_{n}, a_{n}) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (a_{n - 1}, a_{n})

である。これは $[PARSE ERROR: Undefined("Command(\"gcd\")")] (x + q y, y) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (x, y)$ による隣接最大公約数りんせつさいだいこうやくすうの不変性ふへんせいである。

11性質せいしつを求もとめる問題もんだい

一般項いっぱんこうが不要ふような場合ばあいもある。整数係数せいすうけいすうの漸化式ぜんかしきを法ほう $m$ で縮約しゅくやくすれば、有限個ゆうげんこの剰余状態じょうよじょうたいを解析かいせきできる。不等式ふとうしきや区間不変性くかんふへんせいは、初期条件しょきじょうけんを確認かくにんし、 $a_{n}$ の性質せいしつから更新式こうしんしきによって $a_{n + 1}$ の性質せいしつを導みちびく帰納法きのうほうで証明しょうめいする。

極限きょくげんを問とう問題もんだいでは、固定点こていてんを候補こうほとするだけでは収束しゅうそくの証明しょうめいにならない。極限きょくげん、連続性れんぞくせい、単調性たんちょうせい、有界性ゆうかいせいを導入どうにゅうした後続講義こうぞくこうぎで厳密げんみつに扱あつかう。

12適用範囲てきようはんい

比ひを使用しようする判定はんていには分母ぶんぼの非零性ひれいせい、変化係数法へんかけいすうほうには $p \neq 0$ 、平衡点法へいこうてんほうには $p \neq 1$ が必要ひつようである。非線型漸化式ひせんけいぜんかしきでは、逆数ぎゃくすう、対数たいすう、固定点こていてんからの差さの比ひ等とうの変換へんかんが有効ゆうこうな場合ばあいがあるが、変換へんかんの定義域ていぎいきと逆変換可能性ぎゃくへんかんかのうせいを個別こべつに確認かくにんする必要ひつようがある。