Sequences and recursive formulas

A sequence is an ordered list of numbers, where each element has a specific place. A sequence can be described either by an explicit formula or by a recursive formula.

When a sequence is defined recursively, the next term depends on one or more of the previous terms.

 

Example of a simple recursive sequence

We can define a sequence where each term is twice as large as the previous one:

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

Here \( \large a_{0} = 1 \) is the starting point. From the formula we obtain

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

 

Recursive formula

In a recursive formula, a term is described from previous terms. To get started, one must know one or more starting values, called initial conditions.

 

First-order recursion

A first-order recursion means that each term depends only on the previous term. An example is

 

$$ \large a_{n} = 3 \cdot a_{n-1}, \quad a_{0} = 2 $$

 

Here each term is multiplied by 3 compared to the previous one. The sequence becomes

 

$$ \large 2, \; 6, \; 18, \; 54, \ldots $$

 

Second-order recursion

A second-order recursion means that each term depends on the two preceding terms. The most famous example is the Fibonacci sequence:

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Here each term is the sum of the two previous ones. The sequence begins as

 

$$ \large 0, \; 1, \; 1, \; 2, \; 3, \; 5, \; 8, \; 13, \ldots $$

 

There are many other examples of second-order recursions. Here is one where each term is found by multiplying the previous by 2 and subtracting the term before that:

 

$$ \large a_{n} = 2 \cdot a_{n-1} - a_{n-2}, \quad a_{0} = 1, \quad a_{1} = 2 $$

 

If we insert the first values, we get

 

$$ \large a_{2} = 3, \quad a_{3} = 4, \quad a_{4} = 5, \quad a_{5} = 6, \ldots $$

 

In this case, the recursion produces a simple arithmetic progression, even though the original formula looks more complicated.

 

Explicit formula

Here one can actually find an explicit formula that describes the entire sequence directly:

 

$$ \large a_{n} = n + 1 $$

 

This shows that recursive and explicit forms are often closely connected. An apparently complex recursive definition can hide a very simple explicit formula.

 

 

Terminology

In working with recursive formulas, some standard concepts are used:

 

• Initial conditions: the first values that start the sequence.
• Order of recursion: how many previous terms are used to determine the next (e.g., first-order or second-order).
• Basis: the first steps in the definition on which the rest is built.

 

These concepts appear in all types of recursive definitions and make it easier to work with them systematically.

 

 

Summary

Recursive formulas are useful for describing structures where each new term grows out of the previous ones. They give a clear picture of the relationship between the numbers but require knowledge of earlier terms in order to continue. Often one can later find an explicit formula that provides a faster way to calculate directly.

Understanding the difference between first- and second-order recursions, and their relation to explicit solutions, is an important first step in working with recursive methods.