This is the 7th part of our series on sequences. Today we will learn how to solve a linear recurrence equation in the case when the characteristic equation has complex roots. In this case, we can express the complex roots of the characteristic equation in trigonometric form and then use de Moivre's identity to obtain a trigonometric formula for the sequence.
Suppose we have a sequence $\{f_n\}$ of real numbers that satisfies the following linear 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.$$
Here, the coefficients $a_0, a_1, \dots, a_k$ are real numbers but the characteristic equation $$a_k ~x^k + a_{k−1} ~x^{k−1} + \dots + a_1 ~x + a_0=0$$ has complex roots. We will classify the roots into two groups:
- Real roots: suppose that the characteristic equation has $t$ real roots $x_1$, $x_2$, ..., $x_t$, where $x_1$ is a root of multiplicity $u_1$, $x_2$ is a root of multiplicity $u_2$, etc...
- Complex roots: suppose that the characteristic equation has $s$ pairs of complex roots $z_1$, $\overline{z_1}$, $z_2$, $\overline{z_2}$, ..., $z_s$, $\overline{z_s}$, where $z_1$, $\overline{z_1}$ is a root pair of multiplicity $v_1$, $z_2$, $\overline{z_2}$ is a root pair of multiplicity $v_2$, etc...
By the method that we learned in previous posts, we can show that the general formula for the sequence is $$f_n = p_1(n) ~x_1^{n} + \dots + p_t(n) ~x_t^{n} + q_1(n) ~z_1^{n} + \overline{q_1}(n) ~\overline{z_1}^{n} + \dots + q_s(n) ~z_s^{n} + \overline{q_s}(n) ~\overline{z_s}^{n},$$ where
- $p_1(n)$, ..., $p_t(n)$ are polynomials of real coefficients whose degrees are less than $u_1$, ..., $u_t$, respectively;
- $q_1(n)$, ..., $q_s(n)$ are polynomials of complex coefficients whose degrees are less than $v_1$, ..., $v_s$, respectively.
Let us look at an example.
Problem 1: Determine a general formula for the sequence $$f_0=2, ~f_1=12, ~f_n= 3 f_{n−1} − 9 f_{n−2}.$$
Solution: From the recurrence equation $f_n= 3 f_{n−1} − 9 f_{n−2}$ we have the following characteristic equation $$x^2 − 3x + 9 =0.$$
We have $$\Delta = 3^2 - 4 \times 9 = - 27 < 0,$$ $$\pm ~\sqrt{\Delta} = \pm ~ 3 \sqrt{3} ~i,$$
so the quadratic equation has two complex roots $$z_1 = \frac{3 + 3 \sqrt{3} i}{2}, ~~~\overline{z_1} = \frac{3 - 3 \sqrt{3} i}{2}.$$
Thus the sequence is of the following form $$f_n = \alpha ~ \left(\frac{3 + 3 \sqrt{3} i}{2}\right)^n + \overline{\alpha} ~ \left(\frac{3 - 3 \sqrt{3} i}{2}\right)^n.$$
With $n=0,1$, we have $$f_0= \alpha + \overline{\alpha} = 2,$$ $$f_1= \alpha ~ \frac{3 + 3 \sqrt{3} i}{2} + \overline{\alpha} ~ \frac{3 - 3 \sqrt{3} i}{2} = 12.$$
From the second equation, we have $$f_1= \frac{3}{2} (\alpha + \overline{\alpha}) + \frac{3 \sqrt{3} i}{2} (\alpha - \overline{\alpha}) = 12.$$
Thus, $$\alpha - \overline{\alpha} = -2 \sqrt{3} ~i.$$
It follows that $$\alpha = 1 - \sqrt{3} ~i, ~~~ \overline{\alpha} = 1 + \sqrt{3} ~i.$$
Therefore, the general formula for the sequence is $$f_n = (1 - \sqrt{3} ~i) ~ \left(\frac{3 + 3 \sqrt{3} i}{2}\right)^n + (1 + \sqrt{3} ~i) ~ \left(\frac{3 - 3 \sqrt{3} i}{2}\right)^n.$$
We know that in an exponentiation formula of complex numbers, it is very convenient to use trigonometric form because we can utilize de Moivre's identity.
Let us express the complex roots $$\frac{3 \pm 3 \sqrt{3} i}{2}$$ in trigonometric form.
First, let us calculate their absolute value $$\left| \frac{3 \pm 3 \sqrt{3} i}{2} \right| = \sqrt{ \left(\frac{3}{2}\right)^2 + \left(\frac{3\sqrt{3}}{2}\right)^2 } = \sqrt{ \frac{9}{4} + \frac{27}{4} } = \sqrt{9} = 3.$$
Now we can write them in trigonometric form $$\frac{3 \pm 3 \sqrt{3} i}{2} = 3 ~\left( \frac{1}{2} \pm i ~\frac{\sqrt{3}}{2} \right) = 3 (\cos{\frac{\pi}{3}} \pm i ~ \sin{\frac{\pi}{3}}).$$
By de Moivre's identity, we have
$$f_n = (1 - \sqrt{3} ~i) ~ \left(\frac{3 + 3 \sqrt{3} i}{2}\right)^n + (1 + \sqrt{3} ~i) ~ \left(\frac{3 - 3 \sqrt{3} i}{2}\right)^n$$ $$= (1 - \sqrt{3} ~i) ~3^n ~ (\cos{\frac{\pi}{3}} + i ~ \sin{\frac{\pi}{3}})^n + (1 + \sqrt{3} ~i) ~ 3^n ~ (\cos{\frac{\pi}{3}} - i ~ \sin{\frac{\pi}{3}})^n $$ $$= 3^n (1 - \sqrt{3} ~i) (\cos{\frac{n \pi}{3}} + i ~ \sin{\frac{n \pi}{3}}) + 3^n (1 + \sqrt{3} ~i) (\cos{\frac{n \pi}{3}} - i ~ \sin{\frac{n \pi}{3}})$$ $$= 3^n (2 \cos{\frac{n \pi}{3}} + 2 \sqrt{3} \sin{\frac{n \pi}{3}}).$$
Thus, we obtain another general formula for the sequence
$$f_n = (1 - \sqrt{3} ~i) ~ \left(\frac{3 + 3 \sqrt{3} i}{2}\right)^n + (1 + \sqrt{3} ~i) ~ \left(\frac{3 - 3 \sqrt{3} i}{2}\right)^n$$ $$= 3^n ~ \left(2 ~\cos{\frac{n \pi}{3}} + 2 \sqrt{3} ~\sin{\frac{n \pi}{3}} \right).$$
Trigonometric formula for sequence
Let us now present a method to determine a trigonometric formula for a general sequence.
Suppose we want to determine a general formula for a real number sequence $\{f_n\}$ that satisfies the following 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.$$
The coefficients $a_0, a_1, \dots, a_k$ are real numbers but the characteristic equation $$a_k ~x^k + a_{k−1} ~x^{k−1} + \dots + a_1 ~x + a_0=0$$ has complex roots. We classify the roots into two groups:
- Real roots: suppose that the characteristic equation has $t$ real roots $x_1$, $x_2$, ..., $x_t$, where $x_1$ is a root of multiplicity $u_1$, $x_2$ is a root of multiplicity $u_2$, etc...
- Complex roots: suppose that the characteristic equation has $s$ pair of complex roots
$z_1$, $\overline{z_1}$, $z_2$, $\overline{z_2}$, ..., $z_s$,
$\overline{z_s}$, where $z_1$, $\overline{z_1}$ is a root pair of
multiplicity $v_1$, $z_2$, $\overline{z_2}$ is a root pair of
multiplicity $v_2$,
etc...
Write these complex roots in trigonometric form as follows $$z_1, \overline{z_1} = r_1 (\cos{\phi_1} \pm i ~ \sin{\phi_1}); ~\dots; ~z_s, \overline{z_s} = r_s (\cos{\phi_s} \pm i ~ \sin{\phi_s}).$$
- $p_1(n)$, ..., $p_t(n)$ are polynomials of real coefficients whose degrees are less than $u_1$, ..., $u_t$, respectively;
- $g_1(n)$, $h_1(n)$, ..., $g_s(n)$, $h_s(n)$ are polynomials of real coefficients whose degrees are less than $v_1$, ..., $v_s$.
In the following problem, we will only derive the trigonometric formula for the sequence.
Problem 2: Determine a general formula for the sequence $$f_0=5, ~f_1=12, ~f_n= 6 f_{n−1} − 12 f_{n−2}.$$
Solution: From the recurrence equation $f_n= 6 f_{n−1} − 12 f_{n−2}$ we have the following characteristic equation $$x^2 − 6x + 12 =0.$$
This quadratic equation has a pair of complex roots $3 \pm i~ \sqrt{3}$.
We will express the roots $3 \pm i~ \sqrt{3}$ in trigonometric form.
First, we calculate the absolute value $$\left| 3 \pm i~ \sqrt{3} \right| = \sqrt{3^2 + (\sqrt{3})^2} = \sqrt{12} = 2 \sqrt{3}.$$
Thus, $$3 \pm i~ \sqrt{3} = 2 \sqrt{3} ~\left( \frac{\sqrt{3}}{2} \pm i ~\frac{1}{2} \right) = 2 \sqrt{3} (\cos{\frac{\pi}{6}} \pm i ~ \sin{\frac{\pi}{6}}).$$
The sequence has the following form $$f_n = (2 \sqrt{3})^n ~ (\alpha ~ \cos{\frac{n \pi}{6}} + \beta ~ \sin{\frac{n \pi}{6}} ).$$
With $n=0,1$, we have $$f_0= \alpha = 5,$$ $$f_1= 2 \sqrt{3} (\alpha ~\frac{\sqrt{3}}{2} + \beta ~\frac{1}{2}) = 12.$$
Solving these equations we obtain $\alpha = 5$ and $\beta = - \sqrt{3}$.
Therefore, $$f_n = (2 \sqrt{3})^n ~ (5 ~ \cos{\frac{n \pi}{6}} - \sqrt{3} ~ \sin{\frac{n \pi}{6}} ).$$
Let us stop here for now, in the next post we will look at more examples of using complex numbers in sequence. Hope to see you again then.
Homework.
1. Determine a general formula for the sequence $$f_0=1, ~f_1=4, ~f_n= 2 f_{n−1} − 4 f_{n−2}.$$
2. Determine a general formula for the sequence $$f_0=2, ~f_1=4, ~f_n = f_{n−1} − f_{n−2}.$$
3. Determine a general formula for the sequence $$f_0=5, ~f_1=6, ~f_n = 3 f_{n−1} − 3 f_{n−2}.$$
4. Determine a general formula for the sequence $$f_0=2, ~f_1=1, ~f_2=10, ~f_n= 4 f_{n−1} − 24 f_{n−3}.$$
5. Determine a recurrence condition for the sequence $$f_n = (5 ~ \cos{\frac{n \pi}{4}} + 3 ~ \sin{\frac{n \pi}{4}}) (\sqrt{2})^n .$$
6. Determine a recurrence condition for the sequence $$f_n = \cos{\frac{n \pi}{4}} + \sin{\frac{n \pi}{4}}.$$
7. Determine a recurrence condition for the sequence $$f_n = 2n + 1 + (3 ~ \cos{\frac{n \pi}{6}} - \sqrt{3} ~ \sin{\frac{n \pi}{6}}) ~(\sqrt{3})^n.$$
8. Determine a recurrence condition for the sequence $$f_n = (2n \cos{\frac{n \pi}{3}} - 2 \sqrt{3} ~ \sin{\frac{n \pi}{3}} ) ~ 3^n.$$
Answer.
1. $f_n = (\cos{\frac{n \pi}{3}} + \sqrt{3} ~ \sin{\frac{n \pi}{3}} ) ~ 2^n.$
2. $f_n = 2 ~ \cos{\frac{n \pi}{3}} + 2 \sqrt{3} ~ \sin{\frac{n \pi}{3}} .$
3. $f_n = (5 ~ \cos{\frac{n \pi}{6}} - \sqrt{3} ~ \sin{\frac{n \pi}{6}}) ~(\sqrt{3})^n .$
4. $f_n = (-2)^n + (2 \sqrt{3})^n ~ \cos{\frac{n \pi}{6}}.$
5. $f_0 = 5, ~~f_1 = 8, ~~f_n = 2 f_{n-1} - 2 f_{n-2}.$
6. $f_0 = 1, ~~f_1 = \sqrt{2}, ~~f_n = \sqrt{2} f_{n-1} - f_{n-2}.$
7. $f_0 = 4, ~~f_1 = 6, ~~f_2 = 5, ~~f_3 = -2, ~~f_n= 5 f_{n−1} − 10 f_{n−2} + 9 f_{n-3} - 3 f_{n-4}.$
8. $f_0 = 0, ~~f_1 = -6, ~~f_2 = -45, ~~f_3 = -162, ~~f_n= 6 f_{n−1} − 27 f_{n−2} + 54 f_{n-3} - 81 f_{n-4}.$