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

## No comments:

## Post a Comment