Sequence - Part 2

This is the second part of our series on sequences. Please have a careful read of Part 1 before you continue to this post. Today, we will introduce some more terminologies about sequences and we will present a general method to solve a linear recurrence equation.

Let us start with a simple sequence $$f_0 = 3, ~~~f_{n} = 2 f_{n-1}.$$

This sequence $\{f_n\}$ is called a geometric sequence because each term $f_n$ is equal to the previous term $f_{n-1}$ times a fixed number, which is $2$ in this case. So $$f_0=3, ~f_1 = 6, ~f_2 = 12, ~f_3 = 24, ~f_4 = 48, ~f_5 = 96, ~f_6 = 192, \dots$$  

We have $$f_n = 2 f_{n-1} = 2^2 f_{n-2} = 2^3 f_{n-3} = \dots = 2^n f_0 = 3 \times 2^n.$$

Thus, the general formula for the sequence $\{f_n\}$ is $f_n = 3 \times 2^n$.

The defining condition $$f_{n} = 2 f_{n-1}$$ of the sequence $\{f_n\}$ is called a linear recurrence equation of degree 1, this is because $f_n$ is determined based on one previous term $f_{n-1}$. 

Now let us look at a linear recurrence equation of degree 2. We are aiming to find a general formula for the following sequence $$f_0=7, ~~f_1=1, ~~f_n = 2 f_{n-1} + 3f_{n-2}.$$ The recurrence equation $$f_n = 2 f_{n-1} + 3 f_{n-2}$$ of this sequence is called a recurrence equation of degree 2 because $f_n$ is defined based on two previous terms: $f_{n-1}$ and $f_{n-2}$.

The defining condition of this sequence has two parts:

• Part 1: is called the initial condition, that is $f_0 = 7$, $f_1 = 1$.
• Part 2: is called the recurrence equation, which is $f_{n} = 2 f_{n-1} + 3 f_{n-2}$.

Clearly, there is exactly one sequence satisfies both conditions  $$f_0=7, ~f_1=1, ~f_n = 2 f_{n-1} + 3f_{n-2}.$$

But, there are infinitely many sequences that satisfy the recurrence equation part  $$f_n = 2 f_{n-1} + 3f_{n-2}.$$


We make an observation that if all the sequences $\{a_n\}$, $\{b_n\}$, $\dots$, $\{c_n\}$ satisfy the same recurrence equation $$f_n = 2 f_{n-1} + 3f_{n-2}$$ then its linear sum, the sequence $\alpha ~ \{a_n\} + \beta ~ \{b_n\} + \dots + \gamma ~ \{c_n\}$, also satisfies this same recurrence equation $$f_n = 2 f_{n-1} + 3f_{n-2}.$$ It is not hard to prove this fact, indeed, we have already proved it in Part 1. This observation looks simple but it is crucially important. Please make sure that you understand and remember this fact because we are going to use it very often.

In the exercise below, we will temporarily ignore the initial condition and only focus on the recurrence equation part. We will find all sequences of the form $f_n = z^n$ that satisfy the recurrence equation.

Problem 1: Determine all sequences of the form $f_n = z^n$ that satisfy $f_n = 2 f_{n-1} + 3f_{n-2}$.

Solution: Substituting $f_n = z^n$ into the equation $f_n = 2 f_{n-1} + 3f_{n-2}$ we have $$z^n = 2 z^{n-1} + 3 z^{n-2}.$$
Case $z = 0$: we have the sequence $f_n = 0$.

Case $z \neq 0$: dividing both sides of the above equation by $z^{n-2}$ we obtain $$z^2 = 2 z + 3.$$

Solving the quadratic equation $$x^2 - 2 x - 3 =0$$ we have two roots $x = -1$ and $x=3$.

So $z =-1$ or $z =  3$.

Therefore, in total, we have three sequences of the form $f_n = z^n$ that satisfy the recurrence equation $f_n = 2 f_{n-1} + 3 f_{n-2}$, they are $$f_n = 0, ~f_n =  (-1)^n , ~f_n = 3^n.$$



From Problem 1, by taking linear summation, we obtain an infinite number of sequences that satisfy the recurrence equation $f_n = 2 f_{n-1} + 3f_{n-2}$.

For any two numbers $\alpha$ and $\beta$, the sequence $$f_n = \alpha ~ (-1)^n + \beta ~ 3^n$$ satisfies the condition  $$f_n = 2 f_{n-1} + 3 f_{n-2}.$$

