The Central Idea

A recurrence relation connects a term of a sequence with earlier terms.

A linear recurrence relation does this through a linear combination.

For example,

\[ \boxed{a_n=3a_{n-1}-2a_{n-2}} \]

is linear because the earlier terms appear only to the first power and are multiplied by coefficients.

The recurrence

\[ a_n=(a_{n-1})^2+a_{n-2} \]

is not linear because \(a_{n-1}\) is squared.

Linear Combination of Earlier Terms

A linear combination has the form

\[ c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}, \]

where the \(c_i\) are coefficients.

A general linear recurrence may be written

\[ \boxed{ a_n = c_1a_{n-1} + c_2a_{n-2} +\cdots+ c_ka_{n-k} + g(n) }. \]

The term \(g(n)\) represents an optional input depending on the index.

First-Order Linear Recurrences

A first-order linear recurrence depends only on the immediately preceding term.

A common form is

\[ \boxed{a_n=ca_{n-1}+g(n)}. \]

For example,

\[ a_n=2a_{n-1}+3 \]

is first order and linear.

Second-Order Linear Recurrences

A second-order linear recurrence reaches back two positions.

A common form is

\[ \boxed{a_n=c_1a_{n-1}+c_2a_{n-2}+g(n)}. \]

For example,

\[ a_n=4a_{n-1}-a_{n-2} \]

is second order.

Higher-Order Linear Recurrences

A recurrence can depend on three or more earlier positions.

For example,

\[ a_n=2a_{n-1}+a_{n-2}-5a_{n-3} \]

reaches back to \(a_{n-3}\), so it is third order.

The order is determined by the most distant previous term that appears with a nonzero coefficient.

Order and Initial Conditions

The order of a recurrence determines how much starting information is normally required for forward evaluation.

A first-order recurrence typically needs one initial value.

A second-order recurrence typically needs two initial values.

A \(k\)th-order recurrence typically needs \(k\) consecutive initial values.

For example,

\[ a_n=2a_{n-1}-a_{n-2} \]

can be evaluated forward once values such as

\[ a_1,\qquad a_2 \]

are known.

Example: Evaluate a First-Order Linear Recurrence

Let

\[ a_1=2, \] \[ a_n=3a_{n-1}+1\qquad(n\ge2). \]

Then

\[ a_2=3(2)+1=7, \] \[ a_3=3(7)+1=22, \] \[ a_4=3(22)+1=67. \]

Therefore,

\[ \boxed{2,\ 7,\ 22,\ 67,\ldots}. \]

Example: Evaluate a Second-Order Linear Recurrence

Let

\[ a_1=1,\qquad a_2=3, \] \[ a_n=2a_{n-1}+a_{n-2}\qquad(n\ge3). \]

Then

\[ a_3=2(3)+1=7, \] \[ a_4=2(7)+3=17, \] \[ a_5=2(17)+7=41. \]

Thus,

\[ \boxed{1,\ 3,\ 7,\ 17,\ 41,\ldots}. \]

Coefficients in a Linear Recurrence

In

\[ a_n=5a_{n-1}-3a_{n-2}, \]

the coefficients are

\[ \boxed{5\text{ and }-3}. \]

The coefficient \(5\) multiplies the immediately preceding term, and the coefficient \(-3\) multiplies the term two positions back.

Zero Coefficients

A previous position may formally have coefficient \(0\).

For example,

\[ a_n=2a_{n-1}+0a_{n-2}+4a_{n-3}. \]

This is still third order because the recurrence reaches back to \(a_{n-3}\).

The missing \(a_{n-2}\) term is equivalent to assigning it coefficient \(0\).

Constant-Coefficient Linear Recurrences

A recurrence has constant coefficients when the coefficients multiplying earlier terms do not depend on \(n\).

For example,

\[ \boxed{a_n=3a_{n-1}-2a_{n-2}} \]

has constant coefficients \(3\) and \(-2\).

The recurrence

\[ a_n=na_{n-1}+a_{n-2} \]

is still linear, but its coefficient \(n\) varies with the index.

Variable-Coefficient Linear Recurrences

A recurrence can remain linear even when its coefficients depend on the index.

For example,

\[ \boxed{a_n=na_{n-1}+(n-1)a_{n-2}} \]

is linear because \(a_{n-1}\) and \(a_{n-2}\) still appear only to the first power and are not multiplied together.

The coefficients are simply functions of \(n\).

Homogeneous Linear Recurrences

A linear recurrence is called homogeneous when there is no additional term independent of the sequence values.

