Explicit solution of recursive formulas

When a sequence is defined by a recursive formula, it can be difficult to calculate an arbitrary term, because you always need to know the previous ones. Therefore, one often looks for an explicit solution, where each term can be calculated directly from \( \large n \).

 

 

From recursive to explicit

A common method is to write out the first terms and try to find a pattern. Often the first calculations reveal a connection that can be generalized.

 

Example 1

We look at the sequence

 

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

 

The first values are

 

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

 

The pattern is clear: each term is a power of 2. The explicit formula is

 

$$ \large a_{n} = 2^n $$

 

 

Example 2

We look at the sequence

 

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

 

The first values become

 

$$ \large a_{1} = 3, \quad a_{2} = 7, \quad a_{3} = 15, \quad a_{4} = 31 $$

 

Here we see the pattern: \( \large a_{n} = 2^{\,n+1} - 1 \). This can be proven by induction or by “unpacking the recursion” step by step.

 

 

Unpacking the recursion

Instead of only guessing the pattern, one can try to substitute several times in the formula. For example:

 

$$ \large a_{n} = 2 \cdot a_{n-1} + 1 \quad \Leftrightarrow $$

$$ \large a_{n}= 2 \cdot (2 \cdot a_{n-2} + 1) + 1 \quad \Leftrightarrow $$

$$ \large a_{n}= 2^2 \cdot a_{n-2} + 2 + 1 \quad \Leftrightarrow $$

$$ \large a_{n}= 2^3 \cdot a_{n-3} + 2^2 + 2 + 1 $$

 

If we continue this pattern all the way back to \( \large a_{0} = 1 \), we get

 

$$ \large a_{n} = 2^n \cdot a_{0} + (2^n - 1) $$

 

Since \( \large a_{0} = 1 \), the result becomes

 

$$ \large a_{n} = 2^n + 2^n - 1 \quad \Leftrightarrow $$

$$ \large a_{n} = 2^{\,n+1} - 1 $$

 

 

Example of a 2nd order recursion

We now look at a sequence that depends on the two preceding terms:

 

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

 

The first terms become:

 

$$ \large a_{2} = 5, \quad a_{3} = 8, \quad a_{4} = 13, \quad a_{5} = 21, \ldots $$

 

To find an explicit formula, we use the method of characteristic roots. We guess a solution of the form:

 

$$ \large a_{n} = r^n $$

 

Why this guess?

The recursion is linear and has constant coefficients.

When a term is always a linear combination of a fixed number of previous terms, it is natural to try an exponential form \( \large r^n \). If we insert this guess, the whole recursion reduces to an equation in \( \large r \), which does not depend on \( \large n \).

This means that the whole recursion can be satisfied by a geometric sequence where the ratio between two successive terms is constant.

Other guesses, such as \( \large n^\alpha \), could not satisfy the recursion for all \( \large n \).

 

Inserted into the recursion, this gives:

 

$$ \large r^n = r^{n-1} + r^{n-2} $$

 

Dividing by \( \large r^{\,n-2} \) (for \( \large r \neq 0 \)), we get

 

$$ \large r^2 = r + 1 $$

 

This is called the characteristic equation. It can be rewritten as:

 

$$ \large r^2 - r - 1 = 0 $$

 

With the quadratic formula, we find the discriminant:

 

$$ \large \Delta = (-1)^2 - 4 \cdot 1 \cdot (-1) \quad \Leftrightarrow $$

$$ \large \Delta = 1 + 4 \quad \Leftrightarrow $$

$$ \large \Delta = 5 $$

 

Hence comes the square root of 5. The solutions become:

 

$$ \large r_1 = \frac{1 + \sqrt{5}}{2}, \quad r_2 = \frac{1 - \sqrt{5}}{2} $$

 

Thus the general solution is

 

$$ \large a_{n} = C_1 \cdot r_1^n + C_2 \cdot r_2^n $$

 

We determine the constants from the initial conditions:

 

$$ \large a_{0} = 2 = C_1 + C_2 $$

$$ \large a_{1} = 3 = C_1 \cdot r_1 + C_2 \cdot r_2 $$

 

From this we get:

 

$$ \large C_1 = \frac{1 + \sqrt{5}}{\sqrt{5}}, \quad C_2 = \frac{\sqrt{5} - 1}{\sqrt{5}} $$

 

The explicit formula therefore becomes:

 

$$ \large a_{n} = \frac{1 + \sqrt{5}}{\sqrt{5}} \cdot \left(\frac{1 + \sqrt{5}}{2}\right)^n \;+\; \frac{\sqrt{5} - 1}{\sqrt{5}} \cdot \left(\frac{1 - \sqrt{5}}{2}\right)^n $$

 

With this formula, one can calculate any term directly. For example, with \( \large n = 5 \):

 

$$ \large a_{5} = 21 $$

 

 

 

Summary

An explicit solution makes it possible to jump directly to term number \( \large n \) without calculating all the previous ones. One often finds the formula by observing a pattern or by unpacking the recursion. In more advanced cases, such as 2nd order recursions, one can use the method of characteristic roots. Many recursive formulas can thus be rewritten into a simple explicit form, which both gives insight into the structure and makes calculation easier.