Today we will begin our first post of a series on recurrence sequences. The purpose of this series is to show you how to derive a general formula for a sequence that satisfies a linear recurrence equation. We start with some basic operations on sequences. We will learn about addition of sequences and multiplication of a sequence with a number.
Usually we talk about addition of numbers such as $2+3=5$, but today, you will see that we can actually do addition on sequences.
Suppose that $\{ a_n \}$ and $\{ b_n \}$ are two sequences. We can add them together to obtain a new sequence $\{c_n\}$ as $$c_n = a_n + b_n.$$
Below is an example, by adding term by term of the two sequences $\{ a_n \}$ and $\{ b_n \}$ we obtain the sequence $\{ c_n \}$.
 |
| Sum of two sequences is a sequence $\{ c_n \} = \{ a_n \} + \{ b_n \}$ |
In a similar way, we can subtract two sequence as $\{c_n\} = \{ a_n \} - \{ b_n \}$, or, we can add/subtract three or four sequences together as $\{e_n\} = \{ a_n \} - \{ b_n \} + \{ c_n\} - \{ d_n \}$.
Multiplication of a sequence with a number
Now suppose $\{ a_n \}$ is a sequence and $\alpha$ is a number, we can multiply the number $\alpha$ with the sequence $\{ a_n \}$ to obtain a new sequence $\{ b_n \}$ as $$b_n = \alpha ~ a_n.$$
In the example below, we multiply each term of the sequence $\{ a_n \}$ with the number $\alpha = 2$ and obtain the sequence $\{ b_n \} = 2 \times \{ a_n \}$.
Linear summation of sequences
Combining both operations, addition and multiplication, we can form a new sequence such as $$\{d_n\} = \alpha \{ a_n \} + \beta \{ b_n \} + \gamma \{ c_n \},$$ where $\alpha$, $\beta$, $\gamma$ are some constant numbers.
We call this sequence $\{d_n\}$ a linear sum of the sequences $\{ a_n \}$, $\{ b_n \}$, $\{ c_n \}$.
In the example below, we multiply each term of the sequence $\{ a_n \}$ with the number $\alpha = 2$ and obtain the sequence $\{ b_n \} = 2 \times \{ a_n \}$.
 |