Problem 2: Determine the values of $\alpha$ and $\beta$ such that the sequence $$f_n =  \alpha ~ (-1)^n + \beta ~ 3^n$$ satisfies the following condition $$f_0 = 7, ~f_1 =1, ~f_n = 2 f_{n-1} + 3 f_{n-2}.$$

Solution: Take $n=0$ and $n=1$, we have

$$f_0 = \alpha + \beta = 7,$$

$$f_1 =  - \alpha + 3 \beta = 1.$$

Solving these equations we have $\alpha = 5$ and $\beta = 2$. Therefore, $$f_n = 5 \times (-1)^n + 2 \times 3^n .$$

We are now moving on to a recurrence equation of degree 3 $$f_{n} = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}.$$


Problem 3: Determine all sequences of the form $f_n = z^n$ that satisfy $f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}$.

Solution: Substituting $f_n = z^n$ into the equation $f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}$ we have $$z^n = 4 z^{n-1} - z^{n-2} - 6 z^{n-3}.$$
Case $z = 0$: we have the sequence $f_n = 0$.

Case $z \neq 0$: dividing both sides of the above equation by $z^{n-3}$ we obtain $$z^3 = 4 z^2 - z -6.$$

Solving the cubic equation $$x^3 - 4 x^2 + x + 6 =0$$ we have three roots $x = -1$, $x=2$ and $x=3$.

So $z =-1$, $z=2$ or $z =  3$.

Therefore, in total, we have four sequences of the form $f_n = z^n$ that satisfy the recurrence equation $f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}$, they are $$f_n = 0, ~f_n =  (-1)^n , ~f_n = 2^n, ~f_n = 3^n.$$

From Problem 3, if we take linear summation, we will obtain an infinite number of sequences that satisfy the recurrence equation $f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}$.

For any $\alpha$, $\beta$ and $\gamma$, the sequence $$f_n = \alpha ~ (-1)^n + \beta ~ 2^n + \gamma ~ 3^n$$ satisfies the condition $$f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}.$$

Problem 4: Determine the values of $\alpha$, $\beta$ and $\gamma$ such that the sequence $$f_n = \alpha ~ (-1)^n + \beta ~ 2^n + \gamma ~ 3^n$$ satisfies the following condition $$f_0 = 2, ~f_1 =-1, ~f_2 = 7, ~f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3}.$$

Solution: Take $n=0,1,2$, we have

$$f_0 = \alpha + \beta + \gamma = 2,$$ $$f_1 = - \alpha + 2 ~\beta + 3 ~\gamma = -1,$$ $$f_2 = \alpha + 4 ~\beta + 9 ~\gamma = 7.$$

Solving these equations we have $\alpha = 2$, $\beta = -1$ and $\gamma = 1$. Therefore, $$f_n = 2 (-1)^n - 2^n + 3^n.$$



By now you may have already recognized the pattern.  Recall that with the recurrence equation of degree 2 $$f_{n} = 2 f_{n-1} + 3 f_{n-2},$$ we solve the quadratic equation $$x^2 = 2 x + 3,$$ and with the recurrence equation of degree 3 $$f_n = 4 f_{n-1} - f_{n-2} - 6 f_{n-3},$$ we solve the cubic equation $$x^3 = 4 x^2 - x -6.$$

In general, if we have a linear recurrence equation of degree $k$ $$a_k f_{n} + a_{k-1} f_{n-1} + a_{k-2} f_{n-2} + \dots + a_0 f_{n-k}=0$$ then we need to solve for the following equation of degree $k$ $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=0.$$ This equation is called the characteristic equation of the recurrence equation.

General method to solve a linear recurrence equation

To determine the general formula for the sequence $\{f_n\}$ that satisfies the recurrence equation $$a_k f_{n} + a_{k-1} f_{n-1} + a_{k-2} f_{n-2} + \dots + a_0 f_{n-k}=0$$ with the initial condition on the values of $f_0, f_1, \dots, f_{k-1}$, we follow the following steps.

Step 1. Solve the recurrence equation.
Form the characteristic equation $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=0$$ and determine its roots. 

Suppose that the characteristic equation has $k$ roots $x_1, \dots, x_k$. Then for any $\alpha_1, \dots, \alpha_k$, the sequence $$f_n = \alpha_1 ~ x_1^n + \dots + \alpha_k ~ x_k^n$$ satisfies the recurrence equation $$a_k f_{n} + a_{k-1} f_{n-1} + a_{k-2} f_{n-2} + \dots + a_0 f_{n-k}=0.$$  

