Sequence - Part 8

In the last post, we learn how to determine a trigonometric formula for a sequence in the case when the characteristic equation has complex roots. Today we will solve more exercises for this case.



Let us recall the method to determine a trigonometric formula for a 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$ 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...
  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}).$$
   

Then the sequence can be written in trigonometric form as follows $$f_n = p_1(n) ~x_1^{n} + \dots +  p_t(n) ~x_t^{n}$$ $$+  r_1^n (g_1(n) ~\cos{n \phi_1} + h_1(n) ~ \sin{n \phi_1})  + \dots + r_s^{n}  (g_s(n) ~ \cos{n \phi_s} + h_s(n) ~ \sin{n \phi_s}),$$ where

• $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$.

Let us look at some examples.

• If the characteristic equation is factored as $(x - z_1)(x - \overline{z_1})=0$ with $$z_1, \overline{z_1} = r_1 (\cos{\phi_1} \pm i ~ \sin{\phi_1})$$ then $$f_n = (g_1 ~\cos{n \phi_1} + h_1 ~ \sin{n \phi_1}) ~r_1^n,$$ where $g_1$, $h_1$ are two real numbers.
  

• If the characteristic equation is factored as $(x - x_1)(x - z_1)(x - \overline{z_1})=0$ then $$f_n = p_1 ~x_1^n + (g_1 ~\cos{n \phi_1} + h_1 ~ \sin{n \phi_1}) ~r_1^n,$$ where $p_1$, $g_1$, $h_1$ are real numbers.

• If the characteristic equation is factored as $(x - x_1)^2 (x - z_1)(x - \overline{z_1})=0$ then $$f_n = (p_{11} + p_{12} n) ~x_1^n + (g_1 ~\cos{n \phi_1} + h_1 ~ \sin{n \phi_1}) ~r_1^n.$$

• If the characteristic equation is factored as $(x - x_1)^2 (x - z_1)^2(x - \overline{z_1})^2=0$ then $$f_n = (p_{11} + p_{12} n) ~x_1^n + [(g_{11} + g_{12} n) ~\cos{n \phi_1} + (h_{11}+ h_{12} n) ~ \sin{n \phi_1}] ~r_1^n .$$

• If the characteristic equation is factored as $(x - x_1) (x - z_1)^2(x - \overline{z_1})^2=0$ then $$f_n =p_1 ~x_1^n +  [(g_{11} + g_{12} n) ~\cos{n \phi_1} + (h_{11}+ h_{12} n) ~ \sin{n \phi_1}] ~r_1^n .$$

• If the characteristic equation is factored as $(x - z_1)(x - \overline{z_1})(x - z_2)(x - \overline{z_2})=0$ then $$f_n = (g_1 ~\cos{n \phi_1} + h_1 ~ \sin{n \phi_1}) ~r_1^n + (g_2 ~\cos{n \phi_2} + h_2 ~ \sin{n \phi_2}) ~r_2^n.$$

Let us do some exercises.

Problem 1: Determine a general formula for the sequence $$f_0=1, ~f_1=4, ~f_n= 2 f_{n−1} − 4 f_{n−2}.$$

Solution: From the recurrence equation $f_n= 2 f_{n−1} − 4 f_{n−2}$ we have the following characteristic equation $$x^2 − 2 x + 4 =0.$$
This quadratic equation has a pair of complex roots $1 \pm i~ \sqrt{3}$. We will express the roots in trigonometric form. First we calculate their absolute value $$| 1 \pm i~ \sqrt{3} | = \sqrt{1^2 + (\sqrt{3})^2} = \sqrt{4} = 2.$$

Thus, $$1 \pm i~ \sqrt{3} = 2 ~\left( \frac{1}{2} \pm i ~\frac{\sqrt{3}}{2} \right) = 2 (\cos{\frac{\pi}{3}} \pm i ~ \sin{\frac{\pi}{3}}).$$

The sequence has the following form $$f_n =  (\alpha ~ \cos{\frac{n \pi}{3}} + \beta ~ \sin{\frac{n \pi}{3}} ) ~ 2^n.$$

With $n=0,1$, we have $$f_0= \alpha = 1,$$ $$f_1=  (\alpha ~\frac{1}{2} + \beta ~\frac{\sqrt{3}}{2}) 2 = 4.$$

Solving these equations we obtain $\alpha = 1$ and $\beta = \sqrt{3}$. 

Therefore, $$f_n =  (\cos{\frac{n \pi}{3}} + \sqrt{3} ~ \sin{\frac{n \pi}{3}} ) ~ 2^n.$$



Problem 2: Determine a general formula for the sequence $$f_0=2, ~f_1=4, ~f_n = f_{n−1} − f_{n−2}.$$

