Linear Recurrences

students, imagine you are tracking a growing savings account, the number of tiles in a pattern, or how fast a computer program repeats a task. In each case, the next value often depends on earlier values. That idea is the heart of a recurrence relation, and a linear recurrence is one of the most important types. 📈

In this lesson, you will learn how to recognize linear recurrences, understand the key vocabulary, and use them to model real situations. By the end, you should be able to explain how linear recurrences fit into the larger study of recurrence relations and apply them to simple problems in discrete mathematics.

What Is a Linear Recurrence?

A recurrence relation is a rule that defines each term of a sequence using one or more earlier terms. Instead of listing every value directly, we start with a few initial values and then use a pattern to build the rest.

A recurrence is called linear if each new term is made from earlier terms by adding together constant multiples of those terms. In other words, the earlier terms are not multiplied together, raised to powers, or put inside complicated functions.

A general linear recurrence has the form

$$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k} + f(n)$$

where $c_1, c_2, \dots, c_k$ are constants and $f(n)$ is a function of $n$.

If $f(n)=0$, the recurrence is called homogeneous. If $f(n)\neq 0$, it is non-homogeneous.

For example, the Fibonacci sequence is a famous linear recurrence:

$$F_n = F_{n-1} + F_{n-2}$$

with starting values $F_0=0$ and $F_1=1$.

This rule says each term is the sum of the previous two terms. That simple idea appears in nature, computer science, and mathematics. 🌱

Key Vocabulary and Main Ideas

To work with linear recurrences, it helps to know the main terms.

Sequence: an ordered list of numbers such as $1, 2, 4, 8, \dots$
Term: one entry in the sequence, such as $a_5$
Index: the position of a term, such as $n$ in $a_n$
Initial conditions: the starting values needed to generate the sequence
Order: how many earlier terms are used in the recurrence
Homogeneous recurrence: a linear recurrence with no extra term $f(n)$
Non-homogeneous recurrence: a linear recurrence with an extra term $f(n)$

The order is especially important. A first-order recurrence uses only the previous term, such as

$$a_n = 3a_{n-1}$$

A second-order recurrence uses the previous two terms, such as

$$a_n = 2a_{n-1} - a_{n-2}$$

A third-order recurrence uses the previous three terms, and so on.

The coefficients are also important. In a linear recurrence, the coefficients are constants. For example, in

$$a_n = 4a_{n-1} - 5a_{n-2}$$

the numbers $4$ and $-5$ are constant coefficients.

Notice what makes a recurrence linear: the terms $a_{n-1}$ and $a_{n-2}$ are not squared, multiplied together, or hidden inside a square root. A rule like

$$a_n = a_{n-1}^2 + 1$$

is a recurrence, but it is not linear because of the square.

How Linear Recurrences Work in Practice

A linear recurrence gives a step-by-step method for generating a sequence. You begin with the initial conditions, then apply the rule again and again.

Suppose

$$a_n = 2a_{n-1} + 1$$

with $a_0=1$.

Then the first few terms are:

$$a_1 = 2(1)+1 = 3$$

$$a_2 = 2(3)+1 = 7$$

$$a_3 = 2(7)+1 = 15$$

So the sequence begins

$$1, 3, 7, 15, \dots$$

This kind of reasoning is common in algorithm analysis. If a process does twice as much work as before, plus a small extra cost, the recurrence can describe how the work grows.

For example, imagine a game where each level requires solving all tasks from the previous level plus one new task. If the number of tasks at level $n$ is $a_n$, a recurrence might look like

$$a_n = a_{n-1} + 1$$

with some starting value $a_0$.

That recurrence is linear and first-order. It shows how a simple rule can create a predictable pattern over time. 🔁

Recognizing Linear Versus Nonlinear Recurrences

It is important to tell whether a recurrence is linear, because many methods in discrete mathematics depend on that structure.

Linear examples

$$a_n = 5a_{n-1} - 2$$
$$a_n = 3a_{n-1} + 4a_{n-2}$$
$$a_n = 2a_{n-1} - a_{n-3} + n$$

These are linear because each earlier term appears only to the first power, and the terms are combined using addition and constant multiplication.

Nonlinear examples

$$a_n = a_{n-1}^2 + 1$$
$$a_n = a_{n-1}a_{n-2}$$
$$a_n = \sin(a_{n-1})$$

