This is the third part of our series on sequences. There will be no new material in this post. The main purpose of this post is to go through some examples so we can get used to the method of solving recurrence equations. If you have not read the previous parts of our series, please read them here: Part 1, Part 2.
Let us review the method to solve recurrence equations.
Suppose we have a sequence $\{f_n\}$ that satisfies the 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$$ with some initial condition on the values of $f_0, f_1, \dots, f_{k-1}$, we follow the following steps to determine a general formula for the sequence.
Step 1. Solve the recurrence equation.
Form the characteristic equation $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=0$$ and determine its roots.
Suppose that the characteristic equation has $k$ roots $x_1, \dots, x_k$. Then for any $\alpha_1, \dots, \alpha_k$, the sequence $$f_n = \alpha_1 ~ x_1^n + \dots + \alpha_k ~ x_k^n$$ satisfies the 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.$$
Step 2. Solve the initial condition.
Substituting the values of $f_0, f_1, \dots, f_{k-1}$ into the equation $$f_n = \alpha_1 ~ x_1^n + \dots + \alpha_k ~ x_k^n$$ and solve for $\alpha_1, \dots, \alpha_k$.
Let us go through some examples.
Problem 1: Determine the formula for the sequence $$f_0 = 8, ~f_1 =2, ~f_n = 2 f_{n-1} + 8 f_{n-2}.$$
Solution: From the recurrence equation $f_n - 2 f_{n-1} - 8 f_{n-2}=0$ we have the characteristic equation $$x^2 - 2 x - 8 = 0.$$ This equation has two roots $x_1 = -2$ and $x_2=4$. So we determine the sequence of the following form $$f_n = \alpha_1 ~ (-2)^n + \alpha_2 ~ 4^n.$$ With $n=0,1$, we have $$f_0 = \alpha_1 + \alpha_2 = 8,$$ $$f_1 = -2 \alpha_1 + 4 \alpha_2 = 2.$$ Solving these equations we obtain $\alpha_1 = 5$ and $\alpha_2 = 3$. Therefore, $$f_n = 5 \times (-2)^n + 3 \times 4^n.$$
Problem 2: Determine the formula for the sequence $$f_0 = 5, ~f_1 =20, ~f_n = 2 f_{n-1} + 8 f_{n-2}.$$
Solution: Problem 1 and Problem 2 have the same recurrence equation, only the initial conditions are different. As in Problem 1, we determine the sequence of the following form $$f_n = \alpha_1 ~ (-2)^n + \alpha_2 ~ 4^n.$$ With $n=0,1$, we have $$f_0 = \alpha_1 + \alpha_2 = 5,$$ $$f_1 = -2 \alpha_1 + 4 \alpha_2 = 20.$$ Solving these equations we obtain $\alpha_1 = 0$ and $\alpha_2 = 5$. Therefore, $$f_n = 5 \times 4^n.$$
Problem 3: Determine the formula for the Fibonacci sequence $$f_0 = 0, ~f_1 =1, ~f_n = f_{n-1} + f_{n-2}.$$
Solution: From the recurrence equation $f_n - f_{n-1} - f_{n-2}=0$ we have the characteristic equation $$x^2 - x - 1 = 0.$$ This equation has two roots $$x = \frac{1 \pm \sqrt{5}}{2}.$$ So we determine the sequence of the following form $$f_n = \alpha_1 \left( \frac{1 + \sqrt{5}}{2} \right)^n + \alpha_2 \left( \frac{1 - \sqrt{5}}{2} \right)^n.$$ With $n=0,1$, we have $$f_0 = \alpha_1 + \alpha_2 = 0,$$ $$f_1 = \alpha_1 \frac{1 + \sqrt{5}}{2} + \alpha_2 \frac{1 - \sqrt{5}}{2} = 1.$$ Solving these equations we obtain $$\alpha_1 = \frac{1}{\sqrt{5}}, ~~ \alpha_2 = - \frac{1}{\sqrt{5}}.$$ Therefore, $$f_n = \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n.$$
Problem 4: Determine the formula for the sequence $$f_0 = 1, ~f_1 =2, ~f_n = 2 f_{n-1} + 5 f_{n-2}.$$
Solution: From the recurrence equation $f_n - 2 f_{n-1} - 5 f_{n-2}=0$ we have the characteristic equation $$x^2 - 2 x - 5 = 0.$$ This equation has two roots $x = 1 \pm \sqrt{6}$. So we determine the sequence of the following form $$f_n = \alpha_1 ~ ( 1 + \sqrt{6} )^n + \alpha_2 ~ ( 1 - \sqrt{6} )^n.$$ With $n=0,1$, we have $$f_0 = \alpha_1 + \alpha_2 = 1,$$ $$f_1 = \alpha_1 ~ ( 1 + \sqrt{6} ) + \alpha_2 ~ ( 1 - \sqrt{6} ) = 2.$$ Solving these equations we obtain $$\alpha_1 = \frac{1+\sqrt{6}}{2 \sqrt{6}}, ~~ \alpha_2 = - \frac{1-\sqrt{6}}{2 \sqrt{6}}.$$ Therefore, $$f_n = \frac{1}{2 \sqrt{6}} [(1+\sqrt{6})^{n+1} - (1-\sqrt{6})^{n+1}].$$
Problem 5: Determine the formula for the sequence $$f_0 = 4, ~f_1 =4, ~f_2 = 38, ~f_n = f_{n-1} + 14 f_{n-2} - 24 f_{n-3}.$$
Solution: From the recurrence equation $f_n - f_{n-1} - 14 f_{n-2} + 24 f_{n-3}=0$ we have the characteristic equation $$x^3 - x^2 - 14 x + 24 = 0.$$ This equation has three roots $x = -4$, $x = 2$ and $x = 3$. So we determine the sequence of the following form $$f_n = \alpha_1 ~ ( -4 )^n + \alpha_2 ~ 2^n + \alpha_3 ~ 3^n.$$ With $n=0,1,2$, we have $$f_0 = \alpha_1 + \alpha_2 + \alpha_3= 4,$$ $$f_1 = -4 \alpha_1 + 2 \alpha_2 + 3 \alpha_3 = 4,$$ $$f_2 = 16 \alpha_1 + 4 \alpha_2 + 9 \alpha_3 = 38.$$ Solving these equations we obtain $\alpha_1 = 1$, $\alpha_2 = 1$ and $\alpha_3 = 2$. Therefore, $$f_n = (-4)^n + 2^n + 2 \times 3^n.$$
Problem 6: Determine the formula for the sequence $$f_0 = 8, ~f_1 =13, ~f_2 = 99, ~f_n = 13 f_{n-2} + 12 f_{n-3}.$$
Solution: From the recurrence equation $f_n - 13 f_{n-2} - 12 f_{n-3}=0$ we have the characteristic equation $$x^3 - 13 x - 12 = 0.$$ This equation has three roots $x = -3$, $x = -1$ and $x = 4$. So we determine the sequence of the following form $$f_n = \alpha_1 ~ ( -3 )^n + \alpha_2 ~ (-1)^n + \alpha_3 ~ 4^n.$$ With $n=0,1,2$, we have $$f_0 = \alpha_1 + \alpha_2 + \alpha_3= 8,$$ $$f_1 = -3 \alpha_1 - \alpha_2 + 4 \alpha_3 = 13,$$ $$f_2 = 9 \alpha_1 + \alpha_2 + 16 \alpha_3 = 99$$ Solving these equations we obtain $\alpha_1 = 2$, $\alpha_2 = 1$ and $\alpha_3 = 5$. Therefore, $$f_n = 2 \times (-3)^n + (-1)^n + 5 \times 4^n.$$
Problem 7: Determine the recurrence conditions for the sequence $f_n = 5 \times 3^n - 4^n$.
Solution: The characteristic equation has two roots $x = 3$ and $x = 4$, so it must be $$(x-3)(x-4) = x^2 - 7 x + 12 = 0.$$ The corresponding recurrence equation is $$f_n - 7 f_{n-1} + 12 f_{n-2} = 0.$$ With the initial condition, we have $$f_0= 4, ~f_1 = 11, ~f_n = 7 f_{n-1} - 12 f_{n-2}.$$
Problem 8: Determine the formula for the sequence $$f_0 = 3, ~f_1 = 2, ~f_n = 4 f_{n-1} - 4 f_{n-2}.$$
Solution: From the recurrence equation $f_n - 4 f_{n-1} + 4 f_{n-2}=0$ we have the characteristic equation $$x^2 - 4 x + 4 = 0.$$ This equation has a double root $x = 2$. So we determine the sequence of the following form $$f_n = \alpha ~ 2^n.$$ With $n=0,1$, we have $$f_0 = \alpha = 3,$$ $$f_1 = 2 \alpha = 2.$$ The first equation gives $ \alpha = 3$ but the second equation gives $\alpha = 1$. Therefore, the sequence is not of the form $f_n = \alpha ~ 2^n$.
In Problem 8, since the characteristic equation has a double root, our second step fails. In this scenario, we will need a new method to solve the recurrence equation. We will learn this new method in our future posts.
All of the above exercises are very basic and designed to help us get used to the method of solving recurrence equations. If you find these problems a bit boring then we have some more interesting problems for you in the homework section.
Let us stop here for now, hope to see you next time.
Let us stop here for now, hope to see you next time.
Homework.
1. Given the following sequence $$f_0=2, ~f_1 = 2013, ~f_n = 2013 f_{n-1} - f_{n-2}.$$ Prove that for any $n$, there always exists an integer $m$ such that $$f_n f_{n+2} + 4 = 2013^2 + m^2.$$
2. Given the following sequence $$f_0=2, ~f_1 = 2013, ~f_n = 2013 f_{n-1} + f_{n-2}.$$ Determine all values of $n$ such that $f_n f_{n+2} + 2013^2 +4$ is a perfect square number.
3. The Pell sequence is defined as follows $$P_0=0, ~P_1 = 1, ~P_n = 2 P_{n-1} + P_{n-2}.$$
The following sequence is called 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$.
4. Generalize the results of the above exercises.