一次いちじ漸化式ぜんかしき

1導入どうにゅう

この講義こうぎでは、定数係数ていすうけいすうの一次線型漸化式いちじせんけいぜんかしきを、平衡点へいこうてんの減算げんざんによって等比数列とうひすうれつへ帰着きちゃくする方法ほうほうを説明せつめいする。

$a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q は、一般いっぱんには等差数列とうさすうれつでも等比数列とうひすうれつでもない。定数項ていすうこう $q$q の消去しょうきょと、例外れいがい $p=1$p=1 の分離ぶんりが解法かいほうの要点ようてんである。

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

この講義こうぎで扱あつかう定数係数一次線型漸化式ていすうけいすういちじせんけいぜんかしきconstant-coefficient first-order linear recurrenceとは、

の形かたちをした漸化式ぜんかしきである。ここで $p,q$p,q は定数ていすうであり、この講義こうぎでは $n\ge 1$n\geq1、初期値しょきち $a_1$a_1 を採用さいようする。$q=0$q=0 の場合ばあいは同次どうじであり、$q\ne 0$q\ne0 の場合ばあいは非同次ひどうじである。$x\mapsto px+q$x\mapsto px+q は $q\ne 0$q\ne0 のときアフィン写像しゃぞうであるが、列れつに作用さようする方程式ほうていしき $(E-pI)a=q1$(E-pI)a=q\mathbf1 は線型作用素せんけいさようそによる非同次方程式ひどうじほうていしきとして表現ひょうげんされる。

平衡点へいこうてんequilibrium point とは、

を満みたす値あたい $\alpha$\alpha である。$p\ne 1$p\ne1 の場合ばあい、

が一意いちに存在そんざいする。$p=1,q\ne 0$p=1,\ q\ne0 の場合ばあい、平衡点へいこうてんは存在そんざいしない。$p=1,q=0$p=1,\ q=0 の場合ばあい、すべての値あたいが平衡点へいこうてんである。

3方針ほうしん

まず $p=1$p=1 と $p\ne 1$p\ne1 を区別くべつする。$p=1$p=1 の場合ばあい、

であるため、$\left(a_n\right)$(a_n) は等差数列とうさすうれつである。$p\ne 1$p\ne1 の場合ばあい、平衡点へいこうてん $\alpha$\alpha が一意いちに存在そんざいするため、偏差列へんされつ $a_n-\alpha$a_n-\alpha を導入どうにゅうする。

4直感的ちょっかんてきな説明せつめい

4.11. 平衡点へいこうてんを減算げんざんする理由りゆう

平衡点へいこうてんは、更新写像こうしんしゃぞう $x\mapsto px+q$x\mapsto px+q によって不変ふへんな値あたいである。$p\ne 1$p\ne1 の場合ばあい、この点てんは一意いちに存在そんざいする。$a_n$a_n ではなく平衡点へいこうてんからの偏差へんさを対象たいしょうとすることにより、更新則こうしんそくを単純化たんじゅんかできる。

4.22. 偏差列へんされつの等比性とうひせい

平衡点へいこうてんからの偏差へんさは、添字そえじが 1 増加ぞうかするごとに $p$p 倍ばいされる。したがって、$p\ne 1$p\ne1 の一次漸化式いちじぜんかしきは偏差列へんされつの等比性とうひせいによって解決かいけつできる。$p=1$p=1 の場合ばあいには、前進差分ぜんしんさぶんが定数ていすうとなる。

5厳密げんみつな説明せつめい

5.1命題めいだい 1：$$p\ne 1$$p\ne1 の場合ばあい

仮定かてい：$n\ge 1$n\geq1 において $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q、$p\ne 1$p\ne1 とし、初期値しょきちを $a_1$a_1 とする。

結論けつろん：$$\alpha =\text{[PARSE ERROR: Undefined("Command("dfrac")")]}q1-p$$\alpha=\dfrac{q}{1-p} と定義ていぎすると、

である。

証明しょうめい：

を対象たいしょうとする。$\alpha$\alpha を

を満みたす定数ていすうとする。

ここで

と定義ていぎすると、

である。元もとの漸化式ぜんかしきを代入だいにゅうすると、

である。さらに $\alpha =p\alpha +q$\alpha=p\alpha+q より $q=\alpha -p\alpha$q=\alpha-p\alpha であるから、

