Section 5.5 Defining Sequences Recursively
We’ve seen sequences defined explicitly, such as \(a_n=n^2\text{.}\) Another common way to generate a sequence is by giving a rule for how to generate the next term from the previous term. For example, \(a_n=a_{n-1}+2\) where \(a_1=1\text{.}\) Such sequences are called recursively defined sequences.
Example 5.5.1. Explicitly Defined Sequences.
Find the first five terms of the sequence given by \(a_n=n^2, n\geq 0\text{.}\)
Answer 1.
\(a_0=0, a_1=1, a_2=4, a_3=9, a_4=16\)
Find the first five terms of the sequence given by \(a_n=\frac{1}{n}, n\geq 1\text{.}\)
Answer 2.
\(a_1=1, a_2=1/2, a_3=1/3, a_4=1/4, a_5=1/5\)
Activity 5.5.1.
Write out the first 6 terms of the sequence \(a_n=2^n, n\geq 0\text{.}\)
Example 5.5.2. Recursively Defined Sequences.
Find the first five terms of the sequence given by \(a_n=a_{n-1}+2, a_1=1\text{.}\)
Answer 1.
\(a_1=1, a_2=3, a_3=5, a_4=7, a_5=9\)
Find the first five terms of the sequence given by \(a_n=a_{n-1}+2, a_1=0\text{.}\)
Answer 2.
\(a_1=0, a_2=2, a_3=4, a_4=6, a_5=8\)
Find the first five terms of the sequence given by \(a_n=a_{n-1}+5a_{n-2}, a_0=1, a_1=1\text{.}\)
Answer 3.
\(a_0=1, a_1=1, a_2=6, a_3=11, a_4=41\)
Activity 5.5.2.
Write out the first 6 terms of the sequence \(a_n=a_{n-1}+2a_{n-2}, a_0=1, a_1=1\text{.}\)
Although both types of sequences use an equation to find \(a_n\text{,}\) the recursive sequence also needs to define the first few terms. If we change the initial terms, we get a different sequence. The formula used to generate the recursive sequence is called a recurrence relation, while the first term (or terms) is called the initial condition(s).
An advantage of an explicitly defined sequence is that it is easy to find any particular term. For example, it would be easy to calculate
\(a_{500}\) in
Example 5.5.1. In order to find
\(a_{500}\) in
Example 5.5.2, we would need to know
\(a_{499}\text{,}\) and all the terms before that. So we would need to have generated the sequence up to that point to calculate a specific term.
Recursive sequences have the advantage that they can be faster (or computationally simpler) to calculate, especially if you need to generate many terms of the sequence. Computers are good at generating recursive sequences. It also may be the case that we can easily define a recursive sequence in which it is difficult, or even impossible, to express with an explicit formula.
Example 5.5.3. The Fibonacci Sequence.
The Fibonacci sequence is defined recursively by
\begin{equation*}
F_1=1, F_2=1, F_k=F_{k-1}+F_{k-2}.
\end{equation*}
Give the first 6 terms of the Fibonacci sequence.
Answer.
\(1, 1, 2, 3, 5, 8\)
Activity 5.5.3.
Write out the 7th, 8th, and 9th terms of the Fibonacci sequence.
The Fibonacci sequence is a good example of a recursively defined sequence where it is difficult to find an explicit formula. An explicit formula for the Fibonacci sequence does exist, we will see it in the next section and in
Exercise 5.5.7, but it requires much more sophisticated mathematics to find it than anything we will see in this course. If you are interested, though, this is the sort of thing you would see if you take a combinatorics course. When we do see the formula, it should be clear that it is computationally
much harder to work with than the recursive definiton (which is why you rarely see it when working with the Fibonacci sequence).
Activity 5.5.4.
We would like to explore the connection between recursive and explicit sequences.
(a)
Write out the first 6 terms of \(a_n=\frac{(-1)^n}{n!}, n\geq 0\text{.}\) Is this an explicitly or recursively defined sequence?
(b)
Consider the recurrence relationship \(a_k=\frac{-a_{k-1}}{k}, k\geq1\text{.}\) Write out several terms of the sequence for a couple different choices of initial terms.
(c)
How do the sequences in (a) and (b) compare?
We want to be able to show the relationship between the recursive definition and the explicit definition for a sequence. In this section we will look at proving an explicit sequence satisfies a given recurrence relation. Since, in general, explict formulas contain more information than a recurrence relation, we can use simpler proof techniques to show an explicit sequence satisfies a recurrence relation.
Proving a Sequence Satisfies a Recurrence Relation.
To prove an explicity defined sequence satisfies a recurrence relation:
Assume the explicit formula for the sequence.
Show, using a LHS/RHS proof, that the recurrence relation holds.
This is always a direct proof. Do not use induction. We will see induction in the next section.
Example 5.5.4. Proving a Recurrence Relation for an Explicit Sequence.
Let \(a_n=3n+1, n\geq 0\text{.}\) Show this sequence satisfies the recurrence relation \(a_k=a_{k-1}+3\text{,}\) for \(k\geq 1\text{.}\)
Proof.
Assume \(a_n=3n+1\) for all \(n\geq 0\text{.}\) Show this sequence statisfies the recurrence relation \(a_k=a_{k-1}+3\text{.}\)
LHS: \(a_{k}=3k+1\text{,}\) since we know that \(a_k\) satisfies the explicit formula.
RHS: \(a_{k-1}+3=(3(k-1)+1)+3\text{,}\) since we know that \(a_{k-1}\) satisfies the explicit formula.
Simplifying, we get \(a_{k-1}+3=3k-3+1+3=3k+1\text{.}\)
Thus, the LHS=RHS, hence \(a_k=a_{k-1}+3\text{.}\)
Activity 5.5.5.
Prove \(a_n=\frac{(-1)^n}{n!}, n\geq 0\) satisfies the recurrence relationship \(a_k=\frac{-a_{k-1}}{k}, k\geq1\text{,}\) by assuming the sequence is given by \(a_n=\frac{(-1)^n}{n!}, n\geq 0\text{,}\) and showing \(a_k=\frac{-a_{k-1}}{k}\text{.}\)
To show an explicitly defined sequence satisfies a recurrence relationship always assume the explicit formula and show the recursive one. This can almost always be done with a direct proof.
We can use the recurrence relation for the Fibonacci numbers to prove additional properties.
Activity 5.5.6.
For the Fibonacci sequence, prove \({F_k}^2-{F_{k-1}}^2=F_kF_{k+1}-F_{k+1}F_{k-1}\) for all \(k\geq 1\text{.}\)
Hint.
Pick whichever side of the equation looks easier to start with. Do some algebra and, where appropriate, use the recursive definition for \(F_k\text{.}\) If you get stuck, try working with the other side of the equation.
Reading Questions Check Your Understanding
1.
2.
3.
4.
5.
Determine if the following sequence is explicitly defined or recursively defined: \(a_n=5a_{n-1}-4, a_1=2\text{.}\)
Explicitly defined
-
Recursively defined
-
6.
Determine if the following sequence is explicitly defined or recursively defined: \(a_n=\frac{a_{n-1}}{a_{n-2}}, a_{0}=1, a_1=2\text{.}\)
Explicitly defined
-
Recursively defined
-
7.
Determine if the following sequence is explicitly defined or recursively defined: \(a_n=n^2+n, n\geq 1\text{.}\)
Explicitly defined
-
Recursively defined
-
8.
Determine if the following sequence is explicitly defined or recursively defined: \(a_n=n+a_{n-1}, a_1=1\text{.}\)
Explicitly defined
-
Recursively defined
-
9.
Let \(a_n=2n+1, n\geq 0\text{.}\) Show this sequence satisfies the recurrence relation \(a_k=a_{k-1}+2\text{.}\)
Hint.
This is a LHS/RHS proof showing the recurrence relation is true when you assume \(a_n=2n+1\text{.}\) In particular, you know \(a_k=2k+1\) and \(a_{k-1}=2(k-1)+1\text{.}\)
10.
Let \(a_n=2n, n\geq 0\text{.}\) Show this sequence satisfies the recurrence relation \(a_k=a_{k-1}+2\text{.}\)
Hint.
This is a LHS/RHS proof showing the recurrence relation is true when you assume \(a_n=2n\text{.}\) In particular, you know \(a_k=2k\) and \(a_{k-1}=2(k-1)\text{.}\)
11.
Let \(a_n=2n+d, n\geq 0\text{.}\) Show this sequence satisfies the recurrence relation \(a_k=a_{k-1}+2\text{.}\)
Hint.
This is a LHS/RHS proof showing the recurrence relation is true when you assume \(a_n=2n+d\text{.}\) In particular, you know \(a_k=2k+d\) and \(a_{k-1}=2(k-1)+d\text{.}\)
Exercises Exercises
1.
Find the first 4 terms of the sequence defined by
\begin{equation*}
a_1=1
\end{equation*}
\begin{equation*}
a_k=a_{k-1}+3k, k\geq2.
\end{equation*}
2.
Find the first 4 terms of the sequence defined by
\begin{equation*}
b_0=-1, b_1=2
\end{equation*}
\begin{equation*}
b_k=b_{k-1}+2b_{k-2}, k\geq2.
\end{equation*}
3.
Let \(a_0, a_1, a_2, \ldots\) be the sequence defined by the formula \(a_n=3n+1\text{,}\) for all integers \(n\geq 0\text{.}\) Show that this sequence satisfies the recurrence relation \(a_k=a_{k-1}+3\) for all integers \(k\geq1\text{.}\)
4.
Let \(b_0, b_1, b_2, \ldots\) be the sequence defined by the formula \(b_n=4^n\text{,}\) for all integers \(n\geq 0\text{.}\) Show that this sequence satisfies the recurrence relation \(b_k=4b_{k-1}\) for all integers \(k\geq1\text{.}\)
5.
Let \(c_0, c_1, c_2, \ldots\) be the sequence defined by the formula \(c_n=2+n\text{,}\) for all integers \(n\geq 0\text{.}\) Show that this sequence satisfies the recurrence relation
\begin{equation*}
c_k=2c_{k-1}-c_{k-2}.
\end{equation*}
6.
Let \(F_0, F_1, F_2, \ldots\) be the Fibonacci sequence. Prove that
\begin{equation*}
F_k=3F_{k-3}+2F_{k-4}
\end{equation*}
for all integers \(k\geq 4\text{.}\)
7.
It turns out that the Fibonacci sequence satisfies the following explicit formula:
\begin{equation*}
F_n=\frac{1}{\sqrt{5}}\Biggl[\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{n+1}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{n+1}\Biggr].
\end{equation*}
Verify that the sequence defined by this explicit formula satisfies the Fibonacci recurrence relation \(F_{k}=F_{k-1}+F_{k-2}\) for all integers \(k\geq 2\text{.}\)
You have attempted
of
activities on this page.
