シフト作用素さようそと漸化式ぜんかしき

date2026-07-14document_iddoc_0b18ab09a807f50dfc45ab78e5df7a24description漸化式・差分・和分を、シフト作用素 E による線型作用素方程式として統一する講義である。prerequisites数列と漸化式 / 線型作用素方程式 / 等差数列と等比数列type講義content_typelecturestatusactive

mathsequencerecurrenceshift-operatorlinear-operatorlecture

1導入どうにゅう

この講義こうぎでは、差分さぶんdifference、和分わぶんindefinite sum、漸化式ぜんかしきrecurrence relationを、列れつを 1 項こう前進ぜんしんさせるシフト作用素さようそshift operator $E$ によって統一的とういつてきに記述きじゅつする。

差分さぶんはシフト後ごの列れつと元もとの列れつの差さであり、和分わぶんはその逆問題ぎゃくもんだいである。また、定数係数線型漸化式ていすうけいすうせんけいぜんかしきはシフトした列れつの線型結合せんけいけつごうとして表現ひょうげんできる。したがって、中心的ちゅうしんてきな作用素さようそは

(E a)_{n} = a_{n + 1}

である。

この解釈かいしゃくにより、漸化式ぜんかしきは単たんなる項こうの更新規則こうしんきそくではなく、

P (E) a = b

という線型作用素方程式せんけいさようそほうていしきlinear operator equationになる。

2用語ようごと定義ていぎ

列れつ $a = (a_{n})$ 全体ぜんたいからなる空間くうかんを考かんがえる。必要ひつように応おうじて、両側りょうがわ無限列むげんれつ $(a_{n})_{n \in Z}$ や片側かたがわ列れつ $(a_{n})_{n [PARSE ERROR: Undefined("Command(\"ge\")")] 0}$ を使つかう。ここでは、添字そえじが定義ていぎできる範囲はんいで議論ぎろんする。

シフト作用素さようそshift operator $E$ を

(E a)_{n} = a_{n + 1}

で定義ていぎする。

恒等作用素こうとうさようそidentity operator $I$ は

(I a)_{n} = a_{n}

である。

前進差分ぜんしんさぶんforward difference $Δ$ は

(Δ a)_{n} = a_{n + 1} - a_{n}

である。したがって

Δ = E - I

である。

この規約きやくは Z 変換へんかんの講義こうぎと一致いっちし、両側りょうがわ Z 変換へんかんでは $E$ が $z$ による乗算じょうざんへ対応たいおうする。

3方針ほうしん

この講義こうぎでは、次つぎの順じゅんに確認かくにんする。

$E$ が線型作用素せんけいさようそlinear operatorであることを証明しょうめいする。
$Δ = E - I$ から差分さぶん公式こうしきを導みちびく。
$Δ F = f$ を和分わぶん、すなわち差分さぶんの逆問題ぎゃくもんだいとして定式化ていしきかする。
定数ていすう係数けいすう線型せんけい漸化式ぜんかしきを $P (E) a = b$ と書かく。
$r^{n}$ が $E$ の固有列こゆうれつeigen-sequenceであることから、特性とくせい方程式ほうていしきを導みちびく。

この順序じゅんじょにより、各手法かくしゅほうの採用理由さいようりゆうを作用素さようその構造こうぞうから説明せつめいできる。

個別こべつの入試にゅうし型かたや、固定点こていてん・階差かいさ・和わの消去しょうきょ・連立れんりつ化か・帰納法きのうほうへの使つかい分わけは、次つぎの講義こうぎで整理せいりする。

data/lecture/math/sequence/recurrence-types-and-strategies.lecture.n.md data/lecture/math/linear-operator/linear-operator-equation-basics.lecture.n.md data/lecture/math/linear-operator/polynomial-operators-and-eigenvalue-problems.lecture.n.md

4命題めいだい 1： $E$ は線型作用素せんけいさようそlinear operatorである

4.1主張しゅちょう

列れつ空間上くうかんじょうの $E$ は線型作用素せんけいさようそlinear operatorである。

4.2証明しょうめい

列れつ $a, b$ とスカラー $α, β$ を任意にんいに取とる。このとき

\begin{aligned} (E(\alpha a+\beta b))_n &=(\alpha a+\beta b)_{n+1}\\ &=\alpha a_{n+1}+\beta b_{n+1}\\ &=(\alpha Ea+\beta Eb)_n \end{aligned}\begin{aligned} (E(\alpha a+\beta b))_n &=(\alpha a+\beta b)_{n+1}\\ &=\alpha a_{n+1}+\beta b_{n+1}\\ &=(\alpha Ea+\beta Eb)_n \end{aligned}

である。これはすべての $n$ で成立せいりつするので

