Today we will learn how to solve a linear recurrence equation and derive a general formula for a sequence. This method will work for all cases, including the case when the characteristic equation has multiple roots.
General method to solve a linear 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 list here some examples.
- If the characteristic equation is $(x - x_1)^2=0$ then $$f_n = (\alpha_{11} + \alpha_{12} ~n) ~ x_1^n .$$
- If the characteristic equation is $(x - x_1)^2 (x-x_2)=0$ then $$f_n = (\alpha_{11} + \alpha_{12} ~n) ~ x_1^n + \alpha_{21} ~ x_2^n .$$
- If the characteristic equation is $(x - x_1)^3 (x-x_2) (x-x_3)^2=0$ then $$f_n = (\alpha_{11} + \alpha_{12} ~n + \alpha_{13} ~n^2) ~ x_1^n + \alpha_{21} ~ x_2^n + (\alpha_{31} + \alpha_{32} ~n) ~x_3^n .$$
- If the characteristic equation is $(x - x_1)^2 (x-x_2)^2 (x-x_3)^2=0$ then $$f_n = (\alpha_{11} + \alpha_{12} ~n ) ~ x_1^n + (\alpha_{21} + \alpha_{22} ~n) ~ x_2^n + (\alpha_{31} + \alpha_{32} ~n) ~x_3^n .$$
- If the characteristic equation is $(x - x_1) (x-x_2) (x-x_3)=0$ then $$f_n = \alpha_{11} ~ x_1^n + \alpha_{21} ~ x_2^n + \alpha_{31} ~x_3^n .$$
- If $j_1 = j_2 = \dots = j_t = 1$, i.e. the characteristic equation only has single roots $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=a_k(x - x_1) (x - x_2) \dots (x - x_t)=0$$ then $$f_n = \alpha_{11} ~ x_1^n + \alpha_{21} ~ x_2^n + \dots + \alpha_{t1} ~ x_t^n,$$ this is the familiar formula that we have learned in previous posts.
Let us do some exercises.
Problem 1: Determine a general 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-2} + 4 f_{n-3}=0$ we have the following characteristic equation $$x^2 - 4 x + 4 = 0.$$ Solving this equation, we have $$x^2 - 4 x + 4 = (x-2)^2= 0,$$ thus, it has one root $x = 2$ of multiplicity 2. So we determine the sequence of the following form $$f_n = (\alpha_{11} + \alpha_{12} ~n )~ 2^n.$$ With $n=0,1$, we have $$f_0 = \alpha_{11} = 3,$$ $$f_1 = (\alpha_{11} + \alpha_{12}) ~2 = 2.$$ Solving these equations we obtain $\alpha_{11} = 3$ and $\alpha_{12} = -2$. Therefore, $$f_n = (3 - 2n) ~2^n.$$
Problem 2: Determine a recurrence condition for the sequence $f_n = 5 \times 3^n + (n+2) \times 4^n$.
Solution: The characteristic equation must have the form $$(x-3)(x-4)^2 = x^3 -11 x^2 + 40 x - 48 = 0.$$ So the recurrence equation is $$f_n - 11 f_{n-1} + 40 f_{n-2} - 48 f_{n-3} = 0.$$ Combining with the initial condition, we have $$f_0= 7, ~f_1 = 27, ~f_2 = 109, ~f_n = 11 f_{n-1} - 40 f_{n-2} + 48 f_{n-3}.$$
Why does it work?
To explain the reason behind the above method of solving recurrence equation, we need to show that
- if the characteristic equation factored into $(x-x_i)$ then the sequence $$f_n = \alpha_{i1} ~x_i^n$$ must satisfy the recurrence equation;
- if the characteristic equation factored into $(x-x_i)^2$ then the sequence $$f_n = (\alpha_{i1} + \alpha_{i2}~n ) ~x_i^n$$ must satisfy the recurrence equation;
- if the characteristic equation factored into $(x-x_i)^3$ then the sequence $$f_n = (\alpha_{i1} + \alpha_{i2}~n + \alpha_{i3}~n^2) ~x_i^n$$ must satisfy the recurrence equation; etc...
- in general, if the characteristic equation is factored as $$f(x) = a_k x^k + a_{k-1} x^{k-1} + \dots + a_0 = (x - z)^j (b_s x^s + b_{s-1} x^{s-1} + \dots + b_0)$$ then the sequence $$f_n = p(n)~z^n,$$ where $p(n)$ is a polynomial of degree less than $j$, must satisfy the recurrence equation.
Let us record this fact as a theorem
A fundamental theorem for linear recurrence equation. Suppose that the characteristic equation can be factored as $$f(x) = a_k x^k + a_{k-1} x^{k-1} + \dots + a_0 = (x - z)^j (b_s x^s + b_{s-1} x^{s-1} + \dots + b_0)$$ and $$f_n = p(n)~z^n,$$ where $p(n)$ is a polynomial of degree less than $j$. Then the sequence $f_n$ satisfies the recurrence equation
$$a_k f_{n} + a_{k-1} f_{n-1} + \dots + a_1 f_{n-k+1} + a_0 f_{n-k} = 0.$$
In the next few posts, we will learn about finite difference method and use it to prove the above fundamental theorem. Stated briefly, a (forward) difference of $p(x)$ is defined as $$\Delta (p(x)) = p(x+1) - p(x).$$ This difference operator used in algebra is very similar to the differential operator used in calculus. Difference operator has many applications, for instance, previously on this blog, we have used it to prove Wilson's Theorem.
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 = 5, ~f_1 = 9, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$
2. Determine a general formula for the sequence $$f_0 = 2, ~f_1 = 6, ~f_n = 6 f_{n-1} - 9 f_{n-2}.$$
3. 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}.$$
4. 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}.$$
5. Determine a general formula for the sequence $$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}.$$
6. Determine a general formula for the sequence $$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}.$$
7. Determine a recurrence condition for the sequence $f_n = n ~3^n$.
8. Determine a recurrence condition for the sequence $f_n = n ~2^n + n^2 ~3^n$.
9. Determine a recurrence condition for the sequence $f_n = n ~(1 + 2^n + 3^n)$.
Solution.
1. $f_n = (5 - 2n) ~3^n$
2. $f_n = 2 \times 3^n$
3. $f_n = 2^n + n ~3^n$
4. $f_n = 3 (-1)^{n} + 2 + n + n^2$
5. $f_n = n^2 + n + (-1)^n$
6. $f_n = (2n + 1) (-1)^n + (n-1) 2^n$