Solution: From the recurrence equation $f_n= f_{n−1} − f_{n−2}$ we have the following characteristic equation $$x^2 − x + 1 =0.$$
This quadratic equation has a pair of complex roots $$\frac{1 \pm i ~\sqrt{3}}{2}.$$
We will express the roots in trigonometric form. First we calculate their absolute value $$\left| \frac{1 \pm i ~\sqrt{3}}{2} \right| = \sqrt{\left( \frac{1}{2}\right)^2 + \left( \frac{\sqrt{3}}{2}\right)^2} = 1.$$

Thus, $$\frac{1 \pm i ~\sqrt{3}}{2} = \cos{\frac{\pi}{3}} \pm i ~ \sin{\frac{\pi}{3}}.$$

The sequence has the following form $$f_n =  \alpha ~ \cos{\frac{n \pi}{3}} + \beta ~ \sin{\frac{n \pi}{3}}.$$

With $n=0,1$, we have $$f_0= \alpha = 2,$$ $$f_1=  \alpha ~\frac{1}{2} + \beta ~\frac{\sqrt{3}}{2} = 4.$$

Solving these equations we obtain $\alpha = 2$ and $\beta = 2 \sqrt{3}$. 

Therefore, $$f_n =  2 ~ \cos{\frac{n \pi}{3}} + 2 \sqrt{3} ~ \sin{\frac{n \pi}{3}} .$$



Problem 3: Determine a general formula for the sequence $$f_0=5, ~f_1=6, ~f_n = 3 f_{n−1} − 3 f_{n−2}.$$

Solution: From the recurrence equation $f_n = 3 f_{n−1} − 3 f_{n−2}$ we have the following characteristic equation $$x^2 − 3 x + 3 =0.$$
This quadratic equation has a pair of complex roots $$\frac{3 \pm i ~\sqrt{3}}{2}.$$
We will express the roots in trigonometric form. First we calculate their absolute value $$\left| \frac{3 \pm i ~\sqrt{3}}{2} \right| = \sqrt{\left( \frac{3}{2}\right)^2 + \left( \frac{\sqrt{3}}{2}\right)^2} = \sqrt{3}.$$

Thus, $$\frac{3 \pm i ~\sqrt{3}}{2} = \sqrt{3} \left( \frac{\sqrt{3}}{2} \pm i ~ \frac{1}{2}\right) = \sqrt{3} (\cos{\frac{\pi}{6}} \pm i ~ \sin{\frac{\pi}{6}}).$$

The sequence has the following form $$f_n =  (\alpha ~ \cos{\frac{n \pi}{6}} + \beta ~ \sin{\frac{n \pi}{6}}) ~(\sqrt{3})^n.$$

With $n=0,1$, we have $$f_0= \alpha = 5,$$ $$f_1=  (\alpha ~\frac{\sqrt{3}}{2} + \beta ~\frac{1}{2}) ~\sqrt{3} = 6.$$

Solving these equations we obtain $\alpha = 5$ and $\beta = - \sqrt{3}$. 

Therefore, $$f_n =  (5 ~ \cos{\frac{n \pi}{6}} - \sqrt{3} ~ \sin{\frac{n \pi}{6}}) ~(\sqrt{3})^n .$$




Problem 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}.$$

Solution: From the recurrence equation $f_n= 4 f_{n−1} − 24 f_{n−3}$ we have the following characteristic equation $$x^3 − 4 x^2 + 24 =0.$$
We can factor it as $$x^3 − 4 x^2 + 24 = (x+2)(x^2 - 6x + 12) = 0.$$
Thus, the characteristic equation has one real root (-2) and two complex roots $3 \pm i~ \sqrt{3}$.

We will express the complex roots in trigonometric form. First we calculate their 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 = \alpha ~(-2)^n + (\beta ~ \cos{\frac{n \pi}{6}} + \gamma ~ \sin{\frac{n \pi}{6}} ) ~(2 \sqrt{3})^n.$$

With $n=0,1,2$, we have $$f_0= \alpha + \beta= 2,$$ $$f_1= -2 \alpha + (\beta ~\frac{\sqrt{3}}{2} + \gamma ~\frac{1}{2}) 2 \sqrt{3} = 1,$$ $$f_2 = 4 \alpha +(\beta ~\frac{\sqrt{1}}{2} + \gamma ~\frac{\sqrt{3}}{2}) 12 =10.$$

Solving these equations we obtain $\alpha = 1$, $\beta = 1$ and $\gamma=0$. 

Therefore, $$f_n = (-2)^n + (2 \sqrt{3})^n ~  \cos{\frac{n \pi}{6}} .$$


Problem 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.$$

Solution: We need to find a characteristic equation that has two complex roots $$z_{1}, \overline{z_1} = \sqrt{2}(\cos{\frac{\pi}{4}} \pm i ~\sin{\frac{\pi}{4}}).$$

