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,$ ...
Problem 2: 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.
Solution: 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.$$
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.$$
Problem 3: 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}.$$
(A sequence is called periodic if there exists a period $K \neq 0$ such that for any $n$, $f_{n+K} = f_n$.)
Solution: 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.$$
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.
Problem 4: 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.
Solution: 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.$$
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.
Problem 5: Determine a recurrence condition for the sequence $f_n=n 2^n$.
Solution: 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.$$
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}.$$
Problem 6: Determine a recurrence condition for the sequence $f_n=2n^3−n^2+3n−1$.
Solution: 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.$$
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}.$$
Problem 7: 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.$$
Solution: Form the sequence $$f_n = P(n).$$
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.$$
Problem 8: 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}}}.$$
Solution: From the recurrence equation $$F_n - F_{n-1} - F_{n-2} = 0$$ we have the characteristics equation $$x^2 - x - 1 = 0.$$
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 non-homogeneous linear recurrence equation. This is an 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}=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.