となる。したがって $$b_n$$b_n は等比数列とうひすうれつで、

である。$b_1=a_1-\alpha$b_1=a_1-\alpha であるから、

を得える。

5.2命題めいだい 2：$$p=1$$p=1 の場合ばあい

仮定かてい：$n\ge 1$n\geq1 において $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q、$p=1$p=1 とし、初期値しょきちを $a_1$a_1 とする。

結論けつろん：

である。

証明しょうめい：$p=1$p=1 であるから、元もとの漸化式ぜんかしきは

である。したがって

である。$N\ge 2$N\geq2 とし、両辺りょうへんを $n=1,2,\dots ,N-1$n=1,2,\ldots,N-1 について総和そうわすると、

となる。左辺さへんは望遠和ぼうえんわとなり、

である。したがって、

である。$N=1$N=1 では公式こうしきが初期条件しょきじょうけん $a_1=a_1$a_1=a_1 と一致いっちする。したがって、任意にんいの $n\ge 1$n\geq1 について結論けつろんを得える。

6具体例ぐたいれい

具体例ぐたいれいとして、

を対象たいしょうとする。平衡点へいこうてん $\alpha$\alpha は

より

である。この平衡点へいこうてんに基もとづき、

と定義ていぎすると、

である。

したがって $b_n$b_n は公比こうひ 2 の等比数列とうひすうれつである。$b_1=4$b_1=4 であるから、

である。したがって、

となる。

7数学的すうがくてきな解釈かいしゃく

7.1代数的だいすうてきな解釈かいしゃく

一次漸化式いちじぜんかしきは、平衡点へいこうてんを原点げんてんとする座標ざひょうへ移行いこうすることにより、定数項ていすうこうを消去しょうきょして同次化どうじかできる。

この座標変換ざひょうへんかんにより、高等学校数学こうとうがっこうすうがくの標準解法ひょうじゅんかいほうを、非同次方程式ひどうじほうていしきの同次化どうじかという代数操作だいすうそうさとして整理せいりできる。

7.2作用素さようそによる解釈かいしゃく

添字そえじを 1 増加ぞうかさせるシフト作用素さようそshift operator $E$E を $(Ea{)}_n=a_{n+1}$(Ea)_n=a_{n+1} と定義ていぎすると、一次漸化式いちじぜんかしき

は

と表現ひょうげんできる。ここで $1$\mathbf 1 はすべての項こうが 1 の定数列ていすうれつである。

この式しきは、線型作用素方程式せんけいさようそほうていしきlinear operator equation

の形かたちである。ただし $L=E-pI$L=E-pI、$y=q1$y=q\mathbf 1 である。平衡点へいこうてん $\alpha$\alpha の決定けっていは、定数列ていすうれつ $a_n=\alpha$a_n=\alpha という特解とくかいの決定けっていに対応たいおうする。実際じっさい、$a_n=\alpha$a_n=\alpha の場合ばあい、

である。したがって $p\ne 1$p\ne1 のとき、$(1-p)\alpha =q$(1-p)\alpha=q となるように $\alpha$\alpha を選択せんたくすれば、$a_n=\alpha$a_n=\alpha は非同次方程式ひどうじほうていしきの特解とくかいである。$p=1,q\ne 0$p=1,\ q\ne0 のときは定数列ていすうれつの特解とくかいがないため、$\mathrm{\Delta }a=q$\Delta a=q という差分方程式さぶんほうていしきとして処理しょりする。

続つづいて $b_n=a_n-\alpha$b_n=a_n-\alpha と定義ていぎすると、$b$b は

を満みたす。この作用素さようその核かくは、添字領域そえじりょういきにおいて $b_{n+1}=p{b}_n$b_{n+1}=pb_n を満みたす等比数列とうひすうれつの全体ぜんたいである。

7.3線形代数的せんけいだいすうてきな解釈かいしゃく

$a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q は線形写像せんけいしゃぞうではなくアフィン変換へんかんである。定数座標ていすうざひょう 1 を付加ふかすると、

と表現ひょうげんでき、2 次元じげんの線形変換せんけいへんかんへ埋うめ込こまれる。

このとき

が

