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