Shift Operators and Recurrence Relations

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

mathsequencerecurrenceshift-operatorlinear-operatorlecture

1Introduction

This lecture unifies differences, indefinite sums, and recurrences through the forward shift operator

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

A constant-coefficient linear recurrence then becomes the linear operator equation $P (E) a = b$ .

2Terminology and Definitions

Work with bilateral sequences indexed by $Z$ or unilateral sequences indexed by $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ , as specified. Define

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

and the forward difference

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

This convention agrees with the Z-transform lecture: the bilateral transform maps $E$ to multiplication by $z$ .

3Program

The development proceeds by proving linearity of $E$ , deriving difference identities from $Δ = E - I$ , treating $Δ F = f$ as an inverse problem, expressing recurrences as $P (E) a = b$ , and deriving the characteristic equation from the eigen-sequence $r^{n}$ .

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

4Proposition 1: $E$ Is a Linear Operator

4.1Statement

The shift $E$ is linear on the sequence space.

4.2Proof

For sequences $a, b$ and scalars $α, β$ ,

\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}

The identity holds for every admissible $n$ , hence $E (α a + β b) = α E a + β E b$ . $□$

5The Difference Is $E - I$

Since

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

$Δ = E - I$ . Therefore $Δ$ is linear as the difference of linear operators:

Δ (α a + β b) = α Δ a + β Δ b .

6Higher Differences from the Binomial Theorem

Because $E$ and $I$ commute,

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

Consequently,

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

Thus the signs and indices follow directly from the operator binomial expansion.

7Indefinite Summation as the Inverse Difference Problem

An indefinite sum seeks $F$ satisfying $Δ F = f$ , or $F (n + 1) - F (n) = f (n)$ . Summing from $n = a$ to $b - 1$ telescopes:

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

This is the discrete counterpart of $\int_{a}^{b} F^{'} (x) d x = F (b) - F (a)$ .

8The Shift Term in a Product Difference

Direct calculation gives

\begin{aligned} \Delta(uv)(n) &=u(n+1)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)\\ &=v(n+1)(u(n+1)-u(n))+u(n)(v(n+1)-v(n)), \end{aligned}

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

The shift $E v$ cannot be omitted by copying the continuous product rule.

9Summation by Parts Is Discrete Integration by Parts

Rearranging the product rule gives $u Δ v = Δ (u v) - (E v) Δ u$ . Indefinite summation yields

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

the discrete counterpart of $\int u d v = u v - \int v d u$ . The one-step shift explains why the shift operator must remain explicit.

On a finite range, the precise boundary formula is

\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) .

10A Recurrence Is $P (E) a = b$

For

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

define $P (t) = t^{k} - c_{1} t^{k - 1} - \dots - c_{k}$ . Then

P (E) a = b .

The operator equation is solvable exactly when $b \in Im P (E)$ . If $a_{p}$ is one solution, every solution is

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

11Eigen-Sequences and the Characteristic Equation

For bilateral sequences assume $r \neq 0$ ; for unilateral sequences define $r^{n}$ on $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ . The geometric sequence satisfies

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

so it is an eigen-sequence of $E$ with eigenvalue $r$ . Hence

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

It solves $P (E) a = 0$ precisely when $P (r) = 0$ . The characteristic-equation method is therefore the discrete eigenvalue method for constant-coefficient linear recurrences.

12Example: A Fibonacci-Type Recurrence

The recurrence $f_{n + 2} = f_{n + 1} + f_{n}$ is

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

Its characteristic polynomial is $P (t) = t^{2} - t - 1$ , with roots

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

The sequences $r_{1^{n}}$ and $r_{2^{n}}$ are linearly independent. Moreover, a solution of this second-order recurrence is uniquely determined by the two initial values $f_{0}, f_{1}$ , so its solution space is two-dimensional. Hence these sequences form a basis and

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

and initial conditions determine $C_{1}, C_{2}$ . The geometric trial sequences are justified because they are eigen-sequences of $E$ .

13Constant and Nonconstant Coefficients

Constant coefficients commute with $E$ , allowing the polynomial $P (E)$ . For the variable-coefficient recurrence $a_{n + 1} - n a_{n} = 0$ , define $(M a)_{n} = n a_{n}$ . The equation is $(E - M) a = 0$ , but

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

so $E M \neq M E$ . Thus the ordinary polynomial calculus and simple characteristic equation generally fail for nonconstant coefficients. Constancy is an essential commutativity hypothesis.

14Newton's Forward Formula ( $n [PARSE ERROR: Undefined("Command(\"ge\")")] 0$ )

Since $E = I + Δ$ and the operators commute,

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

Applying both sides to the zeroth entry of $f$ gives

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

which reconstructs a sequence from its initial forward differences.

15Scope

The representation $P (E) a = b$ applies primarily to constant-coefficient linear recurrences. Nonlinear recurrences lack this linear operator structure; variable coefficients generally do not commute with $E$ , so the usual characteristic method is unavailable.

On unilateral sequence spaces, $E^{- 1}$ need not have a natural definition. Any use of backward differences or bilateral shifts must specify the index set of the sequence space.

16Canonical Formulas

[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) .

17Summary

A recurrence relation is a linear operator equation in the shift $E$ when it is linear with constant coefficients. Its characteristic equation arises from the eigen-sequences $r^{n}$ of $E$ .

18Related Lectures

data/lecture/math/analysis/introduction-to-z-transform.lecture.n.md data/lecture/math/sequence/sequences-and-recurrences.lecture.n.md data/lecture/math/sequence/recurrence-types-and-strategies.lecture.n.md data/lecture/math/sequence/first-order-recurrences.lecture.n.md data/lecture/math/sequence/difference-equation-basics.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