Dear friends of MHB

some months ago I wrote for MHF a tutorial on the Difference equations and the reason of that was the difficulties I noticed in the treatment of difference equations, an important chapter of Discrete Maths that [may be...] is a little unfairly undervaluated. Request by the staff I decided to rewrite, with some rearrangements and improvements, the tutorial on MHB asdraftofPart I:general concepts about sequences and first order difference equations, which for size reason has been divided in four parts...

I will appreciate very much all the errors, omissions, modifications, suggestion and requests of clarification that You all will express about my work...

Kind regards

$\chi$ $\sigma$

---------- Post added at 05:37 PM ---------- Previous post was at 05:25 PM ----------

Difference equation tutorial- Part I: general concepts about sequences and first order difference equations

By: Carlo Sabatini

1. Definitions

In mathematics there are various definitions of ‘sequence’ so that we adopt, among them, the most suitable with the purposes of this tutorial work. We define sequence a set of numbers each of them associated to a natural number n, supposing that the set of natural numbers includes the 0. Each term of a sequence a is written as $\displaystyle a_{n} ,n=0,1,2, …$. In general we will consider the term ‘sequence’ and ‘discrete function’ as synonyms. Each term can be real or complex, so that there are real or complex sequences. If nothing is specified a sequence has to be considered as a real sequence.

Like a ‘conventional’ function of real variable, a discrete function can be defined in explicit or implicit form. Defining a sequence in explicit form means to have a computational formula that permits for each n to compute the corresponding $\displaystyle a_{n}$. A simple example of sequence defined in explicit form is…

$\displaystyle a_{n}=2\ n$ (1.1)

Defining a sequence in implicit form means to have an expression of the type…

$\displaystyle f(n,a_{n},a_{n+1},a_{n+2},…,a_{n+k})=0$ (1.2)

... combined with the ‘initial conditions’…

$\displaystyle a_{0}=\alpha_{0},a_{1}=\alpha_{1}, … ,a_{k-1}=\alpha_{k-1}$ (1.3)

An expression like the (1.2) combined with the initial conditions like the (1.3) is called recursive relation, or alternatively difference equation. The index k in (1.2) is the order of the difference equation. ‘Solving’ a difference equation means to find, given the (1.2) and (1.3), an expression of the $\displaystyle a_{n}$ like (1.1). As we will see later, that is not always feasible or ‘comfortable’. The reason of the ‘dual name’ will be explained in detail in a successive section.

2. Some basic sequences

Now we define some ‘fundamental sequences’ that are commonly used practically in all branches of Mathematics. The first of them is theunit sample sequence, defined as…

$\displaystyle \delta_{n}=\begin{cases}1&\text{if}\ n=0\\ 0 &\text{if}\ n>0\end{cases}$ (2.1)

The unit sample sequence $\displaystyle \delta_{n}$ plays the same role of the ‘impulsive function’ $\displaystyle \delta(t)$ in the continuous functions set but, and that is remarkable, it doesn’t suffer of any ‘complication’ in the definition for n=0.

The second ‘fundamental sequence’ [or, more exactly, ‘fundamental set of sequences’…] is theexponential sequence on base$\displaystyle \alpha$ the general term of which is usually written as $\displaystyle \alpha^{n}$ and defined by the recursive relation…

$\displaystyle a_{n+1}= \alpha\ a_{n}\ ,\ a_{0}=1\ ,\ \alpha \in \mathbb{R}$ (2.2)

It is important to precise that $\displaystyle \alpha$ can be any real number, even negative and even 0 , so that any ‘ambiguity’ in the definition of $\displaystyle 0^{0}$ doesn’t exist in Discrete Mathematics. In particular the sequence $\displaystyle 0^{n}$ is different from the ‘all zero sequence’ and is $\displaystyle 0^{n}=\delta_{n}$. A significant difference between continuous and discrete Mathematics in the fact that in the first the ‘exponential function’ has as base the number e, defined as…

$\displaystyle e=\lim_{n\rightarrow \infty} (1+\frac{1}{n})^{n}$

That is in continuous mathematics. In discrete mathematics any real number $\displaystyle \alpha$ can be the base of an ‘exponential sequence’ and don’t exist any particular ‘privilege’.

The last ‘fundamental sequence’ we go to define is thefactorial sequence, the general term of which is written as $\displaystyle n!$ and defined by the recursive relation…

$\displaystyle a_{n+1}= (n+1)\ a_{n}\ ,\ a_{0}=1$ (2.3)

Also for factorials the definition (2.3) eliminates any ‘complication’ regarding $\displaystyle 0!$, so that we can say that that is an important ‘common property’ of the three ‘fundamental sequences’ examined in this section.

3. Transforming a recursive relation into a difference equation and vice-versa

The reason of the ‘duality of the name’ is now explained starting from definition of first difference, second difference and ‘difference of order k’. Given a sequence $\displaystyle a_{n}$ we define asfirst differencethe quantity…

$\displaystyle \Delta_{n}=a_{n+1}-a_{n}$ (3.1)

… andsecond differencethe quantity…

$\displaystyle \Delta_{n}^{2}= \Delta_{n+1}-\Delta_{n}=a_{n+2}-2\ a_{n+1}+a_{n}$ (3.2)

In general thedifference of order kof a sequence is the quantity…

$\displaystyle \Delta_{n}^{k}=\Delta_{n+1}^{k-1}-\Delta_{n}^{k-1}$ (3.3)

An useful property of the recursive relation written in the form (1.2) is the fact that it can be rewritten in term of differences as…

$\displaystyle f(n,a_{n},\Delta_{n},\Delta_{n}^{2},…,\Delta_{n}^{k})=0$ (3.4)

This possibility, as we will see in a successive section, may be very useful and an illustrative example is appropriate. The following second order recursive relation…

$\displaystyle a_{n+2}=a_{n+1}+a_{n}$ (3.5)

… is well known and, with the initial conditions $\displaystyle a_{0}=0$ and $\displaystyle a_{1}=1$, it generates the ‘Fibonacci’s sequence’. Now with simple steps the (3.5) is transformed in the form (3.4) as…

$\displaystyle \Delta_{n}^{2}-\Delta_{n}-a_{n}=0$ (3.6)

In the successive sections we will use both the expression (1.2) and (3.4), simply taking into account which is more ‘comfortable’ and in both cases will use the term ‘difference equation’…

Comments and questions should be posted here: