Today we will learn about difference operator and use it to prove a fundamental theorem for linear recurrence equations.
A fundamental theorem for linear recurrence equations. 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.$$
Difference operator
First, let us learn about difference operator. The (forward) difference operator $\Delta$ is defined simply as $$\Delta (P(x)) = P(x+1) - P(x).$$ Here are some examples
- If $P(x) = 5$ then $$\Delta(P(x))=5-5=0;$$
- If $P(x) = x$ then $$\Delta(P(x))= (x+1)-x = 1;$$
- If $P(x) = x^2$ then $$\Delta(P(x))= (x+1)^2 - x^2 = 2x + 1;$$
- If $P(x) = 3 x^2 + 2x + 1$ then $$\Delta(P(x))= [3 (x+1)^2 + 2(x+1) + 1] - [3 x^2 + 2x + 1] = 6x + 5;$$
- If $P(x) = \frac{1}{x}$ then $$\Delta(P(x))= \frac{1}{x+1} - \frac{1}{x} = - \frac{1}{x(x+1)}.$$
- If $P(x) = 2^{x}$ then $$\Delta(P(x))= 2^{x+1} - 2^{x} = 2^x.$$
- If $P(x) = 3^{x}$ then $$\Delta(P(x))= 3^{x+1} - 3^{x} = 2 \times 3^x.$$
Clearly, the difference operator has the following properties
- Additivity: $$\Delta(u(x) + v(x)) = \Delta(u(x)) + \Delta(v(x));$$
- Homogeneity: for any constant $a$, $$\Delta(a ~P(x)) = a ~\Delta(P(x)).$$
Higher-order difference
We can repeat the application of difference operator to create differences of higher orders as follows.
- Let us start with the usual difference operator (it is called the difference of order 1) $$\Delta(P(x)) = P(x+1) - P(x).$$
- Next, we apply the difference operator to $\Delta(P(x))$, the result is the difference of order 2, we will use the following notation $$\Delta^2(P(x)) = \Delta(\Delta(P(x))) = \Delta(P(x+1) - P(x)).$$ Thus, $$\Delta^2(P(x)) = [P(x+2) - P(x+1)] - [P(x+1) - P(x)]$$ $$ = P(x+2) - 2 P(x+1) + P(x).$$
- Again, the difference of order 3 is $$\Delta^3(P(x)) = P(x+3) - 3 P(x+2) + 3 P(x+1) - P(x).$$
Have you noticed any pattern yet? If you haven't, then keep calculating the differences of order 4, order 5 -- $\Delta^4(P(x))$, $\Delta^5(P(x))$ -- you will surely recognize the pattern.
The pattern is that the coefficients in the formula are the numbers in the Pascal triangle!
This is a very important formula that we will use in our later proof of the fundamental theorem for linear recurrence equations, so we will restate it
Formula for higher-order differences. The difference of order $j$ of $P(x)$ is $$\Delta^j(P(x)) = \sum_{v=0}^{j} (-1)^{j-v} {j \choose v} P(x + v).$$
Difference of polynomials
Let us now consider the application of difference operator to polynomials. A very important fact is that:
- For any $n > 0$, if we apply the difference operator to a polynomial of degree $n$ then we will obtain a polynomial of degree $n-1$.
Thus,
- Difference of order $n$ of a polynomial of degree $n$ is a constant.
- Difference of order $n+1$ of a polynomial of degree $n$ is equal to $0$.
On this blog, we have used these facts to prove Wilson's Theorem.
Let us pick an example, a polynomial of degree 3, $P(x) = 2 x^3 + x^2 + 3 x + 5$, and calculate its differences
- We start with the difference of order 1 $$\Delta(P(x)) = [2(x+1)^3 + (x+1)^2 + 3(x+1) + 5] - [2 x^3 + x^2 + 3 x + 5]$$ $$=2[(x+1)^3 - x^3] + [(x+1)^2 - x^2] + 3[(x+1)-x]$$ $$=2[3 x^2 + 3x + 1] + [2x+1] + 3 =6 x^2 + 8x + 6,$$ So the difference of order $1$ of $2 x^3 + x^2 + 3 x + 5$ is a polynomial of degree $2$.
- Next, the difference of order 2 $$\Delta^2(P(x)) = [6 (x+1)^2 + 8 (x+1) + 6] - [6 x^2 + 8x + 6]$$ $$= 6 [(x+1)^2 - x^2] + 8 [(x+1) -x]$$ $$= 6 [2x+1] + 8 = 12 x + 14$$ So the difference of order $2$ of $2 x^3 + x^2 + 3 x + 5$ is a polynomial of degree $1$.
- The difference of order 3 $$\Delta^3(P(x)) = [12 (x+1) + 14] - [12x + 14] = 12$$ The difference of order $3$ of $2 x^3 + x^2 + 3 x + 5$ is a constant.
- Finally, the difference of order 4 of $2 x^3 + x^2 + 3 x + 5$ is zero $$\Delta^4(P(x)) = 12 - 12 = 0.$$
- Clearly, each time we apply the difference operation, the degree of the polynomial decreases and finally, it becomes 0.
A fundamental theorem for linear recurrence equations. 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.$$
First, we will express each $a_i$ in terms of the $b_i$. We have $$f(x) = \sum_{v=0}^{j}{(-1)^{j-v} {j \choose v} z^{j-v} x^v} \sum_{u=0}^{s}{b_u x^u} = \sum_{u=0}^{s} \sum_{v=0}^{j} (-1)^{j-v} {j \choose v} b_u z^{j-v} x^{u+v}$$
Therefore, we obtain $$a_w = \sum_{0 \leq u \leq s, ~0 \leq v \leq j, ~u+v=w} (-1)^{j-v} {j \choose v} b_u z^{j-v}$$
Now, let us substitute the above formula of $a_i$ and $f_i = p(i)~z^i$ into the recurrence equation. We have $$\sum_{w=0}^{k} a_w f_{n-k+w} = \sum_{w=0}^{k} a_w p(n-k+w) z^{n-k+w}= z^{n-k} \sum_{w=0}^{k} a_w z^w p(n-k+w) $$ $$=z^{n-k} \sum_{w=0}^{k} \sum_{0 \leq u \leq s, ~0 \leq v \leq j, ~u+v=w} (-1)^{j-v} {j \choose v} b_u z^{j-v} z^w p(n-k+w) $$ $$=z^{n-k} \sum_{w=0}^{k} \sum_{0 \leq u \leq s, ~0 \leq v \leq j, ~u+v=w} (-1)^{j-v} {j \choose v} b_u z^{j+u} p(n-k+w)$$ $$=z^{n-k} \sum_{u=0}^{s} b_u z^{j+u} \sum_{v=0}^{j} (-1)^{j-v} {j \choose v} p(n-k+u+v).$$
By the formula of higher-order difference that we have learned above, we have $$\sum_{w=0}^{k} a_w f_{n-k+w} = z^{n-k} \sum_{u=0}^{s} b_u z^{j+u} \Delta^{j}(p(n-k+u)).$$
Since $p(n)$ is a polynomial of degree less than $j$, for any value of $u$, $p(n-k+u)$ is also a polynomial of variable $n$ of degree less than $j$. Therefore, the difference of order $j$ of $p(n-k+u)$ must be terminated, i.e. $$\Delta^{j}(p(n-k+u)) = 0.$$
It follows that $$\sum_{w=0}^{k} a_w f_{n-k+w} = 0,$$ this is the required recurrence equation and the proof is completed.
The above theorem is a fundamental theorem for solving linear recurrence equations. Indeed,
- if the characteristic equation has a root $x=z_1$ of multiplicity $j_1$, then by the theorem, for any polynomial $p_1(n)$ of degree less than $j_1$, the sequence $\{p_1(n) z_1^n\}$ satisfies the recurrence equation;
- if the characteristic equation has a root $x=z_2$ of multiplicity $j_2$, then by the theorem, for any polynomial $p_2(n)$ of degree less than $j_2$, the sequence $\{p_2(n) z_2^n\}$ satisfies the recurrence equation;...
- if the characteristic equation has a root $x=z_t$ of multiplicity $j_t$, then by the theorem, for any polynomial $p_t(n)$ of degree less than $j_t$, the sequence $\{p_t(n) z_t^n\}$ satisfies the recurrence equation;
- thus, if we add all these sequences, we will have a sequence of the form $$f_n = p_1(n) z_1^n + p_2(n) z_2^n + \dots + p_t(n) z_t^n,$$ this sequence also satisfies the recurrence equation. This is exactly the formula that we used in previous posts to solve recurrence equations.
Example: suppose we want to find a general formula for the sequence $$f_0=1, ~f_1 = 7, ~f_2= 32, ~f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}.$$ From the recurrence equation $$f_n = 8 f_{n-1} - 21 f_{n-2} + 18 f_{n-3}$$ we solve the characteristic equation $$x^3 - 8 x^2 + 21 x - 18 = (x-2)(x-3)^2= 0.$$ The fundamental theorem asserts that sequence of the form $$f_n = p_1(n) ~2^n + p_2(n) ~3^n,$$ where $p_1(n)$ is a polynomial of degree less than $1$ and $p_2(n)$ is a polynomial of degree less than $2$, will satisfy the recurrence equation. We let $$p_1(n) = a, ~~~ p_2(n) = b + c ~n.$$ Then $$f_n = a ~ 2^n + (b + c~n)~ 3^n.$$ From the initial condition: $f_0=1$, $f_1=7$, $f_2=32$, we establish a system of equations $$f_0 = a + b = 1,$$ $$f_1 = 2 a + 3 b + 3 c = 7,$$ $$f_2 = 4 a + 9 b + 18 c = 32.$$ Solving this system of equations we obtain $a = -1$, $b=2$ and $c = 1$. Therefore, $$f_n = (2 + n) ~3^n - 2^n.$$
Let us end this post here with a review of the method of solving linear 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 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 - z_1)^{j_1} (x - z_2)^{j_2} \dots (x - z_t)^{j_t}.$$
Suppose the characteristic equation has $t$ roots $z_1, \dots, z_t$, where $z_1$ is a root of multiplicity $j_1$, $z_2$ is a root of multiplicity $j_2$, etc... Then for any polynomial $p_1(n)$, ..., $p_t(n)$ of degree less than $j_1$, ..., $j_t$, respectively, the sequence $$f_n = p_1(n)~ z_1^n + p_2(n) ~ z_2^n + \dots + p_t(n) ~z_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 and solve this system of equations to derive a general formula for $f_n$.
Hope to see you again in the next post.
Homework.
1. Use mathematical induction to prove the formula for higher-order difference $$\Delta^j(P(x)) = \sum_{v=0}^{j} (-1)^{j-v} {j \choose v} P(x + v).$$
2. Prove the following important facts about difference of polynomials:
- For any $n > 0$, if we apply the difference operator to a polynomial of degree $n$ then we will obtain a polynomial of degree $n-1$.
- Difference of order $n$ of a polynomial of degree $n$ is a constant.
- Difference of order $n+1$ of a polynomial of degree $n$ is equal to $0$.
3. Calculate $\Delta(P(x))$ for the following cases:
- $P(x) = a^x$
- $P(x) = x^n$
- $P(x) = x(x+1)$
- $P(x) = x(x+1)(x+2)$
- $P(x) = 1/[x(x+1)]$
- $P(x) = 1/[x(x+1)(x+2)]$
- $P(x) = F_x$ the Fibonacci number
4. Determine the following summations $$1 \times 2 + 2 \times 3 + \dots + n(n+1)$$ $$\frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \dots + \frac{1}{n(n+1)}$$
Generalize these results.
5. Prove the following formula for difference of a product
$$\Delta(u(x) v(x)) = \Delta(u(x)) ~v(x) + u(x+1) ~\Delta(v(x)).$$