を満みたす条件じょうけんは、$\alpha =p\alpha +q$\alpha=p\alpha+q と同値どうちである。したがって、平衡点へいこうてんが存在そんざいする場合ばあい、$(\alpha ,1{)}^{\mathsf{T}}$(\alpha,1)^\mathsf T は固有値こゆうち 1 に属ぞくする固有こゆうベクトルである。

平衡点へいこうてんの減算げんざんは、座標原点ざひょうげんてんを不動点ふどうてんへ移動いどうし、偏差座標へんさざひょうにおける変換へんかんを単純化たんじゅんかする操作そうさである。

7.4解析学的かいせきがくてきな解釈かいしゃく

$a_{n+1}-a_n$a_{n+1}-a_n を離散的りさんてきな変化量へんかりょうと解釈かいしゃくすると、一次漸化式いちじぜんかしきは微分方程式びぶんほうていしき

の離散的対応物りさんてきたいおうぶつである。いずれも平衡点へいこうてんの減算げんざんによって同次化どうじかできるが、離散系りさんけいと連続系れんぞくけいの解公式かいこうしきは区別くべつされる。

この対応たいおうにより、離散系りさんけいと連続系れんぞくけいにおける平衡点近傍へいこうてんきんぼうの構造こうぞうを比較ひかくできる。

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

平衡点へいこうてんの減算げんざんは、$a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q かつ $p\ne 1$p\ne1 の場合ばあいに有効ゆうこうである。$p=1$p=1 では定数差分ていすうさぶんを総和そうわする。非線形漸化式ひせんけいぜんかしきまたは変数係数漸化式へんすうけいすうぜんかしきには、これらの命題めいだいを変更へんこうせずに適用てきようすることはできない。

9基本公式きほんこうしき

$$p\ne 1$$p\ne1 のとき：

$$p=1$$p=1 のとき：

10要約ようやく

• 一次漸化式いちじぜんかしきでは、まず $p=1$p=1 と $p\ne 1$p\ne1 を区別くべつする。
• $p\ne 1$p\ne1 の場合ばあい、平衡点へいこうてんを減算げんざんして等比数列とうひすうれつへ帰着きちゃくする。
• $p=1$p=1 の場合ばあい、定数差分ていすうさぶんを総和そうわして等差数列とうさすうれつとして処理しょりする。

11関連かんれんリンク

関連かんれん講義こうぎ・関連かんれんノート

First-Order Recurrences

1Introduction

This lecture explains how to reduce a constant-coefficient first-order linear recurrence to a geometric sequence by subtracting an equilibrium point. The exceptional case $p=1$p=1 is treated separately.

The recurrence $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q is generally neither arithmetic nor geometric. Its solution depends on eliminating the constant term $q$q when $p\ne 1$p\ne1, or summing its constant forward difference when $p=1$p=1.

2Terminology and Definitions

A constant-coefficient first-order linear recurrence has the form

where $p$p and $q$q are constants. Throughout this lecture, $n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$n\ge1 and the initial value is $a_1$a_1. The equation is homogeneous when $q=0$q=0 and nonhomogeneous when $q\ne 0$q\ne0. Although the update map $x\mapsto px+q$x\mapsto px+q is affine for $q\ne 0$q\ne0, the sequence equation $(E-pI)a=q1$(E-pI)a=q\mathbf1 is a nonhomogeneous equation with a linear operator on the left-hand side.

An equilibrium point is a value $\alpha$\alpha satisfying

For $p\ne 1$p\ne1, the unique equilibrium is $\alpha =q/(1-p)$\alpha=q/(1-p). For $p=1$p=1 and $q\ne 0$q\ne0, no equilibrium exists; for $p=1$p=1 and $q=0$q=0, every value is an equilibrium.

3Program

First distinguish $p=1$p=1 from $p\ne 1$p\ne1. If $p=1$p=1, then $a_{n+1}-a_n=q$a_{n+1}-a_n=q, so the sequence is arithmetic. If $p\ne 1$p\ne1, introduce the displacement $a_n-\alpha$a_n-\alpha from the unique equilibrium.

4Informal Explanation

4.11. Why the Equilibrium Is Subtracted

An equilibrium is invariant under the update map $x\mapsto px+q$x\mapsto px+q. Measuring the displacement from this value removes the translation term and simplifies the update rule.

4.22. The Geometric Displacement Sequence