For example,

\[ \boxed{a_n=4a_{n-1}-4a_{n-2}} \]

is homogeneous.

Every term on the right is built from earlier sequence terms.

Nonhomogeneous Linear Recurrences

A linear recurrence is called nonhomogeneous when an additional forcing or input term appears.

For example,

\[ \boxed{a_n=2a_{n-1}+5} \]

is nonhomogeneous because of the constant input \(5\).

Likewise,

\[ a_n=3a_{n-1}-a_{n-2}+n \]

is nonhomogeneous because of the added term \(n\).

The Forcing Term

In a nonhomogeneous recurrence

\[ a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+g(n), \]

the expression

\[ \boxed{g(n)} \]

is often called a forcing term or input term.

It represents something added to the system from outside the dependence on previous sequence values.

Example: Constant Forcing

Let

\[ a_0=10, \] \[ a_n=2a_{n-1}+3\qquad(n\ge1). \]

Then

\[ a_1=2(10)+3=23, \] \[ a_2=2(23)+3=49, \] \[ a_3=2(49)+3=101. \]

The repeated contribution \(3\) acts as a constant external input at every step.

Example: Index-Dependent Forcing

Let

\[ a_0=1, \] \[ a_n=a_{n-1}+n\qquad(n\ge1). \]

Then

\[ a_1=1+1=2, \] \[ a_2=2+2=4, \] \[ a_3=4+3=7, \] \[ a_4=7+4=11. \]

The added input changes with the index.

Arithmetic Recurrences Are Linear

The arithmetic recurrence

\[ a_n=a_{n-1}+d \]

is a first-order nonhomogeneous linear recurrence.

It can be written

\[ \boxed{a_n=1\cdot a_{n-1}+d}. \]

The coefficient of \(a_{n-1}\) is \(1\), and the constant forcing term is \(d\).

Geometric Recurrences Are Linear

The geometric recurrence

\[ a_n=ra_{n-1} \]

is a first-order homogeneous linear recurrence.

The coefficient is the common ratio \(r\).

Thus, arithmetic and geometric recurrences fit naturally into the broader framework of linear recurrence relations.

Fibonacci-Type Structure Is Linear

The recurrence

\[ a_n=a_{n-1}+a_{n-2} \]

is a second-order homogeneous linear recurrence.

Its coefficients are

\[ 1\qquad\text{and}\qquad1. \]

Different initial conditions produce different Fibonacci-type sequences.

Recognizing a Nonlinear Recurrence

A recurrence is not linear if sequence terms are multiplied together, raised to nonlinear powers, placed inside nonlinear functions, or otherwise combined nonlinearly.

Examples include

\[ a_n=(a_{n-1})^2+1, \] \[ a_n=a_{n-1}a_{n-2}, \] \[ a_n=\sqrt{a_{n-1}}+2. \]

Each fails the linear-combination requirement.

Linearity Refers to the Terms, Not Necessarily to \(n\)

Consider

\[ a_n=n^2a_{n-1}+\sin(n). \]

The recurrence is linear in the sequence values because \(a_{n-1}\) appears to the first power and is multiplied only by a coefficient depending on \(n\).

The functions \(n^2\) and \(\sin(n)\) do not make the recurrence nonlinear in \(a_n\).

Standard Form

A linear recurrence can often be rearranged so all sequence terms appear on one side.

For example,

\[ a_n=3a_{n-1}-2a_{n-2} \]

can be written

\[ \boxed{a_n-3a_{n-1}+2a_{n-2}=0}. \]

This form will become useful when later methods analyze the algebraic structure of recurrence relations.

Nonhomogeneous Standard Form

The recurrence

\[ a_n=2a_{n-1}+n \]

can be written

\[ \boxed{a_n-2a_{n-1}=n}. \]

The left side contains the linear recurrence operator, while the right side contains the forcing term.

Forward Evaluation Is Algorithmic

Once enough initial values are known, a recurrence gives a direct procedure for generating later terms.

Suppose

\[ a_1=2,\qquad a_2=4, \] \[ a_n=3a_{n-1}-2a_{n-2}. \]

Then

\[ a_3=3(4)-2(2)=8, \] \[ a_4=3(8)-2(4)=16, \] \[ a_5=3(16)-2(8)=32. \]

The recurrence acts like an algorithm that updates the sequence one index at a time.

State Information for Second-Order Recurrences

For a second-order recurrence, the next term depends on the two most recent terms.

Therefore, a useful state description is

