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

1導入どうにゅう

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

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

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

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

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

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

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

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

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

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

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

である。$p\ne 1$p\ne1 なら平衡点へいこうてん $\alpha =q/(1-p)$\alpha=q/(1-p) を定義ていぎし、$b_n=a_n-\alpha$b_n=a_n-\alpha とする。$\alpha =p\alpha +q$\alpha=p\alpha+q より

したがって、

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

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

$p\ne 0$p\ne0 かつ $a_{n+1}=p{a}_n+f\left(n\right)$a_{n+1}=pa_n+f(n) とする。$b_n=a_n/p^{n-1}$b_n=a_n/p^{n-1} と定義ていぎすると、

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

メビウス型がた $T\left(x\right)=(Ax+B)/(Cx+D)$T(x)=(Ax+B)/(Cx+D) で $AD-BC\ne 0$AD-BC\ne0 とし、相異そういなる有限固定点ゆうげんこていてん $\alpha ,\beta$\alpha,\beta があり、分母ぶんぼおよび $a_n-\beta$a_n-\beta が非零ひれいであるとする。このとき、ある定数ていすう $\rho$\rho により

が成立せいりつするため、$z_n=(a_n-\alpha )/(a_n-\beta )$z_n=(a_n-\alpha)/(a_n-\beta) は等比数列とうひすうれつとなる。

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

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

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

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

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

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

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

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

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

13関連講義かんれんこうぎ

Types of Recurrences and Solution Strategies

1Introduction

Solving a recurrence begins by identifying its order and algebraic structure rather than by selecting a memorized formula. This lecture then reduces each principal type to a simpler sequence or operator equation.

2Classification Terminology

For a recurrence that determines $a_{n+k}$a_{n+k} from $a_n,\dots ,a_{n+k-1}$a_n,\ldots,a_{n+k-1}, its {order} is the largest index gap actually required. Thus $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q has order one. The recurrence $a_{n+2}=s{a}_{n+1}+t{a}_n$a_{n+2}=sa_{n+1}+ta_n has order two when $t\ne 0$t\ne0 and drops to order one when $t=0$t=0.

A {linear recurrence} is a linear combination of shifts of the unknown sequence whose coefficients and right-hand side are independent of that sequence. Products of unknown terms, powers, and nonlinear functions of unknown terms are excluded. A standard constant-coefficient form is

When $c_k\ne 0$c_k\ne0, this is order $k$k in the direction of increasing indices. It is homogeneous when $f=0$f=0 and nonhomogeneous when $f\ne 0$f\ne0. With the shift operator $(Ea{)}_n=a_{n+1}$(Ea)_n=a_{n+1}, this equation is $P\left(E\right)a=f$P(E)a=f.

3Decision Procedure

4Proposition 1: Summing Differences

If $a_{n+1}-a_n=f\left(n\right)$a_{n+1}-a_n=f(n) for $n\ge 1$n\geq1, then

For $n=1$n=1, the empty sum is zero. For $n\ge 2$n\geq2, summing the assumption over $k=1,\dots ,n-1$k=1,\ldots,n-1 makes the left side telescope to $a_n-a_1$a_n-a_1. The case $f\left(n\right)=d$f(n)=d gives an arithmetic sequence.

5Proposition 2: First-Order Nonhomogeneous Form

Suppose $a_{n+1}=p{a}_n+q$a_{n+1}=pa_n+q. If $p=1$p=1, Proposition 1 gives $a_n=a_1+(n-1)q$a_n=a_1+(n-1)q. If $p\ne 1$p\ne1, define the equilibrium $\alpha =q/(1-p)$\alpha=q/(1-p) and put $b_n=a_n-\alpha$b_n=a_n-\alpha. Since $\alpha =p\alpha +q$\alpha=p\alpha+q,

Therefore

Separating $p=1$p=1 is essential because it prevents division by zero.

6Proposition 3: Variation of Constants

Assume $p\ne 0$p\ne0 and $a_{n+1}=p{a}_n+f\left(n\right)$a_{n+1}=pa_n+f(n). Defining $b_n=a_n/p^{n-1}$b_n=a_n/p^{n-1} gives

Proposition 1 therefore yields

When $p=0$p=0, the relation $a_{n+1}=f\left(n\right)$a_{n+1}=f(n) determines $a_2,a_3,\dots$a_2,a_3,\ldots directly and must be treated separately.

7Proposition 4: Difference Sequences

Suppose $a_{n+2}-a_{n+1}=r(a_{n+1}-a_n)$a_{n+2}-a_{n+1}=r(a_{n+1}-a_n) and define $b_n=a_{n+1}-a_n$b_n=a_{n+1}-a_n. Then $b_{n+1}=r{b}_n$b_{n+1}=rb_n, so $b_n=(a_2-a_1)r^{n-1}$b_n=(a_2-a_1)r^{n-1}. Proposition 1 gives

The sum is $n-1$n-1 when $r=1$r=1 and $(1-r^{n-1})/(1-r)$(1-r^{n-1})/(1-r) when $r\ne 1$r\ne1.

8Proposition 5: Second-Order Constant-Coefficient Linear Form

Over a field $K$K, consider

