Sequence - Part 6

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!

We can show that formula for the difference of order $j$ is $$\Delta^j(P(x)) = P(x+j) - {j \choose {j-1}} P(x+j-1) + {j \choose {j-2}} P(x+j-2) - \dots + (-1)^{j-1} {j \choose 1} P(x+1) + (-1)^j P(x).$$
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.

Proof of the fundamental theorem

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$.

We make a remark that if $j_1 = \dots = j_t=1$, i.e. the characteristic equation only has single roots as $$a_k x^k + a_{k-1} x^{k-1} + \dots + a_1 x + a_0=a_k(x - z_1) (x - z_2) \dots (x - z_k),$$ then the polynomials $p_1(n)$,..., $p_k(n)$ have degree less than $1$, that means they are equal to constants, so we can write $p_i(n) = \alpha_i$ and we have the formula $$f_n = \alpha_1 ~ z_1^n + \alpha_2 ~ z_2^n+ \dots + \alpha_k ~ z_k^n.$$

Let us stop here for now. As we have proved the fundamental theorem for linear recurrence equations, now is a good time to go back to the first post of the series and read all the posts again.

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)).$$