E (α a + β b) = α E a + β E b

である。したがって $E$ は線型せんけいである。

5差分さぶんは $E - I$ である

前進ぜんしん差分さぶんは

(Δ a)_{n} = a_{n + 1} - a_{n}

である。一方いっぽう、

((E - I) a)_{n} = (E a)_{n} - (I a)_{n} = a_{n + 1} - a_{n}

である。したがって

Δ = E - I

である。

ここから、 $Δ$ の線型性せんけいせいlinearityも直ただちに従したがう。 $E$ と $I$ が線型せんけいであるため、その差さ $E - I$ も線型せんけいである。実際じっさい、

Δ (α a + β b) = (E - I) (α a + β b) = α (E - I) a + β (E - I) b = α Δ a + β Δ b

である。

6二項定理にこうていりによる高階差分こうかいさぶん

$Δ = E - I$ であり、 $E$ と $I$ は可換かかんである。したがって

Δ^{m} = (E - I)^{m}

に二項定理にこうていりbinomial theoremを適用てきようできる。

Δ^{m} = \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) E^{m - k}

である。列れつ $a$ に作用さようさせると

(Δ^{m} a)_{n} = \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) a_{n + m - k}

を得える。

この公式こうしきの符号ふごうと添字そえじは、 $(E - I)^{m}$ の二項展開にこうてんかいによって決定けっていされる。

7和分わぶんは差分さぶんの逆問題ぎゃくもんだいである

不定和分ふていわぶんindefinite sumの基本きほん問題もんだいは

Δ F = f

を満みたす列れつ $F$ を決定けっていすることである。これは

F (n + 1) - F (n) = f (n)

を意味いみする。

$n = a, a + 1, \dots, b - 1$ について両辺りょうへんを加算かさんすると

\sum_{n = a}^{b - 1} f (n) = \sum_{n = a}^{b - 1} (F (n + 1) - F (n))

である。右辺うへんは望遠和ぼうえんわtelescoping sumなので

\sum_{n = a}^{b - 1} f (n) = F (b) - F (a)

を得える。

これは連続れんぞくの微積分びせきぶんで

