- Home
- >
- Recursive sequence – Pattern, Formula, and Explanation
Contents
Recursive Sequence – Pattern, Formula, and Explanation
We can observe patterns in our everyday lives – from the number of sunflower petals to snowflakes, they all exhibit patterns. We can model most of these patterns mathematically through functions and recursive sequences.
Recursive sequences are sequences that have terms relying on the previous term’s value to find the next term’s value.
One of the most famous examples of recursive sequences is the Fibonacci sequence. This article will discuss the Fibonacci sequence and why we consider it a recursive sequence.
We’ll also learn how to identify recursive sequences and the patterns they exhibit. We’ll also apply this to predict the next terms of a recursive sequence and learn how to generalize the patterns algebraically.
Let’s begin by understanding the definition of recursive sequences.
What is a recursive sequence?
Recursive sequences are not as straightforward as arithmetic and geometric sequences. That’s because it relies on a particular pattern or rule and the next term will depend on the value of the previous term.
Let’s take a look at the Fibonacci sequence shown below. Take some time to observe the terms and make a guess as to how they progress.
We can see that for this sequence, we start with two $1$’s. These two terms are crucial in predicting the third term: to find the third term; we need to add the two values.
Next, to find the fourth term, we add the second and third terms. Yes, for the fifth term, we add the fourth term by the third term.
This means that the next three terms are shown below:
\begin{aligned}8 + 13 &= \color{blue}21\\13 + 21 &= \color{blue}43\\43 + 21 &= \color{blue}64\end{aligned}
In the next sections, we’ll go back to this example and better understand what makes up a recursive sequence. But for now, we’ve shown you how trickier patterns can be modelled as recursive sequences and why it’s important for us to understand how these sequences work.
How to solve recursive sequences?
Since recursive sequences’ rules vary from each other, it is nearly impossible to create a general pattern that applies to all recursive sequences, unlike arithmetic or geometric sequences.
Instead, it helps to observe the patterns exhibited by a given sequence and use the initial values to create a rule that may apply to the sequence.
As a guide, why don’t we go ahead and review the definition of recursive sequences and try constructing recursive sequence formulas from the patterns we’ve observed?
Recursive sequence definition
As we have mentioned, recursive sequences depend on the previous term and the rules observed for the particular sequence. Here are some examples of recursive sequence along with the rules that they follow:
Recursive Sequence | Recursive Sequence Formula |
$\{1, 3, 7, …\}$ | $\left\{\begin{matrix}a_1 = 1\phantom{xxxxxxx}\\a_n = 2a_{n-1} + 1 \end{matrix}\right.$ |
$\{2, 9, 30, …\}$ | $\left\{\begin{matrix}a_1 = 1\phantom{xxxxxxx}\\a_n = 3a_{n-1} + 3 \end{matrix}\right.$ |
As can be seen, by the two examples, the rules will vary for each sequence and we may even observe several patterns for one sequence.
We can also execute sequences given the recursive sequence formula. We use the previous term and evaluate the next term’s value using the given rules or patterns.
Recursive sequence formula
When given a recursive sequence, we can predict and establish their formulas and rules.
- An initial value such as $a_1$.
- A pattern or an equation in terms of $a_{n – 1}$ or even $a_{n -2}$ that applies throughout the sequence.
- We can express the rule as a function of $a_{n -1}$.
Before establishing recursive sequence formula, let’s practice determining the next terms of a recursive sequence given its formula.
Why don’t we try finding the next three terms of $\{1, 3, 7, …\}$ and $\{2, 9, 30, …\}$?
For $\{1, 3, 7, …\}$, let’s use the rule, $ a_n = 2a_{n-1} + 1$:
$\boldsymbol{a_4}$ | $\boldsymbol{a_5}$ | $\boldsymbol{a_6}$ |
\begin{aligned}a_4 &= 2a_3 + 1\\&= 2(7) + 1\\&= 15 \end{aligned} | \begin{aligned}a_5 &= 2a_4 + 1\\&= 2(15) + 1\\&= 31 \end{aligned} | \begin{aligned}a_6 &= 2a_5 + 1\\&= 2(31) + 1\\&= 63 \end{aligned} |
This shows that as long as we have the previous term and we know the rule for the recursive sequence, we can predict the terms that follow. Let’s go ahead and do this for $\{2, 9, 30, …\}$ given that $a_n = 3a_{n-1} + 3$.
$\boldsymbol{a_4}$ | $\boldsymbol{a_5}$ | $\boldsymbol{a_6}$ |
\begin{aligned}a_4 &= 3a_3 + 3\\&= 3(30) + 3\\&= 93 \end{aligned} | \begin{aligned}a_5 &= 3a_4 + 3\\&= 3(93) + 3\\&= 282 \end{aligned} | \begin{aligned}a_6 &= 3a_5 + 3\\&= 3(282) + 3\\&= 849 \end{aligned} |
But what if we’re not given the rules for the recursive sequence? It will be helpful if we begin observing the first few terms for patterns. We then use these terms to find a rule for the entire sequence.
Let’s go back to the Fibonacci sequence we’ve observed: $\{1, 1, 2, 3, 5, 8, …\}$. We can start with the fact that the third term adds the first and second terms.
As we have discussed in the earlier section, this pattern continues for each set of three terms. We can establish a rule in terms of $a_{n-2}$, $a_{n-1}$, and $a_n$:
\begin{aligned}a_n = a_{n-2} + a_{n – 1}\end{aligned}
This pattern will only be true if we have $a_1 = 1$ and $a_2 = 2$. Hence, we can further establish the general by including the initial values as shown below.
$\left\{\begin{matrix}a_1 = 1\phantom{xxxxxxxxx}\\a_2 =1\phantom{xxxxxxxxx}\\a_n = a_{n -2} + a_{n – 1} \end{matrix}\right.$
Are you ready to try out more problems involving recursive sequences? Make sure to review your notes first before trying out these examples below.
Example 1
What is the fifth term of the recursive sequence that is defined by the following rules: $a_1 = 4$ and $a_n = -2a_{n – 1} + 4$?
Solution
We’ll use the value of $a_1$ and the expression for $a_n$ to find the value of $a_2$.
\begin{aligned}a_2 &= -2a_1 +4 \\&=-2(4) + 4\\&= -8 + 4\\&= -4\end{aligned}
We repeat a similar process to find the next three terms: by using the previous term into the formula as shown below.
$\boldsymbol{a_3}$ | $\boldsymbol{a_4}$ | $\boldsymbol{a_5}$ |
\begin{aligned}a_3 &= -2a_2 +4 \\&=-2(-4) + 4\\&= 8 + 4\\&= 12\end{aligned} | \begin{aligned}a_4 &= -2a_3 +4 \\&=-2(12) + 4\\&= -24 + 4\\&= -20\end{aligned} | \begin{aligned}a_5 &= -2a_5 +4 \\&=-2(-20) + 4\\&= 40 + 4\\&= 44\end{aligned} |
Hence, the fifth term of the sequence is equal to $44$.
Example 2
Write down the first six terms of the sequence that follows the recursive formula shown below.
$\left\{\begin{matrix}a_1 = 0\\a_2 = 1\\a_3 = 1\\a_n = \dfrac{2a_{n – 1}}{a_{n – 2}}\end{matrix}\right.$
Solution
Let’s first understand what $a_n = \dfrac{2a_{n – 1}}{a_{n – 2}}$ means. From this formula, we can see that the nth term of this particular recursive sequence can be determined by finding the last two terms’ ratio and multiplying the result by $2$.
If we want the first six terms, we already have the first three terms, and we only need the three remaining terms: $a_4$, $a_5$, and $a_6$.
To find the value of $a_4$, we simply divide $a_3$ by $a_2$ then multiply the result by $2$. We apply a similar approach to determine the values of $a_5$ and $a_6$.
$\boldsymbol{a_4}$ | $\boldsymbol{a_5}$ | $\boldsymbol{a_6}$ |
\begin{aligned}a_4 &= \dfrac{2a_3}{a_2}\\&= \dfrac{2(1)}{1}\\&= 2\end{aligned} | \begin{aligned}a_5 &= \dfrac{2a_4}{a_3}\\&= \dfrac{2(2)}{1}\\&= 4\end{aligned} | \begin{aligned}a_6 &= \dfrac{2a_5}{a_4}\\&= \dfrac{2(4)}{2}\\&= 4\end{aligned} |
Hence, we have the first six terms of the recursive formula: $\{0, 1, 1, 2, 4, 4\}$.
Example 3
What is the recursive formula that can describe the pattern for the following sequences?
a. $\{2, 6, 14, 30,…\}$
b. $\{1, 2, 6, 24, …\}$
Solution
It helps to observe how the two terms are related to each other, and we can then check if the rules will work for the fourth term.
Let’s begin with the first sequence, $\{2, 6, 14, 30,…\}$, and see how $6$ relates with $2$ and $14$ with $6$.
\begin{aligned}6 &= 4 + 2\\&= 2(2) + 2\\14&= 12 + 2\\ &= 2(6) + 2\end{aligned}
We can see that the next term can be determined by multiplying the previous term by $2$ then adding the result with $2$. To see if the pattern fits the next term, let’s try to multiply $14$ by $2$ then adding $2$ to the product.
\begin{aligned}14(2) + 2 &= 30\end{aligned}
Since we got $30$, this confirms that we have the correct observations and rule for the recursive sequence. This means that to find $a_n$, we simply multiply $a_{n -1}$ by $2$ then add $2$ to the result: $a_n = 2a_{n – 1} + 2$.
Including the first term, we have the recursive formula shown below for the first sequence.
$\left\{\begin{matrix}a_1 = 2 \phantom{xxxxxx}\\a_n = 2a_{n – 1} + 2\end{matrix}\right.$
Let’s go ahead and move on to the second sequence, $\{1, 2, 6, 24, …\}$. We can apply a similar process when trying to find a pattern for the sequence.
\begin{aligned} 1&= 1 \cdot 1\\ 2 &= 1 \cdot 2\\6 & = 2 \cdot 3\end{aligned}
What can you notice about the four terms? The position of the terms is actually a factor for the formula.
This means that $2$ is the result of the previous term being multiplied by the place number – $2$. Similarly, $6$ is the result when we multiply the previous term with the place number – $3$.
We can see that the fourth term, $24$ is equal to $6 \times 4$, which confirms that observation is correct. Hence, $a_n$ will result from the previous term, $a_{n – 1}$, is multiplied by the place number, $n$.
\begin{aligned}24 &= 6 \times 4\\ a_4 &= a_3 \cdot 4\\a_n &= a_{n – 1} \cdot n \\&= na_{n- 1} \end{aligned}
Let’s include the initial value for the formula; hence, we have the rule shown below:
$\left\{\begin{matrix}a_1 = 1 \phantom{xxxxxx}\\a_n = na_{n- 1}\end{matrix}\right.$