The displacement from equilibrium is multiplied by $p$p at every step. Thus the $p\ne 1$p\ne1 recurrence contains a geometric sequence after translation. When $p=1$p=1, its forward difference itself is constant.

5Formal Development

5.1Proposition 1: The Case $p\ne 1$p\ne1

Assumptions: For $n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$n\ge1, let $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q with $p\ne 1$p\ne1.

Conclusion: With $\alpha =q/(1-p)$\alpha=q/(1-p),

Proof: The equilibrium identity is $\alpha =p\alpha +q$\alpha=p\alpha+q. Define $b_n=a_n-\alpha$b_n=a_n-\alpha. Then

Hence $\left(b_n\right)$(b_n) is geometric and

Adding $\alpha$\alpha proves the formula.

5.2Proposition 2: The Case $p=1$p=1

Assumptions: For $n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$n\ge1, let $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q with $p=1$p=1.

Conclusion:

Proof: The recurrence becomes $a_{n+1}-a_n=q$a_{n+1}-a_n=q. For $N\text{[PARSE ERROR: Undefined("Command("ge")")]}2$N\ge2, summing from $n=1$n=1 to $N-1$N-1 gives

so telescoping yields $a_N-a_1=(N-1)q$a_N-a_1=(N-1)q. For $N=1$N=1, the formula reduces to the initial condition $a_1=a_1$a_1=a_1. Therefore the conclusion holds for every $n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$n\ge1.

6Example

Consider

The equilibrium satisfies $\alpha =2\alpha +3$\alpha=2\alpha+3, hence $\alpha =-3$\alpha=-3. Set $b_n=a_n+3$b_n=a_n+3. Then

Since $b_1=4$b_1=4, one has $b_n=4·2^{n-1}=2^{n+1}$b_n=4\cdot2^{n-1}=2^{n+1} and therefore

7Mathematical Interpretations

7.1Algebraic Interpretation

Translation of the coordinate origin to the equilibrium eliminates the constant term. The standard solution method taught in secondary-school mathematics is therefore an algebraic homogenization procedure.

7.2Operator Interpretation

Define the forward shift by $(Ea{)}_n=a_{n+1}$(Ea)_n=a_{n+1}. Then

where $1$\mathbf1 is the constant sequence with every term equal to one. This is a linear operator equation $La=y$La=y, with $L=E-pI$L=E-pI and $y=q1$y=q\mathbf1.

For $p\ne 1$p\ne1, the constant sequence $a_n=\alpha$a_n=\alpha is a particular solution exactly when $(1-p)\alpha =q$(1-p)\alpha=q. Subtracting this particular solution gives

whose kernel consists of geometric sequences satisfying $b_{n+1}=p{b}_n$b_{n+1}=pb_n on the index domain. If $p=1$p=1 and $q\ne 0$q\ne0, there is no constant particular solution, and the equation is instead $\mathrm{\Delta }a=q$\Delta a=q with $\mathrm{\Delta }=E-I$\Delta=E-I.

7.3Linear-Algebraic Interpretation

The affine recurrence can be embedded in a two-dimensional linear transformation:

An equilibrium satisfies

Thus $(\alpha ,1{)}^{\mathsf{T}}$(\alpha,1)^{\mathsf T} is an eigenvector with eigenvalue $1$1. Translation to the equilibrium separates the affine fixed point from multiplication by $p$p in the displacement coordinate.

7.4Analytic Interpretation

The increment $a_{n+1}-a_n$a_{n+1}-a_n is the discrete change measure, so the recurrence is structurally analogous to the differential equation $y^{\prime }=cy+d$y'=cy+d. Both become homogeneous after subtraction of an equilibrium, although their discrete and continuous solution formulas remain distinct.

This correspondence permits comparison of the local structure near an equilibrium in discrete and continuous systems.

8Scope

Equilibrium subtraction applies to $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q when $p\ne 1$p\ne1. For $p=1$p=1, sum the constant forward differences. Variable-coefficient or nonlinear recurrences require other methods, so neither proposition applies to them without modification.

9Basic Formulas

For $p\ne 1$p\ne1,

For $p=1$p=1,

10Summary

• First determine whether $p=1$p=1.
• If $p\ne 1$p\ne1, subtract the equilibrium and solve the resulting geometric recurrence.
• If $p=1$p=1, sum the constant forward differences.

11Related Lectures