Step 2. Solve the initial condition.
Substituting the values of $f_0, f_1, \dots, f_{k-1}$ into the equation $$f_n = \alpha_1 ~ x_1^n + \dots + \alpha_k ~ x_k^n$$ and solve for $\alpha_1, \dots, \alpha_k$.

Let us apply this algorithm for an example.

Problem 5: Determine the formula for the sequence $$f_0 = 0, ~f_1 =1, ~f_n = 5 f_{n-1} - 6 f_{n-2}.$$

Solution: The characteristic equation of the recurrence equation $f_n - 5 f_{n-1} + 6 f_{n-2}=0$ is $$x^2 - 5 x + 6 = 0.$$ This equation has two roots $x_1 = 2$ and $x_2=3$. So $$f_n = \alpha_1 2^n + \alpha_2 3^n.$$ With $n=0,1$, we have $$f_0 = \alpha_1 + \alpha_2 = 0,$$ $$f_1 = 2 \alpha_1 + 3 \alpha_2 = 1.$$ Solving this equations, we obtain $\alpha_1 = -1$ and $\alpha_2 = 1$. Therefore, $$f_n = 3^n - 2^n.$$

There are many more examples in the homework section. Please try these problems to get used to the above algorithm.

We remark that the above algorithm only works if the characteristic equation $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=0$$ has $k$ distinct roots $x_1, \dots, x_k$.

If the characteristic equation has multiple roots then the above algorithm no longer works (see an example of this case in the exercise number 11 in the homework section). We will deal with this scenario in our future post.  

Let us stop here for now. See you again in the next post.

Homework.

1. What is the characteristic equation for the recurrence equation $f_n = 2 f_{n-1}$?
Find the formula for the sequence $f_0 = 3, ~f_n = 2 f_{n-1}.$

2. Determine the formula for the sequence $$f_0 = 8, ~f_1 =2, ~f_n = 2 f_{n-1} + 8 f_{n-2}.$$

3. Determine the formula for the sequence  $$f_0 = 5, ~f_1 =20, ~f_n = 2 f_{n-1} + 8 f_{n-2}.$$

4. Determine the formula for the sequence  $$f_0 = 1, ~f_1 =-2, ~f_n = 2 f_{n-1} + 8 f_{n-2}.$$

5. Determine the formula for the Fibonacci sequence $$f_0 = 0, ~f_1 =1, ~f_n = f_{n-1} + f_{n-2}.$$

6. Determine the formula for the sequence  $$f_0 = 1, ~f_1 =2, ~f_n = 2 f_{n-1} + 5 f_{n-2}.$$

7. Determine the formula for the sequence  $$f_0 = 4, ~f_1 =4, ~f_2 = 38, ~f_n = f_{n-1} + 14 f_{n-2} - 24 f_{n-3}.$$

8. Determine the formula for the sequence  $$f_0 = 2, ~f_1 =3, ~f_2 = 17, ~f_n = f_{n-1} + 14 f_{n-2} - 24 f_{n-3}.$$

9. What is the characteristic equation of the recurrence equation $f_n = 13 f_{n-2} + 12 f_{n-3}$?
Determine the formula for the sequence $$f_0 = 8, ~f_1 =13, ~f_2 = 99, ~f_n = 13 f_{n-2} + 12 f_{n-3}.$$

10. Find the recurrence equation for the sequence $f_n = 5 \times 3^n - 4^n$.

11. Use the above algorithm for the sequence $$f_0 = 3, ~f_1 = 2, ~f_n = 4 f_{n-1} - 4 f_{n-2}$$ and see at which step the algorithm will fail.





Answer to homework.

1. Characteristic equation is $x - 2 = 0$.

2. $f_n =  5 \times (-2)^n + 3 \times 4^n$

3. $f_n = 5 \times 4^n$

4. $f_n = (-2)^n$

5. Fibonacci sequence

6. $f_n = \frac{1}{2 \sqrt{6}} [(1+\sqrt{6})^{n+1} - (1-\sqrt{6})^{n+1}]$

7. $f_n = (-4)^n + 2^n + 2 \times 3^n$

8. $f_n = (-1)^n + 4^n$

9. Characteristic equation is $x^3 - 13 x - 12=0$.
$f_n = 2 \times (-3)^n + (-1)^n + 5 \times 4^n$

10. $f_0= 4, ~f_1 = 11, ~f_n = 7 f_{n-1} - 12 f_{n-2}$.

11. It fails at step 2.