1 Preliminaries: Sequences and Difference Equations

1.1 Sequences

A sequence is a set of numbers formed according to some definite rule. For example the sequence

$\left\{1,4,9,16,25,\dots \right\}\left(1\right)$

is formed by the squares of the positive integers.

If we write

$y_1=1,y_2=4,y_3=9,\dots$

then the general or $n^{th}$ term of the sequence (1) is $y_n=n^2$ . The notations $y\left(n\right)$ and $y\left[n\right]$ are also used sometimes to denote the general term. The notation $\left\{y_n\right\}$ is used as an abbreviation for a whole sequence.

An alternative way of considering a sequence is to view it as being obtained by sampling a continuous function. In the above example the sequence of squares can be regarded as being obtained from the function

$y\left(t\right)=t^2$

by sampling the function at $t=1,2,3,\dots$ as shown in Figure 1.

Figure 1

The notation $y\left(n\right)$ , as opposed to $y_n$ , for the general term of a sequence emphasizes this sampling aspect.

Task!

Find the general term of the sequence $\left\{2,4,8,16,32,\dots \right\}$ .

Answer

An alternative way of defining a sequence is as follows:

1. give the first term $y_1$ of the sequence
2. give the rule for obtaining the ${\left(n+1\right)}^{\text{th}}$ term from the $n^{\text{th}}$ .

A simple example is

$y_{n+1}=y_n+d{y}_1=a$

where $a$ and $d$ are constants.

It is straightforward to obtain an expression for $y_n$ in terms of $n$ as follows:

(2)

This sequence characterised by a constant difference between successive terms

$y_{n+1}-y_n=dn=1,2,3,\dots$

is called an arithmetic sequence.

Task!

Calculate the $n^{\text{th}}$ term of the arithmetic sequence defined by

$y_{n+1}-y_n=2$ $y_1=9$ .

Write out the first 4 terms of this sequence explicitly.

Suggest why an arithmetic sequence is also known as a linear sequence.

Answer

1.2 Nomenclature

The equation

$y_{n+1}-y_n=d$ (3)

is called a difference equation or recurrence equation or more specifically a first order, constant coefficient, linear, difference equation.

The sequence whose $n^{\text{th}}$ term is

$y_n=a+\left(n-1\right)d$ (4)

is the solution of (3) for the initial condition $y_1=a$ .

The coefficients in (3) are the numbers preceding the terms $y_{n+1}$ and $y_n$ so are 1 and $-1$ respectively.

The classification first order for the difference equation (3) follows because the difference between the highest and lowest subscripts is $n+1-n=1.$

Now consider again the sequence

$\left\{y_n\right\}=\left\{2^n\right\}$

Clearly

$y_{n+1}-y_n=2^{n+1}-2^n=2^n$

so the difference here is dependent on $n$ i.e. is not constant. Hence the sequence $\left\{2^n\right\}=\left\{2,4,8,\dots \right\}$ is not an arithmetic sequence.

Task!

For the sequence $\left\{y_n\right\}=2^n$ calculate $y_{n+1}-2y_n$ . Hence write down a difference equation and initial condition for which $\left\{2^n\right\}$ is the solution.

Answer

More generally it follows that

$y_{n+1}-A{y}_n=0y_1=A$

has solution sequence $\left\{y_n\right\}$ with general term

$y_n=A^n$

1.3 A second order difference equation

Second order difference equations are characterised, as you would expect, by a difference of 2 between the highest and lowest subscripts. A famous example of a constant coefficient second order difference equation is

$y_{n+2}=y_{n+1}+y_n$ or $y_{n+2}-y_{n+1}-y_n=0$ (6)

The solution $\left\{y_n\right\}$ of (6) is a sequence where any term is the sum of the two preceding ones.

Task!

What additional information is needed if (6) is to be solved?

Answer

Answer

$y_{n+1}=y_{n+1}+y_n$

with initial conditions $y_1=y_2=1$ is the Fibonacci sequence. What is not so obvious is what is the general term $y_n$ of this sequence.

One way of obtaining $y_n$ in this case, and for many other linear constant coefficient difference equations, is via a technique involving $Z-$ transforms which we shall introduce shortly.

1.4 Shifting of sequences

Right Shift

Recall the sequence $\left\{y_n\right\}=\left\{n^2\right\}$ or, writing out the first few terms explicitly,

