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.