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