$\left\{y_n\right\}=\left\{1,4,9,16,25,\dots \right\}$

The sequence $\left\{v_n\right\}=\left\{0,1,4,9,16,25,\dots \right\}$   contains the same numbers as $y_n$ but they are all shifted one place to the right. The general term of this shifted sequence is

$v_n={\left(n-1\right)}^{2}n=1,2,3,\dots$

Similarly the sequence

$\left\{w_n\right\}=\left\{0,0,1,4,9,16,25,\dots \right\}$

has general term

$w_n=\left\{\begin{array}{ccc}\hfill {\left(n-2\right)}^2\hfill & \hfill \hfill & n=2,3,\dots \hfill \\ \hfill 0\hfill & \hfill \hfill & n=1\hfill \end{array}\right.$

Task!

For the sequence $\left\{y_n\right\}=\left\{2^n\right\}=\left\{2,4,8,16,\dots \right\}$ write out explicitly the first 6 terms and the general terms of the sequences $v_n$ and $w_n$ obtained respectively by shifting the terms of $\left\{y_n\right\}$

1. one place to the right
2. three places the the right.

Answer

The operation of shifting the terms of a sequence is an important one in digital signal processing and digital control. We shall have more to say about this later. For the moment we just note that in a digital system a right shift can be produced by delay unit denoted symbolically as follows:

Figure 2

A shift of 2 units to the right could be produced by 2 such delay units in series:

Figure 3

(The significance of writing $z^{-1}$ will emerge later when we have studied $z-$ transforms.)

Left Shift

Suppose we again consider the sequence of squares

$\left\{y_n\right\}=\left\{1,4,9,16,25,\dots \right\}$

with $y_n=n^2$ .

Shifting all the numbers one place to the left (or advancing the sequence) means that the sequence $\left\{v_n\right\}$ generated has terms

$v_0=y_1=1v_1=y_2=4v_2=y_3=9\dots$

and so has general term

$v_n={\left(n+1\right)}^{2}n=0,1,2,\dots$

$=y_{n+1}$

Notice here the appearance of the zero subscript for the first time.

Shifting the terms of $\left\{v_n\right\}$ one place to the left or equivalently the terms of $\left\{y_n\right\}$ two places to the left generates a sequence $\left\{w_n\right\}$ where

$w_{-1}=v_0=y_1=1w_0=v_1=y_2=4$

and so on.

The general term is

$w_n={\left(n+2\right)}^{2}n=-1,0,1,2,\dots$

$=y_{n+2}$

Task!

If $\left\{y_n\right\}=\left\{1,1,2,3,5,\dots \right\}n=1,2,3,\dots$ is the Fibonacci sequence, write out the terms of the sequences $\left\{y_{n+1}\right\},\left\{y_{n+2}\right\}$ .

Answer

It should be clear from this discussion of left shifted sequences that the simpler idea of a sequence ‘beginning’ at $n=1$ and containing only terms $y_1,y_2,\dots$ has to be modified.

We should instead think of a sequence as two-sided i.e. $\left\{y_n\right\}$ defined for all integer values of $n$ and zero. In writing out the ‘middle’ terms of a two sided sequence it is convenient to show by an arrow the term $y_0$ .

For example the sequence $\left\{y_n\right\}=\left\{n^2\right\}n=0,\pm 1,\pm 2,\dots$ could be written

$\left\{\dots 9,4,1,0,1,4,9,\dots \right\}$

   $\uparrow$

A sequence which is zero for negative integers $n$ is sometimes called a causal sequence.

For example the sequence, denoted by $\left\{u_n\right\}$ ,

$u_n=\left\{\begin{array}{ccc}\hfill 0\hfill & \hfill \hfill & n=-1,-2,-3,\dots \hfill \\ \hfill 1\hfill & \hfill \hfill & n=0,1,2,3,\dots \hfill \end{array}\right.$

is causal. Figure 4 makes it clear why $\left\{u_n\right\}$ is called the unit step sequence .

Figure 4

The ‘curly bracket’ notation for the unit step sequence with the $n=0$ term arrowed is

$\left\{u_n\right\}=\left\{\dots ,0,0,0,1,1,1,\dots \right\}$

   $\uparrow$

Task!

Draw graphs of the sequences $\left\{u_{n-1}\right\},\left\{u_{n-2}\right\},\left\{u_{n+1}\right\}$ where $\left\{u_n\right\}$ is the unit step sequence.

Answer