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.

**L**et 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}.$

## No comments:

## Post a Comment