Definition 2.4.3.1.
A recurrence relation for a sequence \(\seq{a_n}{n}\) is an equation that expresses \(a_n\) in terms of one or more of the previous terms of the sequence.
Subsection 2.4.3 Recurrence relations
Example 2.4.3.2. Compound interest.
Suppose we deposit \(P_0\) dollars in a savings account that yields 3% interest per year, compounded annually. Find a formula for the amount in the account after \(n\) years.
Solution.
Let \(\seq{P_n}{n}\) be the sequence where the \(n\) th term is the amount in the account after \(n\) years. Then
\begin{align*}
P_0 \amp = P_0 \\
P_1 \amp = P_0 + 0.03 P_0 = 1.03P_0 \\
P_2 \amp = P_1 + 0.03 P_1 = 1.03P_1 = (1.03)^2 P_0 \\
P_3 \amp = P_2 + 0.03 P_2 = 1.03P_2 = (1.03)^3 P_0 \\
\vdots \amp \quad \vdots \\
P_n \amp = 1.03 P_{n - 1} = (1.03)^n P_0.
\end{align*}
Example 2.4.3.3. Recurrence relation.
Suppose \(\seq{a_n}{n}\) is a sequence that satisfies the recurrence relation \(a_n = -a_{n - 1} + 1\) for \(n = 1, 2, 3, \dots\text{,}\) and suppose \(a_0 = 2\text{.}\)
Solution.
Then
\begin{align*}
a_0 \amp = 2 \\
a_1 \amp = -a_0 + 1 = -2 + 1 = -1 \\
a_2 \amp = -a_1 + 1 = -(-1) + 1 = 2 \\
a_3 \amp = -a_2 + 1 = -2 + 1 = -1 \\
a_4 \amp = -a_3 + 1 = -(-1) + 1 = 2 \\
\vdots \amp \quad \vdots \\
a_n \amp =
\begin{cases}
2 \amp \text{ if }n\text{ is even,}\\
-1 \amp \text{ if }n\text{ is odd.}
\end{cases}
\end{align*}
Definition 2.4.3.4.
A solution of a recurrence relation is a sequence whose terms satisfy the recurrence relation.
We call a solution \(\seq{a_n}{n}\) to a recurrence relation a closed formula if the expression for \(a_n\) can be evaluated in a fixed finite number of operations on \(n\text{.}\)
Example 2.4.3.5. Solution of a recurrence relation.
Is \(\seq{a_n}{n}\text{,}\) where \(a_n = 3n\) for \(n = 0, 1, 2, \dots\) a solution of the recurrence relation \(a_n = 2a_{n - 1} - a_{n - 2}\) for \(n = 2,3, \dots\) ?
Solution.
We just need to check if the terms of the sequence satisfy the recurrence relation. We compute for \(n \geq 2\text{,}\)
\begin{align*}
2a_{n - 1} - a_{n - 2} \amp = 2(3(n - 1)) - (3(n - 2)) \\
\amp= (6n - 6) - (3n- 6) = 3n = a_n.
\end{align*}
Thus \(a_n = 3n\) is a solution of the recurrence relation.
Note: It is easy to check that the sequence \(\seq{b_n}{n}\text{,}\) defined by \(b_n = 5\) for \(n = 0, 1, 2, \dots\) is also a solution of the recurrence relation. In particular, a recurrence relation can have more than one solution.
Example 2.4.3.6. Factorial as the solution of a recurrence relation.
The sequence \(\seq{a_n}{n}\) defined by \(a_n = n!\) for \(n = 1, 2, 3,\dots\) is a solution to the recurrence relation \(a_n = n a_{n - 1}\text{,}\) since \(n! = n((n - 1)!)\text{.}\)
Next, we define a famous sequence definied by a recurrence relation and two base cases which is named for a twelfth century Italian mathematician.
Definition 2.4.3.7.
The Fibonacci sequence \(f_0, f_1, f_2, \dots\) is defined by the initial conditions \(f_0 = 0\text{,}\) \(f_1 = 1\text{,}\) and the recurrence relation
\begin{equation*}
f_n = f_{n - 1} + f_{n - 2},
\end{equation*}
for \(n = 2, 3, \dots\text{.}\)
Example 2.4.3.8. First terms of the Fibonacci sequence.
It is straightforward to compute more terms of the Fibonacci sequence.
\begin{align*}
f_0 \amp = 0 \\
f_1 \amp = 1 \\
f_2 \amp = f_1 + f_0 = 1 + 0 = 1 \\
f_3 \amp = f_2 + f_1 = 1 + 1 = 2 \\
f_4 \amp = f_3 + f_2 = 2 + 1 = 3 \\
f_5 \amp = f_4 + f_3 = 3 + 2 = 5
\end{align*}
Using linear algebra, we can find a closed formula for the terms of the Fibonacci sequence. We will not derive this formula in this course, but you will be asked to prove it in Exercise 3.2.3.5.
https://xkcd.com/244/). I may have also tossed one of a pair of teleportation rings into the ocean, with interesting results.