| Multiply a sequence with a number: $\{ b_n \} = 2 \times \{ a_n \}$ |
Linear summation of sequences
Combining both operations, addition and multiplication, we can form a new sequence such as $$\{d_n\} = \alpha \{ a_n \} + \beta \{ b_n \} + \gamma \{ c_n \},$$ where $\alpha$, $\beta$, $\gamma$ are some constant numbers.
We call this sequence $\{d_n\}$ a linear sum of the sequences $\{ a_n \}$, $\{ b_n \}$, $\{ c_n \}$.
In the following exercise, we will see that if each of the summand sequences satisfies a linear recurrence equation then their linear sums also satisfy the same recurrence equation.
Problem 1: Suppose that the sequence $\{a_n\}$ satisfies the following recurrence equation $$a_n = 5 a_{n-1} - 6 a_{n-2}.$$
And suppose that the sequence $\{b_n\}$ also satisfies the same equation $$b_n = 5 b_{n-1} - 6 b_{n-2}.$$
Then the sum of $\{a_n\}$ and $\{b_n\}$, the sequence $\{c_n\} = \{a_n\} + \{b_n\}$ satisfies that same recurrence equation $$c_n = 5 c_{n-1} - 6 c_{n-2}.$$
In general, for any numbers $\alpha$ and $\beta$, the linear sum $\{d_n\} = \alpha~ \{a_n\} + \beta~ \{b_n\}$ also satisfies the equation $$d_n = 5 d_{n-1} - 6 d_{n-2}.$$
Solution: We have
So the sequence $\{c_n\}$satisfies the condition $c_n = 5 c_{n-1} - 6 c_{n-2}$.
Similarly,
So the sequence $\{d_n\}$ also satisfies the equation $d_n = 5 d_{n-1} - 6 d_{n-2}$.
Problem 2: Determine all sequences of the form $f_n = z^n$ such that $f_n = 5 f_{n-1} - 6 f_{n-2}$.
Solution: Substituting $f_n = z^n$ into the equation $f_n = 5 f_{n-1} - 6 f_{n-2}$ we have $$z^n = 5 z^{n-1} - 6 z^{n-2}.$$
Case $z = 0$: we obtain the sequence $f_n = 0$.
Case $z \neq 0$: dividing both sides of the above equation by $z^{n-2}$ we have $$z^2 = 5 z - 6.$$
Solving the quadratic equation $$x^2 - 5 x + 6 =0$$ we obtain two roots $x = 2$ and $x=3$.
So $z = 2$ or $z = 3$, which give us two sequences $f_n = 2^n$ and $f_n = 3^n$.
In summary, there are altogether three sequences of the form $f_n = z^n$ that satisfy the recurrence equation $f_n = 5 f_{n-1} - 6 f_{n-2}$, these are $f_n = 0$, $f_n = 2^n$ and $f_n = 3^n$.
Before you continue, please verify for yourselves that the sequences $f_n = 2^n$ and $f_n = 3^n$ do indeed satisfy the recurrence equation $f_n = 5 f_{n-1} - 6 f_{n-2}$.
What can we say from the above two problems? From Problem 2, we know that the two sequences $\{ 2^n \}$ and $\{3^n\}$ satisfy the recurrence equation $$f_n = 5 f_{n-1} - 6 f_{n-2}.$$
From Problem 1, we can take linear sum of these two sequences, $\{ \alpha ~ 2^n + \beta ~ 3^n\}$, then this sequence also satisfies the same recurrence equation $$f_n = 5 f_{n-1} - 6 f_{n-2}.$$
Here we can take $\alpha$ and $\beta$ to be any values we want.
Let us summarize the result that we have just obtained
For any two arbitrary numbers $\alpha$ and $\beta$, the sequence determined by the formula $$f_n = \alpha ~ 2^n + \beta ~ 3^n$$ satisfies the following recurrence equation $$f_n = 5 f_{n-1} - 6 f_{n-2}.$$
Problem 3: Determine the values of the two numbers $\alpha$ and $\beta$ such that the sequence $f_n = \alpha ~ 2^n + \beta ~ 3^n$ satisfies the following conditions $$f_0 = 1, ~f_1 =7, ~f_n = 5 f_{n-1} - 6 f_{n-2}.$$
Solution: Take $n=0$ and $n=1$, we obtain
$$f_0 = \alpha ~ 2^0 + \beta ~ 3^0 = \alpha + \beta = 1,$$
$$f_1 = \alpha ~ 2^1 + \beta ~ 3^1 = 2 ~\alpha + 3 ~\beta = 7.$$
Solving these equations, we obtain $\alpha = -4$ and $\beta = 5$. Thus, $$f_n = 5 \times 3^n - 4 \times 2^n.$$
Let us remark that there are infinitely many sequences satisfies the recurrence equation $f_n = 5 f_{n-1} - 6 f_{n-2}$. For each values of $\alpha$ and $\beta$ we obtain a sequence $f_n = \alpha ~ 2^n + \beta ~ 3^n$ that satisfies the equation $f_n = 5 f_{n-1} - 6 f_{n-2}$.
However, there exists exactly one sequence that satisfies the conditions $$f_0 = 1, ~f_1 =7, ~f_n = 5 f_{n-1} - 6 f_{n-2}.$$
In Problem 3, we have determined the formula $f_n = 5 \times 3^n - 4 \times 2^n$ for the unique sequence that satisfies the conditions $$f_0 = 1, ~f_1 =7, ~f_n = 5 f_{n-1} - 6 f_{n-2}.$$
Homework.
1. Determine the formula for the sequence $$a_0 = 0, ~a_1 =1, ~a_n = 5 a_{n-1} - 6 a_{n-2}.$$
2. Determine the formula for the sequence $$b_0 = 1, ~b_1 =1, ~b_n = 5 b_{n-1} - 6 b_{n-2}.$$
3. Determine all sequences of the form $f_n = z^n$ that satisfy the recurrence equation $f_n = 2 f_{n-1} + 3 f_{n-2}$.
4. Determine the formula for the sequence $$c_0 = 7, ~c_1 =1, ~c_n = 2 c_{n-1} + 3 c_{n-2}.$$
5. Determine the formula for the Fibonacci sequence $$F_0 = 0, ~F_1 =1, ~F_n = F_{n-1} + F_{n-2}.$$