We have $$z_1 \overline{z_1}  = (\sqrt{2})^2 = 2,$$ $$z_1 + \overline{z_1} = 2 \sqrt{2} \cos{\frac{\pi}{4}} = 2 \sqrt{2} \frac{\sqrt{2}}{2} = 2,$$ therefore, by Vieta's formula, $z_1$ and $\overline{z_1}$ are two roots of the following quadratic equation $$x^2 - 2 x + 2 =0.$$

Thus, we obtain the recurrence equation $$f_n= 2 f_{n−1} − 2 f_{n−2}.$$

Combining with the initial condition, we have $$f_0 = 5, ~~f_1 = 8, ~~f_n = 2 f_{n-1} - 2 f_{n-2}.$$


Problem 6: Determine a recurrence condition for the sequence $$f_n = \cos{\frac{n \pi}{4}} + \sin{\frac{n \pi}{4}}.$$

Solution: We need to find a characteristic equation that has two complex roots $$z_{1}, \overline{z_1} = \cos{\frac{\pi}{4}} \pm i ~\sin{\frac{\pi}{4}}.$$

We have $$z_1 \overline{z_1} = 1,$$ $$z_1 + \overline{z_1} = 2 \cos{\frac{\pi}{4}} = 2 \frac{\sqrt{2}}{2} = \sqrt{2},$$ therefore, by Vieta's formula, $z_1$ and $\overline{z_1}$ are two roots of the following quadratic equation $$x^2 - \sqrt{2} x + 1 =0.$$

Thus, we obtain the recurrence equation $$f_n= \sqrt{2} f_{n−1} − f_{n−2}.$$

Combining with the initial condition, we have $$f_0 = 1, ~~f_1 = \sqrt{2}, ~~f_n = \sqrt{2} f_{n-1} - f_{n-2}.$$


Problem 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.$$

Solution: We have $$f_n = (2n+1)~ 1^n + (3 ~\cos{\frac{n \pi}{6}} - \sqrt{3} ~\sin{\frac{n \pi}{6}}) (\sqrt{3})^n.$$

We need to find a characteristic equation that has one real root $x_1 = 1$ of multiplicity 2 and two complex roots $$z_{1}, \overline{z_1} = \sqrt{3} (\cos{\frac{\pi}{6}} \pm i ~\sin{\frac{\pi}{6}}).$$

We have $$z_1 \overline{z_1} = (\sqrt{3})^2 = 3,$$ $$z_1 + \overline{z_1} = 2 \sqrt{3}~\cos{\frac{\pi}{6}} = 2 \sqrt{3} \frac{\sqrt{3}}{2} = 3,$$ therefore, by Vieta's formula, $z_1$ and $\overline{z_1}$ are two roots of the following quadratic equation $$x^2 - 3 x + 3 =0.$$

Thus, we obtain the characteristic equation $$(x - 1)^2 (x^2 - 3x + 3) = x^4 - 5x^3 + 10 x^2 - 9 x + 3 =0.$$

The corresponding recurrence equation is $$f_n= 5 f_{n−1} − 10 f_{n−2} + 9 f_{n-3} - 3 f_{n-4}.$$

Combining with the initial condition, we have $$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}.$$


Problem 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.$$

Solution: We need to find a characteristic equation that has two complex roots of multiplicity 2 $$z_{1}, \overline{z_1} = 3 (\cos{\frac{\pi}{3}} \pm i ~\sin{\frac{\pi}{3}}).$$

We have $$z_1 \overline{z_1} = 3^2 = 9,$$ $$z_1 + \overline{z_1} = 6~\cos{\frac{\pi}{3}} = 3,$$ therefore, by Vieta's formula, $z_1$ and $\overline{z_1}$ are two roots of the following quadratic equation $$x^2 - 3 x + 9 =0.$$

Thus, we obtain the characteristic equation $$(x^2 - 3x + 9)^2 = x^4 - 6 x^3 + 27 x^2 - 54 x + 81 =0.$$

The corresponding recurrence equation is $$f_n= 6 f_{n−1} − 27 f_{n−2} + 54 f_{n-3} - 81 f_{n-4}.$$

Combining with the initial condition, we have $$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}.$$




Let us stop here for now. The next post will be the last post of our series on sequence. Hope to see you again then.



Homework.

1. Prove that for any values of $f_0$ and $f_1$, the following sequence is periodic $$f_n = 2 \cos{\frac{\pi}{2013}} f_{n-1} - f_{n-2}.$$
(A sequence is called periodic if there is a period $K \neq 0$ such that $f_{n+K} = f_n$ for all $n$.)

2. Given the following sequence $$f_0 = 1, ~~f_1 = 2 \cos{\frac{\pi}{2013}}, ~~ f_n = 4 \cos{\frac{\pi}{2013}} f_{n-1} - 4 f_{n-2}$$
Prove that $f_{2013}$ is an integer.