# 6.1: Recursively-Defined Sequences

- Page ID
- 60215

You may be familiar with the term “recursion” as a programming technique. It comes from the same root as the word “recur,” and is a technique that involves repeatedly applying a self-referencing definition until we reach some initial terms that are explicitly defined, and then going back through the applications to work out the result we want. If you didn’t follow that, it’s okay, we’ll go through the definition and some specific examples that should give you the idea.

Definition: Recursive Relation

A sequence \(r_1, r_2, . . . , r_n, . . .\) is** recursively defined** if for every \(n\) greater than or equal to some bound \(b ≥ 2\), the value for \(r_n\) depends on at least some of the values of \(r_1, . . . , r_{n−1}\). The values for \(r_1, . . . , r_{b−1}\) are given explicitly; these are referred to as the **initial conditions** for the recursively-defined sequence. The equation that defines \(r_n\) from \(r_1, . . . , r_{n−1}\) is called the **recursive relation**.

Probably the best-known example of a recursively-defined sequence is the Fibonacci sequence. It is named for an Italian mathematician who introduced the sequence to western culture as an example in a book he wrote in \(1202\) to advocate for the use of Arabic numerals and the decimal system. The sequence was known to Indian mathematicians as early as the \(6^{\text{th}}\) century.

Definition: Fibonacci Sequence

The **Fibonacci sequence** is the sequence \(f_0, f_1, f_2, . . .\), defined by \(f_0 = 1\), \(f_1 = 1\), and \(f_n = f_{n−1} + f_{n−2}\) for all \(n ≥ 2\).

So in the Fibonacci sequence, \(f_0 = f_1 = 1\) are the initial conditions, and \(f_n = f_{n−1} + f_{n−2}\) for all \(n ≥ 2\) is the recursive relation.

The usual problem associated with recursively-defined sequences, is to find an explicit formula for the \(n^{th}\) term that does not require calculating all of the previous terms. Clearly, if we want to be able to determine terms that arise later in the sequence, this is critical. If we try to find the millionth term of a recursively-defined sequence directly, it will require a great deal of computing time and might also require a lot of memory.

Every time you were asked in school to look at a sequence of numbers, find a pattern, and give the next number in the sequence, you were probably working out a recurrence relation and applying it.

Example \(\PageIndex{1}\)

Consider the sequence 5, 8, 11, 14. What number should come next?

**Solution**

We consider the differences between successive pairs: \(8 − 5 = 3\); \(11 − 8 = 3\); \(14 − 11 = 3\). This appears to be an arithmetic sequence, with the constant difference of \(3\) between successive terms. So the sequence can be defined by \(a_1 = 5\) and \(a_n = a_{n−1} + 3\), for every \(n ≥ 2\). We were asked for \(a_5\), and we know that \(a_4 = 14\), so \(a_5 = a_4 + 3 = 14 + 3 = 17\).

Here’s a slightly more complicated example:

Example \(\PageIndex{2}\)

Consider the sequence \(3\), \(6\), \(11\), \(18\), \(27\). What number should come next?

**Solution**

Again, consider the differences between successive terms: \(6 − 3 = 3\); \(11 − 6 = 5\); \(18−11 = 7\); \(27−18 = 9\). These differences aren’t constant, but do follow a predictable pattern: they are the odd numbers (starting at \(3\) and increasing). So the sequence can be defined by \(a_1 = 3\) and an = \(a_{n−1} + (2n − 1)\), for every \(n ≥ 2\). We were asked for \(a_6\), and we know that \(a_5 = 27\), so \(a_6 = a_5 + 2(6) − 1 = 27 + 11 = 38\).

This example shows that the recurrence relation can depend on n, as well as on the values of the preceding terms. (Although we didn’t state this explicitly in our definition, it is implicit because \(n − 1\) is the number of previous terms on which \(r_n\) depends; we could calculate \(n\) as \(a^0_1 + a^0_2 + . . . + a^0_{n−1} + 1\).)

Let’s look at one more example.

Example \(\PageIndex{3}\)

Stavroula’s bank pays \(1 \%\) interest (compounded annually), and charges her a service fee of \($10\) per year to maintain the account. The fee is charged at the start of the year, and the interest is calculated on the balance at the end of the year. If she starts with a balance of \($2000\), is she making money or losing money? If this account is set up for her by her parents and she’s not allowed to touch it, how much money will be in the account after seven years?

**Solution**

We see that the initial term is \(r_0 = 2000\). We’re going to use \(r_0\) as the first term, because then the value of her account after \(1\) year will be \(r_1\); after two years will be \(r_2\); and after seven years will be \(r_7\). This just makes it a little easier to keep track of what we’re aiming to figure out.

If we unpack the financial language, it is telling us that every year, the bank takes \($10\) from Stavroula’s account at the start of the year. Then at the end of the year, the bank adds \(1 \%\) of whatever is in Stavroula’s account, to her account. This can be represented by the following recurrence relation: \(r_n = r_{n−1} − 10 + .01(r_{n−1} − 10)\) for every \(n ≥ 1\), which simplifies to \(r_n = 1.01(r_{n−1} − 10)\). Logically, she will be making money if the \(1 \%\) that she earns in interest, exceeds the service fee of \($10\), so if she makes money in the first year, she will continue to make money; while if she loses money in the first year, she will continue to lose money after that. So to answer the first question, we’ll work out \(r_1 = 1.01(r_0 −10) = 1.01(1990) = 2009.9\). Stavroula is making money.

To answer the second question, unless we’ve managed to figure out an explicit formula for \(r_n\) (which we don’t yet know how to do), we need to calculate \(r_2\), \(r_3\), \(r_4\), \(r_5\), \(r_6\), and \(r_7\). It would be reasonable to assume that the bank rounds its calculations to the nearest penny every year, and carries forward with the rounded value, but because this will create an error that will be compounded in comparison with solving our recurrence relation explicitly (which we’ll learn later how to do), we’ll keep track of the exact values instead. We have

\( \begin{equation}\begin{split} r_2 &= 1.01(2009.9 − 10) = 2019.899; \\ r_3&= 1.01(2009.899) = 2029.99799; \\ r_4&= 1.01(2019.99799) = 2040.1979699; \\ r_5&= 1.01(2030.1979699) = 2050.499949599; \\ r_6&= 1.01(2040.499949599) = 2060.90494909499; \text{ and} \\ r_7&= 1.01(2050.90494909499) = 2071.4139985859399 \end{split} \end{equation} \)

So at the end of seven years, Stavroula has \($2071.41\).

Exercise \(\PageIndex{1}\)

Solve the following problems about recurrence relations.

- Consider the sequence \(4\), \(9\), \(19\), \(39\). Give a recurrence relation that describes this sequence, and find the next term in the sequence.
- Use the recurrence relation for the Fibonacci sequence to find \(f_6\).
- If the annual fee on Stavroula’s bank account from Example 6.1.3 is \($20\) instead of \($10\), is she making money or losing money?