\[ \boxed{(a_{n-1},a_n)}. \]

If

\[ a_{n+1}=2a_n+a_{n-1}, \]

then the pair

\[ (a_{n-1},a_n) \]

contains everything needed to produce the next pair.

Example: State Transition

Suppose

\[ a_{n+1}=a_n+a_{n-1} \]

with initial state

\[ (a_1,a_2)=(2,3). \]

Then

\[ (2,3)\longrightarrow(3,5) \]

because

\[ 5=3+2. \]

Next,

\[ (3,5)\longrightarrow(5,8). \]

This perspective prepares for later work with iteration and state transitions.

Linear Recurrences in Modeling

Linear recurrences can describe systems in which the next state is built from weighted contributions of previous states and new inputs.

Examples include:

Example: Balance with Growth and Deposits

Suppose an account earns \(2\%\) per period and receives a deposit of \(\$100\) at the end of each period.

Let \(B_n\) be the balance after the \(n\)th deposit.

Then

\[ \boxed{B_n=1.02B_{n-1}+100}. \]

This is a first-order nonhomogeneous linear recurrence.

The previous balance contributes through the coefficient \(1.02\), while the deposit contributes the forcing term \(100\).

Example: Delayed Influence

Suppose a model uses both the previous state and the state two periods ago:

\[ P_n=1.1P_{n-1}-0.2P_{n-2}+50. \]

This recurrence is

Each of these labels describes a different structural feature.

Classifying a Linear Recurrence

Consider

\[ a_n=4a_{n-1}-3a_{n-2}+7. \]

It is:

Another Classification Example

Consider

\[ a_n=na_{n-1}+(n+1)a_{n-3}. \]

It is:

Why Homogeneous and Nonhomogeneous Matter

Homogeneous and nonhomogeneous recurrences behave differently because a nonhomogeneous recurrence includes an external contribution.

Compare

\[ a_n=2a_{n-1} \]

with

\[ b_n=2b_{n-1}+1. \]

The first evolves only from its previous value.

The second receives an additional \(1\) at every step.

Verification by Substitution

If an explicit formula is proposed for a recurrence, we can test it by substitution.

Suppose the recurrence is

\[ a_n=2a_{n-1} \]

and we claim

\[ a_n=3\cdot2^{n-1}. \]

Then

\[ a_{n-1}=3\cdot2^{n-2}. \]

Therefore,

\[ 2a_{n-1} = 2\left(3\cdot2^{n-2}\right) = 3\cdot2^{n-1} = a_n. \]

The formula satisfies the recurrence.

Initial Conditions Must Also Be Verified

Satisfying the recurrence is not enough.

A proposed explicit formula must also satisfy the initial conditions.

For the recurrence

\[ a_n=2a_{n-1} \]

both

\[ a_n=2^{n-1} \]

and

\[ a_n=5\cdot2^{n-1} \]

satisfy the recurrence.

An initial condition such as \(a_1=5\) selects the second one.

Linear Recurrences and Superposition

Homogeneous linear recurrences have an important structural property.

If two sequences satisfy the same homogeneous linear recurrence, then suitable linear combinations of those sequences also satisfy it.

This principle is called superposition.

It will become useful later when recurrence solutions are constructed from simpler building blocks.

A Gentle Superposition Example

Consider the recurrence

\[ a_n=2a_{n-1}. \]

The sequence

\[ u_n=2^{n-1} \]

satisfies it.

So does

\[ v_n=3\cdot2^{n-1}. \]

Their sum

\[ u_n+v_n=4\cdot2^{n-1} \]

also satisfies the same homogeneous recurrence.

Why Superposition Fails Directly for Nonhomogeneous Recurrences

Consider

\[ a_n=2a_{n-1}+1. \]

If two sequences each satisfy this recurrence, adding them causes the forcing term \(1\) to be added twice.

The result therefore does not generally satisfy the same recurrence.

This distinction between homogeneous and nonhomogeneous structure becomes important in later solution methods.

Linear Recurrences Can Produce Familiar Patterns

Different coefficient choices create different sequence behavior.

For example,

\[ a_n=a_{n-1}+a_{n-2} \]

produces Fibonacci-type growth.

The recurrence

\[ a_n=2a_{n-1}-a_{n-2} \]

can produce arithmetic sequences.

The recurrence

\[ a_n=-a_{n-1} \]

produces alternating behavior.

Example: A Recurrence Producing an Arithmetic Sequence

Let

\[ a_1=2,\qquad a_2=5, \] \[ a_n=2a_{n-1}-a_{n-2}. \]

Then

\[ a_3=2(5)-2=8, \] \[ a_4=2(8)-5=11, \] \[ a_5=2(11)-8=14. \]

Thus,

\[ \boxed{2,\ 5,\ 8,\ 11,\ 14,\ldots}. \]

The second-order recurrence preserves the constant first difference.

Example: Alternating Linear Recurrence

Let

\[ a_1=6, \] \[ a_n=-a_{n-1}. \]

Then

\[ \boxed{6,\ -6,\ 6,\ -6,\ldots}. \]

This is a first-order homogeneous linear recurrence with coefficient \(-1\).

Repeated Roots and Characteristic Structure Come Later

Many constant-coefficient homogeneous linear recurrences can eventually be solved through an algebraic equation associated with the recurrence.

That method is important, but it is not required for understanding what a linear recurrence is or for generating its terms.

This lesson therefore emphasizes recognition, classification, initial conditions, and forward computation. Characteristic methods are developed in a later lesson.

Common Error: Calling Every Recurrence Linear

The recurrence

\[ a_n=(a_{n-1})^2+1 \]

is recursive, but it is not linear.

Recursion describes dependence on earlier terms. Linearity describes the algebraic form of that dependence.

Common Error: Misidentifying the Order

Consider

\[ a_n=4a_{n-1}+2a_{n-3}. \]

The recurrence is third order, not second order.

The fact that only two earlier terms appear does not determine the order. The most distant dependency is \(a_{n-3}\).

Common Error: Forgetting Required Initial Values

The recurrence

\[ a_n=3a_{n-1}-a_{n-2} \]

is second order.

Giving only \(a_1\) does not normally provide enough information to compute \(a_3\).

Two starting values are required.

Common Error: Confusing Homogeneous with Constant Coefficients

These are different classifications.

The recurrence

\[ a_n=na_{n-1} \]

is homogeneous but has a variable coefficient.

The recurrence

\[ a_n=2a_{n-1}+5 \]

has a constant coefficient but is nonhomogeneous.

Common Error: Treating the Forcing Term as a Coefficient

In

\[ a_n=4a_{n-1}+7, \]

the coefficient of \(a_{n-1}\) is

\[ 4, \]

while

\[ 7 \]

is the forcing term.

Common Error: Skipping Terms during Forward Evaluation

A second-order recurrence requires the most recent two terms at each step.

If

\[ a_n=a_{n-1}+a_{n-2}, \]

then \(a_6\) should normally be computed only after \(a_4\) and \(a_5\) are known.

Skipping directly to a distant term without an explicit formula can omit required dependency information.

Common Error: Assuming Constant Coefficients Mean Constant Terms

In

\[ a_n=2a_{n-1}-a_{n-2}, \]

the coefficients \(2\) and \(-1\) are constant.

The sequence values themselves do not need to be constant.

"Constant coefficient" describes the multipliers in the recurrence.

A Reliable Procedure for Classifying a Recurrence

  1. Identify which earlier sequence terms appear.
  2. Check whether those terms form a linear combination.
  3. Determine the most distant previous index to find the order.
  4. Check whether the coefficients are constant or depend on \(n\).
  5. Check whether an additional forcing term is present.
  6. Classify the recurrence as homogeneous or nonhomogeneous.

A Reliable Procedure for Forward Evaluation

  1. Identify the recurrence order.
  2. Confirm that enough initial values are supplied.
  3. Identify the first index at which the recurrence applies.
  4. Substitute known earlier values into the recurrence.
  5. Simplify carefully to obtain the next term.
  6. Repeat in index order.
  7. Check signs, coefficients, and indexing at every step.

A Reliable Procedure for Verifying a Proposed Formula

  1. Substitute the proposed formula for \(a_n\).
  2. Write corresponding formulas for \(a_{n-1},a_{n-2},\ldots\).
  3. Substitute those expressions into the recurrence.
  4. Verify that both sides agree for the allowed indices.
  5. Check every required initial condition separately.

Practice 1: Classify the Recurrence

Classify

\[ a_n=5a_{n-1}-2a_{n-2}. \]

State whether it is linear, its order, whether its coefficients are constant, and whether it is homogeneous.

Practice 2: Classify a Nonhomogeneous Recurrence

Classify

\[ a_n=3a_{n-1}+4. \]

Practice 3: Identify a Nonlinear Recurrence

Is

\[ a_n=a_{n-1}a_{n-2}+1 \]

