Today we will go through some examples. The first type of examples involves solving a linear recurrence equation to derive a general formula for a sequence. The second type of examples does the reverse process, in which, we are given a formula of a sequence and asked to determine its recurrence equation.
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 conditions 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
$$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=a_k(x - x_1)^{j_1} (x - x_2)^{j_2} \dots (x - x_t)^{j_t}.$$
Suppose the characteristic equation has $t$ roots $x_1, \dots, x_t$, where $x_1$ is a root of multiplicity $j_1$, $x_2$ is a root of multiplicity $j_2$, etc... Then for any $\alpha_{ij}$, the sequence $$f_n = (\alpha_{11} +
\alpha_{12} n + \dots + \alpha_{1 j_1} n^{j_1 - 1}) ~ x_1^n + (\alpha_{21} +
\alpha_{22} n + \dots + \alpha_{2 j_2} n^{j_2 - 1}) ~ x_2^n$$ $$+ \dots + (\alpha_{t1} +
\alpha_{t2} n + \dots + \alpha_{t j_t} n^{j_t - 1}) ~ x_t^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 formula of $f_n$ to form a system of equations for the unknown $\alpha_{ij}$ and solve this system of equations.
Let us do some exercises.
Problem 1: Determine a general formula for the sequence $$f_0 = 5, ~f_1 = 9, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$
Solution: From the recurrence equation $f_n - 6 f_{n-1} + 9 f_{n-2}=0$ we have the following characteristic equation $$x^2 - 6 x + 9 = 0.$$ Solving this equation, we have $$x^2 - 6 x + 9 = (x-3)^2= 0,$$ thus, it has one root $x = 3$ of multiplicity 2. So we determine the sequence of the following form $$f_n = (\alpha_{11} + \alpha_{12} ~n )~ 3^n.$$ With $n=0,1$, we have $$f_0 = \alpha_{11} = 5,$$ $$f_1 = (\alpha_{11} + \alpha_{12}) ~3 = 9.$$ Solving these equations we obtain $\alpha_{11} = 5$ and $\alpha_{12} = -2$. Therefore, $$f_n = (5 - 2n) ~3^n.$$
Problem 2: Determine a general formula for the sequence $$f_0 = 1, ~f_1 = 5, ~f_2 = 22, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$
Solution: From the recurrence equation $f_n - 8 f_{n-1} + 21 f_{n-2}- 18 f_{n-3}=0$ we have the following characteristic equation $$x^3 - 8 x^2 + 21 x - 18 = 0.$$ Solving this equation, we have $$x^3 - 8 x^2 + 21 x - 18 = (x-2)(x-3)^2= 0.$$ So we determine the sequence of the following form $$f_n = \alpha_{11} ~ 2^n + (\alpha_{21} + \alpha_{22} ~n )~ 3^n.$$ With $n=0,1,2$, we have $$f_0 = \alpha_{11} + \alpha_{21} = 1,$$ $$f_1 = 2 \alpha_{11} + 3 \alpha_{21} + 3 \alpha_{22} = 5,$$ $$f_2 = 4 \alpha_{11} + 9 \alpha_{21} + 18 \alpha_{22} = 22.$$ Solving these equations we obtain $\alpha_{11} = 1$, $\alpha_{21}=0$ and $\alpha_{22} = 1$. Therefore, $$f_n = 2^n + n ~3^n.$$
Problem 3: Determine a general formula for the sequence $$f_0 = 5, ~f_1 = 1, ~f_2 = 11, ~f_3 = 11, ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$
Solution: From the recurrence equation $f_n - 2 f_{n-1} + 2 f_{n-3}- f_{n-4}=0$ we have the following characteristic equation $$x^4 - 2 x^3 + 2x - 1 = 0.$$ Solving this equation, we have $$x^4 - 2 x^3 + 2x - 1 = (x+1) (x-1)^3 = 0.$$ So we determine the sequence of the following form $$f_n = \alpha_{11} ~ (-1)^n + (\alpha_{21} + \alpha_{22} ~n + \alpha_{23} ~n^2) ~1^n.$$ With $n=0,1,2,3$, we have $$f_0 = \alpha_{11} + \alpha_{21} = 5,$$ $$f_1 = - \alpha_{11} + \alpha_{21} + \alpha_{22} + \alpha_{23} = 1,$$ $$f_2 = \alpha_{11} + \alpha_{21} + 2 \alpha_{22} + 4 \alpha_{23} = 11,$$ $$f_3 = - \alpha_{11} + \alpha_{21} + 3 \alpha_{22} + 9 \alpha_{23}= 11.$$ Solving these equations we obtain $\alpha_{11} = 3$, $\alpha_{21}=2$, $\alpha_{22} = 1$ and $\alpha_{23} = 1$. Therefore, $$f_n = 3 (-1)^{n} + 2 + n + n^2 .$$
Problem 4: Determine a recurrence condition for the sequence $f_n = n ~3^n$.
Solution: The characteristic equation must have the form $$(x-3)^2 = x^2 - 6 x + 9 = 0.$$ So the recurrence equation is $$f_n - 6 f_{n-1} + 9 f_{n-2} = 0.$$ Combining with the initial condition, we have $$f_0= 0, ~f_1 = 3, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$
Problem 5: Determine a recurrence condition for the sequence $f_n = (2n + 1) 3^n - 2^n$.
Solution: The characteristic equation must have the form $$(x-2)(x-3)^2 = x^3 - 8 x^2 + 21 x - 18 = 0.$$ So the recurrence equation is $$f_n - 8 f_{n-1} + 21 f_{n-2}- 18 f_{n-3}=0.$$ Combining with the initial condition, we have $$f_0= 0, ~f_1 = 7, ~f_2 = 41, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$
Problem 6: Determine a recurrence condition for the sequence $f_n = n^2 + n + (-1)^n$.
Solution: We have $$f_n = (n^2 + n) ~ 1^n + (-1)^n,$$ so the characteristic equation must have the form $$(x+1) (x-1)^3 = x^4 - 2 x^3 + 2x - 1 = 0.$$ So the recurrence equation is $$f_n - 2 f_{n-1} + 2 f_{n-3}- f_{n-4} = 0.$$ Combining with the initial condition, we have $$f_0= 1, ~f_1 = 1, ~f_2 = 7, ~f_3 =11 , ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$
Solution: We have $$f_n = (n^2 + n) ~ 1^n + (-1)^n,$$ so the characteristic equation must have the form $$(x+1) (x-1)^3 = x^4 - 2 x^3 + 2x - 1 = 0.$$ So the recurrence equation is $$f_n - 2 f_{n-1} + 2 f_{n-3}- f_{n-4} = 0.$$ Combining with the initial condition, we have $$f_0= 1, ~f_1 = 1, ~f_2 = 7, ~f_3 =11 , ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$
Problem 7: Determine a recurrence condition for the sequence $f_n = (2n + 1) (-1)^n + (n-1) ~2^n$.
Solution: The characteristic equation must have the form $$(x+1)^2 (x-2)^2 = x^4 - 2 x^3 - 3 x^2 + 4x + 4 = 0.$$ So the recurrence equation is $$f_n - 2 f_{n-1} - 3 f_{n-2} + 4 f_{n-3} + 4 f_{n-4} = 0.$$ Combining with the initial condition, we have $$f_0= 0, ~f_1 = -3, ~f_2 = 9, ~f_3 =9 , ~f_n = 2 f_{n-1} + 3 f_{n-2} - 4 f_{n-3} - 4 f_{n-4}.$$
Let us stop here for now, hope to see you again in our next post.
Homework.
1. Determine a general formula for the sequence $$f_0 = 3, ~f_1 = 6, ~f_n = 4 f_{n-1} - 4 f_{n-2}.$$
2. Determine a general formula for the sequence $$f_0 = 0, ~f_1 = 9, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$
3. Determine a general formula for the sequence $$f_0 = 0, ~f_1 = 1, ~f_2 = 5, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$
4. Determine a general formula for the sequence $$f_0 = 1, ~f_1 = 0, ~f_2 = 3, ~f_3 = 2, ~f_n = 2 f_{n-1} - 2 f_{n-3} + f_{n-4}.$$
5. Determine a recurrence condition for the sequence $f_n = n~ 2^n$.
6. Determine a recurrence condition for the sequence $f_n = 2n^3 - n^2 + 3n -1$.
Solution.
1. $f_n = 3 \times 2^n$
2. $f_n = n \times 3^{n+1}$
3. $f_n = 3^n - 2^n$
4. $f_n = (-1)^{n} + n$