These are not linear because the previous terms are squared, multiplied together, or placed inside a function.

A quick test is this: if every earlier term appears only as a constant multiple and nothing more complicated happens to the term itself, the recurrence is linear.

Why Linear Recurrences Matter in Discrete Mathematics

Linear recurrences are useful because they model processes where each step depends on previous steps in a controlled way.

In counting problems

Suppose a staircase has $n$ steps, and you can climb either $1$ or $2$ steps at a time. Let $a_n$ be the number of ways to reach step $n$. Then the last move is either a $1$-step from step $n-1$ or a $2$-step from step $n-2$. That gives

$$a_n = a_{n-1} + a_{n-2}$$

This is a linear recurrence, and it helps count possibilities without listing them all.

In algorithmic thinking

Some algorithms split a problem into smaller pieces. If the cost of solving a problem of size $n$ depends on the cost of smaller problems, a recurrence can describe the running time.

For example, a very simplified divide-and-conquer idea might lead to a recurrence like

$$T(n) = 2T\left(\frac{n}{2}\right) + n$$

This is a recurrence relation used in computer science to study efficiency. Although it is not the same kind of simple integer-indexed sequence as $a_n$, it still fits the broader recurrence relation idea: the value at one stage depends on earlier or smaller stages.

In population and finance models

If a population grows by a fixed percentage each year, a recurrence such as

$$P_n = 1.05P_{n-1}$$

models the growth. The same structure appears in interest calculations and repeated investment growth. 💰

Solving Simple Linear Recurrences

Not every linear recurrence has a complicated solution. Some can be solved by looking for a pattern.

Consider

$$a_n = a_{n-1} + 3$$

with $a_0 = 2$.

The sequence is

$$2, 5, 8, 11, \dots$$

Each term increases by $3$, so after $n$ steps, the formula is

$$a_n = 2 + 3n$$

This is called a closed form because it gives $a_n$ directly without needing earlier terms.

Another example:

$$a_n = 2a_{n-1}$$

with $a_0 = 5$.

Then

$$a_n = 5\cdot 2^n$$

because each term doubles the previous one.

These examples show an important idea: recurrence relations describe how a sequence is built, while a closed form describes the final result in one formula. Both are useful.

Connection to the Larger Topic of Recurrence Relations

Linear recurrences are a major part of the broader study of recurrence relations. The larger topic includes many kinds of recursive rules, but linear ones are especially important because they are easier to analyze and appear often in applications.

When a course on recurrence relations introduces linear recurrences, it is building the foundation for more advanced ideas such as solving higher-order recurrences, using characteristic equations, and analyzing algorithm growth. Even when the recurrence is more complicated, the same basic questions still apply:

What are the initial conditions?
What order is the recurrence?
Is it linear or nonlinear?
Can the sequence be described in closed form?
What does the recurrence tell us about growth or behavior?

These questions help connect the structure of the recurrence to the behavior of the sequence.

Conclusion

Linear recurrences are rules where each term is a constant linear combination of earlier terms. They are a central idea in discrete mathematics because they help describe sequences, count combinatorial objects, and model repeated processes in algorithms, finance, and science.

students, when you see a recurrence, ask whether it is linear, what its order is, and what starting values are needed. Those questions are the first step toward understanding the pattern and using it effectively. With practice, linear recurrences become a powerful tool for reasoning about sequences and change. ✅

Study Notes

A recurrence relation defines each term of a sequence using earlier terms.
A linear recurrence uses only constant multiples of earlier terms, combined by addition and subtraction.
The order tells how many earlier terms are used.
Initial conditions are required to generate the sequence.
A recurrence is homogeneous if it has no extra term $f(n)$, and non-homogeneous if it does.
The Fibonacci recurrence is $F_n = F_{n-1} + F_{n-2}$.
Examples of linear recurrences include $a_n = 3a_{n-1} + 4a_{n-2}$ and $a_n = 5a_{n-1} - 2$.
Examples of nonlinear recurrences include $a_n = a_{n-1}^2 + 1$ and $a_n = a_{n-1}a_{n-2}$.
Linear recurrences are useful in counting problems, algorithm analysis, and growth models.
A closed form gives $a_n$ directly, while a recurrence gives a step-by-step rule.