linear? Explain.

Practice 4: Forward Evaluation

Let

\[ a_1=1,\qquad a_2=2, \] \[ a_n=3a_{n-1}-a_{n-2}. \]

Find \(a_3,a_4,a_5\).

Practice 5: First-Order Nonhomogeneous Recurrence

Let

\[ b_0=4, \] \[ b_n=2b_{n-1}+5. \]

Find \(b_1,b_2,b_3\).

Practice 6: Determine the Order

What is the order of

\[ c_n=2c_{n-1}-7c_{n-4}? \]

Practice 7: Constant or Variable Coefficients?

Classify the coefficients in

\[ a_n=(n+1)a_{n-1}-na_{n-2}. \]

Practice 8: Homogeneous or Nonhomogeneous?

Classify

\[ a_n=4a_{n-1}-4a_{n-2}+n^2. \]

Practice 9: Model a Repeated Process

An account balance earns \(3\%\) per period and receives a \(\$50\) deposit after the growth is applied.

Write a first-order linear recurrence for the balance \(B_n\).

Practice 10: Verify a Formula

The recurrence is

\[ a_n=3a_{n-1}, \]

with

\[ a_1=2. \]

Verify that

\[ a_n=2\cdot3^{n-1} \]

satisfies both the recurrence and the initial condition.

Practice Answers

Practice 1

The recurrence

\[ a_n=5a_{n-1}-2a_{n-2} \]

is linear because it uses a linear combination of earlier terms.

It reaches back to \(a_{n-2}\), so it is second order.

Its coefficients \(5\) and \(-2\) are constant.

There is no forcing term, so it is homogeneous.

\[ \boxed{\text{linear, second order, constant coefficient, homogeneous}} \]

Practice 2

The recurrence

\[ a_n=3a_{n-1}+4 \]

is linear and first order.

The coefficient \(3\) is constant.

The added \(4\) is a forcing term, so the recurrence is nonhomogeneous.

\[ \boxed{\text{linear, first order, constant coefficient, nonhomogeneous}} \]

Practice 3

No.

The product

\[ a_{n-1}a_{n-2} \]

multiplies sequence terms together, so the recurrence is nonlinear.

Practice 4

\[ a_3=3(2)-1=5, \] \[ a_4=3(5)-2=13, \] \[ a_5=3(13)-5=34. \]

Therefore,

\[ \boxed{a_3=5,\qquad a_4=13,\qquad a_5=34}. \]

Practice 5

\[ b_1=2(4)+5=13, \] \[ b_2=2(13)+5=31, \] \[ b_3=2(31)+5=67. \]

Therefore,

\[ \boxed{b_1=13,\qquad b_2=31,\qquad b_3=67}. \]

Practice 6

The most distant dependency is \(c_{n-4}\).

\[ \boxed{\text{fourth order}} \]

Practice 7

The coefficients

\[ n+1 \]

and

\[ -n \]

depend on the index.

\[ \boxed{\text{variable coefficients}} \]

Practice 8

The term

\[ n^2 \]

is a forcing term independent of earlier sequence values.

\[ \boxed{\text{nonhomogeneous}} \]

Practice 9

A \(3\%\) increase multiplies the previous balance by

\[ 1.03. \]

The \(\$50\) deposit is then added:

\[ \boxed{B_n=1.03B_{n-1}+50}. \]

An initial balance such as \(B_0\) must also be supplied to determine a unique sequence.

Practice 10

First,

\[ a_{n-1}=2\cdot3^{n-2}. \]

Then

\[ 3a_{n-1} = 3\left(2\cdot3^{n-2}\right) = 2\cdot3^{n-1} = a_n. \]

So the formula satisfies the recurrence.

At \(n=1\),

\[ a_1=2\cdot3^0=2, \]

so it also satisfies the initial condition.

\[ \boxed{\text{The formula satisfies both requirements.}} \]

What to Remember

A linear recurrence relation expresses a sequence term as a linear combination of earlier terms, possibly with an additional forcing term.

\[ \boxed{ a_n = c_1a_{n-1} +\cdots+ c_ka_{n-k} + g(n) }. \]

Where We Go Next

Linear recurrence relations provide a broad structural framework for step-by-step dependence. One especially important second-order recurrence adds the two preceding terms and produces the Fibonacci sequence and many related patterns.

The next lesson, Fibonacci-Type Sequences, examines this recurrence family, the role of initial conditions, shifted and scaled variants, combinatorial appearances, and the structural patterns generated by repeated two-term addition.