\int_{a}^{b} F^{'} (x) d x = F (b) - F (a)

となることの離散りさん版はんである。つまり、和わ分ふんとは $Δ$ の逆問題ぎゃくもんだいである。

8積せきの差分さぶんにおけるシフト項こう

連続れんぞく微分びぶんでは積つの微分びぶんが

(u v)^{'} = u^{'} v + u v^{'}

となる。しかし差分さぶんでは、ずれが残のこる。

実際じっさい、

\begin{aligned} \Delta(uv)(n) &=u(n+1)v(n+1)-u(n)v(n)\\ &=u(n+1)v(n+1)-u(n)v(n+1)\\ &\qquad +u(n)v(n+1)-u(n)v(n)\\ &=v(n+1)(u(n+1)-u(n))+u(n)(v(n+1)-v(n)) \end{aligned}\begin{aligned} \Delta(uv)(n) &=u(n+1)v(n+1)-u(n)v(n)\\ &=u(n+1)v(n+1)-u(n)v(n+1)\\ &\qquad +u(n)v(n+1)-u(n)v(n)\\ &=v(n+1)(u(n+1)-u(n))+u(n)(v(n+1)-v(n)) \end{aligned}

である。したがって

Δ (u v) = (E v) Δ u + u Δ v

である。

右辺うへんの $(E v)$ は、前進差分ぜんしんさぶんが 1 項先こうさきの値あたいを含ふくむことを表あらわす。離散計算りさんけいさんでは、このシフトを省略しょうりゃくして連続微分れんぞくびぶんの公式こうしきを適用てきようしてはならない。

9部分和公式ぶぶんわこうしきは離散版りさんばんの部分積分ぶぶんせきぶん

積つの差分さぶん公式こうしき

Δ (u v) = u Δ v + (E v) Δ u

を変形へんけいすると

u Δ v = Δ (u v) - (E v) Δ u

である。両辺りょうへんを和わ分ふんすると

\sum u Δ v = u v - \sum (E v) Δ u

という形式けいしきを得える。有限範囲ゆうげんはんいでは

\sum_{n = a}^{b - 1} u (n) Δ v (n) = u (b) v (b) - u (a) v (a) - \sum_{n = a}^{b - 1} v (n + 1) Δ u (n)

が成立せいりつする。これは連続れんぞくの部分積分ぶぶんせきぶん

\int u d v = u v - \int v d u

の離散りさん版はんである。

ただし、右辺うへんに $v$ ではなく $E v$ が現あらわれる。この一項いっこうの偏移へんいが、差分法さぶんほうでシフト作用素さようそshift operatorを明示めいじする理由りゆうである。

10漸化式ぜんかしきは $P (E) a = b$ である

定数ていすう係数けいすう線型せんけい漸化式ぜんかしき

a_{n + k} = c_{1} a_{n + k - 1} + c_{2} a_{n + k - 2} + \dots + c_{k} a_{n} + b_{n}

を考かんがえる。左辺さへんへ集あつめると

a_{n + k} - c_{1} a_{n + k - 1} - c_{2} a_{n + k - 2} - \dots - c_{k} a_{n} = b_{n}

である。 $E$ を用もちいると

(E^{k} - c_{1} E^{k - 1} - c_{2} E^{k - 2} - \dots - c_{k} I) a = b

と書かける。

つまり

P (E) a = b

である。ただし

P (t) = t^{k} - c_{1} t^{k - 1} - c_{2} t^{k - 2} - \dots - c_{k}

である。

この段階だんかいで、漸化式ぜんかしきは一般いっぱんの線型作用素方程式せんけいさようそほうていしきlinear operator equationになっている。したがって

P (E) a = b issolvable ⟺ b \in Im P (E)

であり、特解とくかい $a_{p}$ が 1 つ存在そんざいすれば

a = a_{p} + h, h \in \ker P (E)

である。

11固有列こゆうれつと特性方程式とくせいほうていしき

両側列りょうがわれつでは $r \neq 0$ とし、片側列かたがわれつでは $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ で $r^{n}$ を定義ていぎする。この幾何列きかれつに対たいして

E (r^{n}) = r^{n + 1} = r r^{n}

である。つまり $r^{n}$ は $E$ の固有列こゆうれつeigen-sequenceであり、固有値こゆうちは $r$ である。

したがって

P (E) (r^{n}) = P (r) r^{n}

である。よって同次どうじ方程式ほうていしき

P (E) a = 0

に $a_{n} = r^{n}$ が解かいとなる条件じょうけんは

P (r) = 0

である。これが特性方程式とくせいほうていしきcharacteristic equationである。

特性とくせい方程式ほうていしきは、 $r^{n}$ が $E$ の固有こゆう列れつであるために現あらわれる。したがって、定数ていすう係数けいすう線型せんけい漸化式ぜんかしきの特性とくせい方程式ほうていしき法ほうは、固有値問題こゆうちもんだいeigenvalue problemの離散りさん版はんである。

12例れい：Fibonacci 型かた漸化式ぜんかしき

漸化式ぜんかしき

f_{n + 2} = f_{n + 1} + f_{n}

は

(E^{2} - E - I) f = 0

である。したがって

P (t) = t^{2} - t - 1

であり、特性とくせい方程式ほうていしきは

r^{2} - r - 1 = 0

である。根こんは

r_{1} = \frac{1 + \sqrt{5}}{2}, r_{2} = \frac{1 - \sqrt{5}}{2}

である。 $r_{1^{n}}$ と $r_{2^{n}}$ はそれぞれ $\ker P (E)$ に属ぞくする。異ことなる根こんに対応たいおうする 2 列れつは線型独立せんけいどくりつである。また、この二階漸化式にかいぜんかしきの解かいは $f_{0}, f_{1}$ によって一意いちいに決定けっていされるため、解空間かいくうかんは 2 次元じげんである。したがって、これらは解空間かいくうかんの基底きていをなし、一般解いっぱんかいは

f_{n} = C_{1} r_{1^{n}} + C_{2} r_{2^{n}}

を得える。定数ていすう $C_{1}, C_{2}$ は初期条件しょきじょうけんで決きまる。

ここで重要じゅうようなのは、 $r^{n}$ を試ためす理由りゆうである。 $r^{n}$ は $E$ の固有こゆう列れつであり、 $P (E)$ が $P (r)$ に落おちるからである。

13定数係数ていすうけいすうと非定数係数ひていすうけいすうの違ちがい

定数ていすう係数けいすうなら、漸化式ぜんかしきは $P (E)$ の形かたちで書かける。係数けいすうが定数ていすうであるため、 $E$ と係数けいすうが可換かかんであり、多項式たこうしきとして扱あつかえる。

しかし係数けいすうが $n$ に依存いぞんすると状況じょうきょうが変かわる。たとえば

a_{n + 1} - n a_{n} = 0

を考かんがえる。 $M$ を

(M a)_{n} = n a_{n}

で定義ていぎされる掛け算作用素ざんさようそmultiplication operatorとすると、この方程式ほうていしきは

(E - M) a = 0

の形かたちで書かける。しかし一般いっぱんに

E M \neq M E

である。実際じっさい、

(E M a)_{n} = (M a)_{n + 1} = (n + 1) a_{n + 1}

だが

(M E a)_{n} = n (E a)_{n} = n a_{n + 1}

である。

したがって、非定数係数ひていすうけいすうでは通常つうじょうの多項式たこうしき $P (E)$ として表現ひょうげんできず、特性方程式法とくせいほうていしきほうは一般いっぱんには成立せいりつしない。定数係数ていすうけいすうという仮定かていは、作用素さようその可換性かかんせいを保証ほしょうする本質的条件ほんしつてきじょうけんである。

14Newton の前進公式ぜんしんこうしき（ $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ ）

$Δ = E - I$ なので

E = I + Δ

である。したがって

E^{n} = (I + Δ)^{n}

である。 $I$ と $Δ$ は可換かかんなので、二項定理にこうていりより

E^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) Δ^{k}

である。

両辺りょうへんを列れつ $f$ の $0$ 番目ばんめに作用さようさせると

f (n) = (E^{n} f)_{0} = \sum_{k = 0}^{n} (\binom{n}{k}) (Δ^{k} f)_{0}

を得える。これは初期値しょきちと初期しょき差分さぶんから列れつを復元ふくげんする公式こうしきである。

15成立範囲せいりつはんい

この講義こうぎの $P (E)$ 表示ひょうじは、主おもに定数係数ていすうけいすうの線型漸化式せんけいぜんかしきに対たいして有効ゆうこうである。非線型漸化式ひせんけいぜんかしきには線型作用素方程式せんけいさようそほうていしきの構造こうぞうがない。非定数係数ひていすうけいすうの線型漸化式せんけいぜんかしきでは、係数作用素けいすうさようそとシフト作用素さようそが一般いっぱんに可換かかんでないため、通常つうじょうの特性方程式法とくせいほうていしきほうは適用てきようできない。

また、片側列かたがわれつでは $E^{- 1}$ が常つねに自然しぜんに定義ていぎできるとは限かぎらない。後退差分こうたいさぶんや両側りょうがわシフトを扱あつかうときは、列空間れつくうかんをどの添字集合そえじしゅうごう上じょうに置おくかを明示めいじする必要ひつようがある。

16主要公式しゅようこうしき

[PARSE ERROR: Undefined("Command(\"boxed\")")] (E a)_{n} = a_{n + 1}

[PARSE ERROR: Undefined("Command(\"boxed\")")] Δ = E - I

[PARSE ERROR: Undefined("Command(\"boxed\")")] Δ F = f (indefinitesumproblem)

[PARSE ERROR: Undefined("Command(\"boxed\")")] P (E) a = b (constant c o e f f i c i e n t l i n e a r r e c u r r e n c e) [PARSE ERROR: Undefined("RBrace")]

[PARSE ERROR: Undefined("Command(\"boxed\")")] E (r^{n}) = r r^{n}, P (E) (r^{n}) = P (r) r^{n}

[PARSE ERROR: Undefined("Command(\"boxed\")")] P (r) = 0 (characteristicequation)

17要約ようやく

漸化式ぜんかしきrecurrence relationは、シフト作用素さようそshift operator $E$ による線型作用素方程式せんけいさようそほうていしきlinear operator equationであり、特性とくせい方程式ほうていしきは $E$ の固有こゆう列れつ $r^{n}$ から生しょうじる。

シフト作用素さようそと漸化式ぜんかしき

1導入どうにゅう

2用語ようごと定義ていぎ

3方針ほうしん

4命題めいだい 1：EE は線型作用素せんけいさようそlinear operatorである

4.1主張しゅちょう

4.2証明しょうめい

5差分さぶんは E-IE-I である

6二項定理にこうていりによる高階差分こうかいさぶん

7和分わぶんは差分さぶんの逆問題ぎゃくもんだいである

8積せきの差分さぶんにおけるシフト項こう

9部分和公式ぶぶんわこうしきは離散版りさんばんの部分積分ぶぶんせきぶん

10漸化式ぜんかしきは P(E)a=bP(E)a=b である

11固有列こゆうれつと特性方程式とくせいほうていしき

12例れい：Fibonacci 型かた漸化式ぜんかしき

13定数係数ていすうけいすうと非定数係数ひていすうけいすうの違ちがい

14Newton の前進公式ぜんしんこうしき（n[PARSE ERROR: Undefined("Command(\"ge\")")]0n\ge0）

15成立範囲せいりつはんい

16主要公式しゅようこうしき

17要約ようやく

18関連かんれんリンク

4命題めいだい 1： $E$ は線型作用素せんけいさようそlinear operatorである

5差分さぶんは $E - I$ である

10漸化式ぜんかしきは $P (E) a = b$ である

14Newton の前進公式ぜんしんこうしき（ $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ ）