*Pell sequence*$$P_0=0, ~~P_1 = 1, ~~P_n = 2 P_{n-1} + P_{n-2},$$ and the

*companion Pell sequence*$$H_0=1, ~~H_1 = 1, ~~H_n = 2 H_{n-1} + H_{n-2},$$ we will show that $$H_n^2 - 2 P_n^2 = (-1)^n.$$

For the Fibonacci sequence $$F_0 = 0, ~~F_1 = 1, ~~F_n = F_{n-1} + F_{n-2},$$ we will prove the following identity $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$

Throughout our series on sequence, we have learned how to derive general formula for a sequence $\{ f_n \}$ that satisfies a

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

As we have seen, when solving a linear recurrence equation,

*the characteristic equation*plays a very important role. The characteristic equation is the following equation $$a_k ~x^k + a_{k−1} ~x^{k−1} + \dots + a_1 ~x + a_0=0.$$ The formula for the sequence will ultimately depend on how many roots the characteristics equation has, and on the nature of these roots: whether they are

*simple roots*or

*roots of multiplicities*, and whether they are

*real roots*or

*complex roots*.

Suppose we classify the roots of the characteristics equation into two groups:

**Real roots:**suppose that the characteristics 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 characteristics 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$;

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

Scenario 1:the characteristics equation only has simple roots $x_1$, $x_2$, ..., $x_k$.

In this case, we have the following formula $$f_n = \alpha_1 ~x_1^{n} + \alpha_2 ~x_2^{n} + \dots + \alpha_k ~x_k^{n},$$ where $\alpha_1$, $\alpha_2$, ..., $\alpha_k$ are real constants.

Scenario 2:the characteristics equation has exactly one pair of complex roots $z_1$, $\overline{z_1}$, $$z_1, \overline{z_1} = r (\cos{\phi} \pm i ~ \sin{\phi}).$$

In this case, we have $$f_n = (\alpha ~\cos{n \phi} + \beta ~ \sin{n \phi}) ~r^n,$$ where $\alpha$, $\beta$ are real constants.

Generally, there are two types of problems on sequence. In the first type, we are given a recurrence relation and asked to determine a general formula for the sequence. In the second type, we do the reverse, from a general formula we need to find out a recurrence relation for the sequence.

Let us do some exercises.

**Problem 1:**Consider the

*Pell sequence*defined as follows $$P_0=0, ~~P_1 = 1, ~~P_n = 2 P_{n-1} + P_{n-2},$$

and the

*companion Pell sequence*$$H_0=1, ~~H_1 = 1, ~~H_n = 2 H_{n-1} + H_{n-2}.$$

Prove that $$H_n^2 - 2 P_n^2 = (-1)^n.$$

**Solution:**The characteristics equation for both sequences $P_n$ and $H_n$ is $$x^2 - 2 x - 1 = 0.$$

This equation has two roots $$1 \pm \sqrt{2}.$$

Thus, $$P_n = \alpha ~ (1 + \sqrt{2})^n + \beta ~ (1 - \sqrt{2})^n$$

and $$H_n = \gamma ~ (1 + \sqrt{2})^n + \delta ~ (1 - \sqrt{2})^n.$$

With $n=0,1$, we have $$P_0 = \alpha + \beta = 0, ~~P_1 = \alpha ~(1 + \sqrt{2}) + \beta ~(1 - \sqrt{2}) = 1,$$ $$H_0 = \gamma + \delta = 1, ~~H_1 = \gamma ~(1 + \sqrt{2}) + \delta ~(1 - \sqrt{2}) = 1.$$

Solving these equations we obtain $\alpha = \frac{1}{2 \sqrt{2}}$, $\beta = -\frac{1}{2 \sqrt{2}}$, $\gamma = \frac{1}{2}$, $\delta = \frac{1}{2}$. Therefore, $$P_n = \frac{1}{2 \sqrt{2}} [(1 + \sqrt{2})^n - (1 - \sqrt{2})^n],$$ $$H_n = \frac{1}{2} [(1+\sqrt{2})^n + (1 - \sqrt{2})^n].$$

We have $$P_n^2 = \frac{1}{8} [(1 + \sqrt{2})^n - (1 - \sqrt{2})^n]^2 = \frac{1}{8} [(1+\sqrt{2})^{2n} + (1 - \sqrt{2})^{2n} - 2 (-1)^n],$$ $$H_n^2 = \frac{1}{4} [(1+\sqrt{2})^n + (1-\sqrt{2})^n]^2 = \frac{1}{4} [(1 + \sqrt{2})^{2n} + (1 - \sqrt{2})^{2n} + 2 (-1)^n].$$

Thus, we obtain the identity $$H_n^2 - 2 P_n^2 = (-1)^n.$$

Here is a few initial values of the

*Pell sequence*and the

*companion Pell sequence*$$P_0=0, ~~P_1 = 1, ~~P_2 = 2, ~~P_3 = 5, ~~P_4 = 12, ~~P_5 = 29, \dots $$ $$H_0=1, ~~H_1 = 1, ~~H_2 = 3, ~~H_3 = 7, ~~H_4 = 17, ~~H_5 = 41, \dots$$

We have the following identities

- $H_2^2 - 2 P_2^2 = 3^2 - 2 \times 2^2 = 9 - 8 = 1,$
- $H_3^2 - 2 P_3^2 = 7^2 - 2 \times 5^2 = 49 - 50 = -1,$
- $H_4^2 - 2 P_4^2 = 17^2 - 2 \times 12^2 = 289 - 288 = 1,$
- $H_5^2 - 2 P_5^2 = 41^2 - 2 \times 29^2 = 1681 - 1682 = -1,$ ...

**Given the following sequence $$f_0=2, ~f_1 = 2013, ~f_n = 2013 f_{n-1} + f_{n-2}.$$ Determine all the values of $n$ such that $$f_n f_{n+2} + 2013^2 + 4$$ is a perfect square.**

**Problem**2:**From the recurrence equation $$f_n - 2013 f_{n-1} - f_{n-2} = 0$$ we have the characteristics equation $$x^2 - 2013 x - 1 = 0.$$**

**Solution**:This equation has two roots $x_1, x_2$ that satisfy the following Vieta's formula $$x_1 + x_2 = 2013,$$ $$x_1 x_2 = -1.$$

We have $$f_n = \alpha ~ x_1^n + \beta ~ x_2^n.$$

With $n=0,1$, $$f_0 = \alpha + \beta = 2,$$ $$f_1 = \alpha ~x_1 + \beta ~x_2 = 2013.$$

Solving these equations we obtain $\alpha = \beta = 1$, thus, $$f_n = x_1^n + x_2^n.$$

It follows that $$f_n f_{n+2} = (x_1^n + x_2^n)(x_1^{n+2} + x_2^{n+2}) = x_1^{2n+2} + x_2^{2n+2} + x_1^n x_2^n (x_1^2 + x_2^2)$$ $$= (x_1^{n+1} + x_2^{n+1})^2 - 2 x_1^{n+1} x_2^{n+1} + x_1^n x_2^n [(x_1 + x_2)^2 - 2 x_1 x_2]$$ $$= f_{n+1}^2 - 2 (-1)^{n+1} + (-1)^n (2013^2 + 2) = f_{n+1}^2 + (-1)^n (2013^2 + 4).$$

So we obtain the following identity $$f_n f_{n+2} = f_{n+1}^2 + (-1)^n (2013^2 + 4).$$

We consider two cases.

Case 1: If $n$ is an even number then $$f_n f_{n+2} = f_{n+1}^2 + (2013^2 + 4).$$

So $$f_n f_{n+2} + 2013^2 + 4 = f_{n+1}^2 + 2(2013^2 + 4).$$

We will show that in this case $f_n f_{n+2} + 2013^2 + 4$ cannot be a perfect square number.

Indeed, suppose that $$f_n f_{n+2} + 2013^2 + 4 = f_{n+1}^2 + 2(2013^2 + 4) = N^2,$$ then $$N^2 - f_{n+1}^2 = 2(2013^2 + 4).$$

It follows that $N^2 - f_{n+1}^2$ is an even number but not divisible by 4. This is impossible because we can easily show that for a number of the form $a^2 - b^2$ if it is an even number then it must be divisible by 4.

Case 2: If $n$ is an odd number then $$f_n f_{n+2} = f_{n+1}^2 - (2013^2 + 4).$$

So in this case $f_n f_{n+2} + 2013^2 + 4 = f_{n+1}^2$ is a perfect square.

In summary, $f_n f_{n+2} + 2013^2 + 4$ is a perfect square if and only if $n$ is an odd number.

Please note that in Problem 2, $$x_1, x_2 = \frac{1}{2}(2013 \pm \sqrt{2013^2 + 4}),$$ but we didn't write them explicitly because doing so would be a bit messy, so instead, we use Vieta's formula $$x_1 + x_2 = 2013,$$ $$x_1 x_2 = -1.$$

**Prove that regardless of the 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}.$$**

**Problem**3:(A sequence is called

**if there exists a**

*periodic**period*$K \neq 0$ such that for any $n$, $f_{n+K} = f_n$.)

**From the recurrence equation $$f_n - 2 \cos{\frac{\pi}{2013}} f_{n-1} + f_{n-2} = 0$$ we have the characteristics equation $$x^2 - 2 \cos{\frac{\pi}{2013}} x + 1 = 0.$$ $$\Delta' = (\cos{\frac{\pi}{2013}})^2 - 1 = - (\sin{\frac{\pi}{2013}})^2.$$**

**Solution**:This quadratic equation has two complex roots $$x_1, x_2 = \cos{\frac{\pi}{2013}} \pm i~ \sin{\frac{\pi}{2013}}.$$

So $$f_n = \alpha ~\cos{\frac{n \pi}{2013}} + \beta ~ \sin{\frac{n \pi}{2013}}.$$

It follows that $$f_{n + 4026} = \alpha ~\cos{\frac{(n+4026) \pi}{2013}} + \beta ~ \sin{\frac{(n+4026) \pi}{2013}}$$ $$= \alpha ~\cos{(\frac{n \pi}{2013} + 2 \pi)} + \beta ~ \sin{(\frac{n \pi}{2013} + 2 \pi)}$$ $$= \alpha ~\cos{\frac{n \pi}{2013}} + \beta ~ \sin{\frac{n \pi}{2013}}= f_n,$$ thus, $\{f_n\}$ is a periodic sequence.

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

**Problem**4:Prove that $f_{2013}$ is an integer.

**From the recurrence equation $$f_n - 4 \cos{\frac{\pi}{2013}} f_{n-1} + 4 f_{n-2} = 0$$ we have the characteristics equation $$x^2 - 4 \cos{\frac{\pi}{2013}} x + 4 = 0.$$ $$\Delta' = (2 \cos{\frac{\pi}{2013}})^2 - 4 = - 4 (\sin{\frac{\pi}{2013}})^2.$$**

**Solution**:This quadratic equation has two complex roots $$x_1, x_2 = 2 (\cos{\frac{\pi}{2013}} \pm i~ \sin{\frac{\pi}{2013}}).$$

So $$f_n = 2^n ~( \alpha ~\cos{\frac{n \pi}{2013}} + \beta ~ \sin{\frac{n \pi}{2013}} ).$$

With $n=0,1$, we have $$f_0 = \alpha = 1,$$ $$f_1 = 2 ( \alpha~\cos{\frac{\pi}{2013}} + \beta ~ \sin{\frac{\pi}{2013}} ) = 2 \cos{\frac{\pi}{2013}}.$$

Solving these equations we obtain $\alpha = 1$ and $\beta = 0$. Thus, $$f_n = 2^n ~\cos{\frac{n \pi}{2013}}.$$

It follows that $f_{2013} = -2^{2013}$ is an integer.

**Determine a recurrence condition for the sequence $f_n=n 2^n$.**

**Problem**5:**We will find a characteristics equation that has one root $x=2$ of multiplicity 2. The characteristics equation is $$(x−2)^2=x^2− 4 x+ 4=0.$$**

**Solution**:The corresponding recurrence equation is $$f_n− 4f_{n−1} + 4f_{n−2}=0.$$

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

**Determine a recurrence condition for the sequence $f_n=2n^3−n^2+3n−1$.**

**Problem**6:**Since $$f_n = (2n^3 - n^2 + 3n-1) 1^n$$ we need to find a characteristics equation that has one root $x=1$ of multiplicity 4. The characteristics equation is $$(x−1)^4=x^4 - 4 x^3 + 6 x^2 - 4 x + 1=0.$$**

**Solution**:The corresponding recurrence equation is $$f_n− 4f_{n−1} + 6f_{n−2} - 4 f_{n-3} + f_{n-4}=0.$$

Combining with the initial condition we have $$f_0=-1, ~~f_1=3, ~~f_2 = 17, ~~f_3 = 53, ~~f_n = 4f_{n−1} - 6f_{n−2} + 4f_{n-3} - f_{n-4}.$$

**For any polynomial $P(x)$ of degree $k$, prove that $$P(n) - {{k+1} \choose 1} P(n-1) + {{k+1} \choose 2} P(n-2) - {{k+1} \choose 3} P(n-3)$$ $$ + \dots + (-1)^k {{k+1} \choose k} P(n-k) + (-1)^{k+1} P(n-k-1) = 0.$$**

**Problem**7:**Form the sequence $$f_n = P(n).$$**

**Solution**:Since $$f_n = P(n) ~ 1^n$$ and the polynomial $P(x)$ has degree $k$, we find a characteristics equation that has one root $x=1$ of multiplicity $k+1$.

The characteristics equation is $$(x-1)^{k+1} = x^{k+1} - {{k+1} \choose 1} x^k + {{k+1} \choose 2} x^{k-1} - \dots + (-1)^k {{k+1} \choose k} x + (-1)^{k+1} = 0.$$

The corresponding recurrence equation is $$f_n - {{k+1} \choose 1} f_{n-1} + {{k+1} \choose 2} f_{n-2} - \dots + (-1)^k {{k+1} \choose k} f_{n-k} + (-1)^{k+1} f_{n-k-1} = 0.$$

Therefore, $$P(n) - {{k+1} \choose 1} P(n-1) + {{k+1} \choose 2} P(n-2) - \dots + (-1)^k {{k+1} \choose k} P(n-k) + (-1)^{k+1} P(n-k-1) = 0.$$

**For the Fibonacci sequence $$F_0 = 0, ~~F_1 = 1, ~~F_n = F_{n-1} + F_{n-2},$$ prove that $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$**

**Problem**8:**From the recurrence equation $$F_n - F_{n-1} - F_{n-2} = 0$$ we have the characteristics equation $$x^2 - x - 1 = 0.$$**

**Solution**:This equation has two roots $x_1, x_2$ that satisfy the Vieta's formula $$x_1 + x_2 = 1,$$ $$x_1 x_2 = -1.$$

We have $$F_n = \alpha ~ x_1^n + \beta ~ x_2^n.$$

Construct a new sequence $$f_n = F_{2013 n}.$$

We have $$f_n = \alpha ~ x_1^{2013 n} + \beta ~ x_2^{2013 n} = \alpha ~ (x_1^{2013})^n + \beta ~ (x_2^{2013})^n.$$

So the characteristics equation of the new sequence $f_n$ has two roots $x_1^{2013}$ and $x_2^{2013}$.

We have $$x_1^{2013} x_2^{2013} = -1.$$

Let $$T = x_1^{2013} + x_2^{2013}.$$

By Vieta's formula, $x_1^{2013}$ and $x_2^{2013}$ are the two roots of the following quadratic equation $$x^2 - T ~x - 1=0.$$

Thus, the recurrence equation for the new sequence $f_n$ is $$f_n− T ~f_{n−1} - f_{n−2}=0.$$

We have $$f_{n+1}− T~ f_{n} - f_{n−1}=0.$$

Thus, $$F_{2013(n+1)}− T ~F_{2013 n} - F_{2013 (n−1)}=0.$$

It implies that $$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = T$$

is a constant. Therefore,

$$\frac{F_{2013(n+1)} - F_{2013 (n−1)}}{F_{2013 n}} = \frac{F_{2013(n^{2013}+1)} - F_{2013 (n^{2013}−1)}}{F_{2013 n^{2013}}}.$$

Let us stop our series on sequence here. On this series we have learned how to solve the recurrence equation of the form

$$a_k f_n + a_{k−1} f_{n−1} + a_{k−2} f_{n−2}+ \dots + a_0 f_{n−k}=0,$$ this equation is technically called the

*homogeneous linear recurrence equation*.

In the future, we will learn about the

*. This is an equation of the form*

**non-homogeneous**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}=g_n,$$ where $g_n \neq 0$. Here is one example of it, $$f_n = 5 f_{n-1} - 6 f_{n-2} + 5^n.$$

Sequences have many interesting applications and we will learn about them in the future. For instance, we will show how to use sequence to calculate summations of the following forms

$$\sum_{n=1}^{N}{2013^n ~n^2}, ~~~~\sum_{n=1}^{N}{2013^n ~n^2 ~\cos{\frac{n \pi}{2013}}}, ~~~~\sum_{n=1}^{N}{2013^n ~\sin{\frac{n \pi}{2013}}}.$$

Hope to see you again in the next post.

## No comments:

## Post a Comment