If $t=0$t=0, the order drops. In particular, if $s=t=0$s=t=0, then $a_{n+2}=0$a_{n+2}=0; the values $a_1,a_2$a_1,a_2 are arbitrary and $a_n=0$a_n=0 for $n\ge 3$n\geq3. Henceforth assume $t\ne 0$t\ne0, and let $\chi \left(x\right)=x^2-sx-t$\chi(x)=x^2-sx-t be the characteristic polynomial. If $\chi$\chi has distinct roots $\alpha$\alpha and $\beta$\beta in a splitting field $L$L, every $L$L-valued solution has the form

Substitution shows that each component satisfies the recurrence. Unique constants $A,B$A,B match $a_1,a_2$a_1,a_2. The difference from any other solution then has two initial zeros, and induction using the recurrence makes every term zero; hence this is the complete solution.

If $\chi$\chi has a nonzero repeated root $\alpha$\alpha, every solution has the form

This follows by checking that $(E-\alpha I{)}^2$(E-\alpha I)^2 annihilates both ${\alpha }^{n-1}$\alpha^{n-1} and $(n-1){\alpha }^{n-1}$(n-1)\alpha^{n-1} and then using the same uniqueness argument.

9Higher Order and State Vectors

A constant-coefficient homogeneous linear recurrence of order $k$k can be written as $P\left(E\right)a=0$P(E)a=0. A nonzero characteristic root $\lambda$\lambda of multiplicity $m$m produces solutions corresponding to ${\lambda }^n,n{\lambda }^n,\dots ,n^{m-1}{\lambda }^n$\lambda^n,n\lambda^n,\ldots,n^{m-1}\lambda^n. A zero root concerns a drop in order or a finite initial segment and must be handled from the original recurrence and initial values. A complete statement must specify a field over which $P$P splits.

An order-$k$k constant-coefficient homogeneous linear recurrence can be converted to a first-order matrix recurrence by introducing $v_n=(a_{n+k-1},\dots ,a_n{)}^{\mathsf{T}}$v_n=(a_{n+k-1},\ldots,a_n)^\mathsf T and writing $v_{n+1}=M{v}_n$v_{n+1}=Mv_n. This does not erase the order; it packages the preceding $k$k terms into one state.

10Additional Types

If a relation contains the partial sum $S_n=\sum _{j=1}^n{a}_j$S_n=\sum_{j=1}^n a_j, subtract its equation at $n$n from its equation at $n+1$n+1 and use $S_{n+1}-S_n=a_{n+1}$S_{n+1}-S_n=a_{n+1} to eliminate the partial sum.

The product form $a_{n+1}=r_n{a}_n$a_{n+1}=r_na_n gives $a_n=a_1\prod _{j=1}^{n-1}{r}_j$a_n=a_1\prod_{j=1}^{n-1}r_j. The reciprocal form $1/a_{n+1}=1/a_n+d$1/a_{n+1}=1/a_n+d reduces to an arithmetic sequence under $b_n=1/a_n$b_n=1/a_n, provided every term involved is nonzero.

Suppose the Möbius map $T\left(x\right)=(Ax+B)/(Cx+D)$T(x)=(Ax+B)/(Cx+D) satisfies $AD-BC\ne 0$AD-BC\ne0 and has distinct finite fixed points $\alpha ,\beta$\alpha,\beta, and the denominators and $a_n-\beta$a_n-\beta are nonzero. Then some constant $\rho$\rho satisfies

so $z_n=(a_n-\alpha )/(a_n-\beta )$z_n=(a_n-\alpha)/(a_n-\beta) is geometric.

A linear system $w_{n+1}=M{w}_n$w_{n+1}=Mw_n is a matrix iteration of a state vector. For the symmetric two-variable system

the variables $u_n=x_n+y_n$u_n=x_n+y_n and $v_n=x_n-y_n$v_n=x_n-y_n separate it into $u_{n+1}=(a+b)u_n$u_{n+1}=(a+b)u_n and $v_{n+1}=(a-b)v_n$v_{n+1}=(a-b)v_n.

For an integer sequence satisfying $q_n\in \mathbb{Z}$q_n\in\mathbb Z and $a_{n+1}=a_{n-1}+q_n{a}_n$a_{n+1}=a_{n-1}+q_na_n,

This is invariance of the gcd of adjacent terms under $\text{[PARSE ERROR: Undefined("Command("gcd")")]}(x+qy,y)=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(x,y)$\gcd(x+qy,y)=\gcd(x,y).

11Problems Asking for Properties

A general term is not always necessary. Reducing an integer-coefficient recurrence modulo $m$m produces finitely many residue states. Inequalities and invariant intervals can be proved by induction: verify the initial condition and derive the property of $a_{n+1}$a_{n+1} from that of $a_n$a_n through the update rule.

For a problem asking about a limit, merely identifying a fixed-point candidate does not prove convergence. Limits, continuity, monotonicity, and boundedness are treated rigorously in the subsequent lecture.

12Scope

A ratio-based test requires nonzero denominators, variation of constants requires $p\ne 0$p\ne0, and the equilibrium method requires $p\ne 1$p\ne1. For nonlinear recurrences, transformations involving reciprocals, logarithms, or ratios of differences from fixed points may be effective, but their domains and invertibility must be checked individually.

13Related Lectures