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

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

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

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

**Problem**1:**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.$$**

**Solution**: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.$$

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

**Problem**2:**From the recurrence equation $f_n= f_{n−1} − f_{n−2}$ we have the following characteristic equation $$x^2 − x + 1 =0.$$**

**Solution**: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}} .$$

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

**Problem**3:**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.$$**

**Solution**: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 .$$

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

**Problem**4:**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.$$**

**Solution**: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}} .$$

**Determine a recurrence condition for the sequence $$f_n = (5 ~\cos{\frac{n \pi}{4}} + 3 ~\sin{\frac{n \pi}{4}}) (\sqrt{2})^n.$$**

**Problem**5:**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}}).$$**

**Solution**: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}.$$

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

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

**Solution**: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}.$$

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

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

**Solution**: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}.$$

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

**Problem**8:**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}}).$$**

**Solution**: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

**if there is a period $K \neq 0$ such that $f_{n+K} = f_n$ for all $n$.)**

*periodic*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.

## No comments:

## Post a Comment