Dear friends of MHB

in this thread some aspects of the difference equation of degree greater than one are investigated. For size limitation the tutorial is divided into several sections. As for the part I, suggestions, observations, requests of clarification and improvements are welcome...

Kind regards

$\chi$ $\sigma$

---------- Post added at 16:32 ---------- Previous post was at 16:27 ----------

Difference equation tutorial- Part II: difference equations of order greater than one

By: Carlo Sabatini

1. Linear second order homogeneous difference equations

The second order difference equation…

$\displaystyle a_{n+2}+ \alpha_{n}\ a_{n+1} + \beta_{n}\ a_{n}=0$ (1.1)

… is calledlinear homogeneous. Here $\displaystyle \alpha_{n}$ and $\displaystyle \beta_{n}$ are functions of n. By inspection You immediately see that $\displaystyle a_{n}=0$ is solution of (1.1). Also comfortable is to see that if $u_{n}$ and $v_{n}$ are solutions, then $\displaystyle z_{n}= c_{1}\ u_{n}+ c_{2}\ v_{n}$, where $c_{1}$ and $c_{2}$ are 'arbitrary constants', is also a solution, that because multiplying $u_{n}$ by $c_{1}$ and $v_{n}$ by $c_{2}$ and taking into account (1.1) You obtain…

$\displaystyle c_{1}\ u_{n+2}+ c_{2}\ v_{n+2}+ \alpha_{n}\ (c_{1}\ u_{n+1}+ c_{2}\ v_{n+1}) + \beta_{n}\ (c_{1}\ u_{n}+ c_{2}\ v_{n})=0$

A very important theorem establishes thatanysolution of (1.1) can be expressed as $\displaystyle a_{n}= c_{1}\ u_{n} + c_{2}\ v_{n}$ if both $u_{n}$ and $v_{n}$ are solutions of (1.1) and is…

$\displaystyle w_{n}= u_{n}\ v_{n-1} – v_{n}\ u_{n-1} \ne 0\ ,\ \forall n$ (1.2)

… where the quantity $w_{n}$ is called ‘Wronskian determinant’. If You know $a_{0}$ and $a_{1}$ [but also any other pair of consecutive $a_{n}$...] the (1.1) imposes that…

$\displaystyle c_{1}\ u_{0}+ c_{2}\ v_{0}=a_{0}\ ,\ c_{1}\ u_{1}+c_{2}\ v_{1}=a_{1}$

… and the fact that $\displaystyle u_{1}\ v_{0} – v_{1}\ u_{0}= w_{1} \ne 0$ allows You to write…

$\displaystyle c_{1}=\frac{a_{1}\ v_{0} - a_{0}\ v{1}}{w_{1}}\ ,\ c_{2}=\frac{a_{0}\ u_{1}- a_{1}\ u_{0}}{w_{1}}$ (1.3)

As for first order [linear or non linear…] difference equations the direct computation of the $a_{n}$ from the (1.1) is ever possible. A ‘closed form’ solution of the (1.1) starting from ‘initial conditions’ $a_{0}=a$ and $a_{1}=b$ is allowable only in ‘favorable conditions’ and among them the most favorable is the case where the $\alpha_{n}$ and $\beta_{n}$ are constants, so that the (1.1) becomes…

$\displaystyle a_{n+2}+ \alpha\ a_{n+1} + \beta\ a_{n}=0\ ,\ a_{0}=a\ ,\ a_{1}=b$ (1.4)

Now we write the second order equation [calledcharacteristic equation]…

$\displaystyle r^{2}+ \alpha\ r + \beta=0$ (1.5)

… and we consider three alternatives…

a) $\displaystyle \alpha^{2}-4\ \beta>0$. In this case the (1.5) has two real distinct solutions $r_{1}$ and $r_{2}$ and, as a simple test can verify, is…

$\displaystyle u_{n}=r_{1}^{n}\ ,\ v_{n}=r_{2}^{n}$ (1.6)

b) $\displaystyle \alpha^{2}-4\ \beta>0$. In this case the (1.5) has one solution r with multiplicity 2 and, as a simple test can verify, is…

$\displaystyle u_{n}=r^{n}\ ,\ v_{n}=n\ r^{n}$ (1.7)

c) $\displaystyle \alpha^{2}-4\ \beta< 0$. In thi case the (1.5) has two complex and conjugate solutions $\displaystyle r\ e^{\pm i\ \theta}$ and, as simple test can verify, is…

$\displaystyle u_{n}=r^{n}\ \cos n \theta,\ v_{n}=r^{n}\ \sin n \theta$ (1.8)

The most famous second order linear homogeneous difference equation is probably the following…

$f_{n+2}-f_{n+1}-f_{n}=0\ ,\ f_{0}=0\ ,\ f_{1}=1$ (1.9)

… the solution of which is the integer sequence 0,1,1,2,3,5,8,13,21,34,55,89,144…, universally known asFibonacci sequencebecause the Italian mathematician Leonardo Pisano known as Fibonacci first [in Western…] described it in the bookLiber Abaciin the year 1202 as a solution of the problem of the growth of rabbit populations. The closed form solution of the (1.9) is obtained as described in a) by solving characteristic equation $\displaystyle r^{2}-r-1=0$ and is…

$\displaystyle f_{n}= \frac{\varphi^{n}- \varphi^{-n}}{\sqrt{5}}$ (1.10)

… where the constant…

$\displaystyle \varphi= \frac{1+\sqrt{5}}{2}= 1.6180339887…$ (1.11)

… is known asgolden ratio. In the last 800 years the Fibonacci’s difference equation has been investigated by the mathematicians of all continents, a large number of useful results have been derived from it and it is not excluded that that will be true also in the future. Space limitations don’t allow us to describe all the possible application of the Fibonacci’s difference equation, so that only two examples will be supplied.

First we examine a possible way to solve a first order non-linear difference equation that hasn’t been described in part I. Let’s suppose we have the following first order non-linear difference equation…

$\displaystyle a_{n+1}=1+\frac{1}{a_{n}}\ ,\ a_{1}=1$ (1.12)

If we set in (1.12) $\displaystyle a_{n}=\frac{b_{n+1}}{b_{n}}$, then we obtain…

$\displaystyle b_{n+2}-b_{n+1}-b_{n}=0\ b_{0}=0\ ,\ b_{1}=1$ (1.13)

… that of course is the Fibonacci’s difference equation. The solution of (1.12) is an increasing sequence and it is easy to see that $\displaystyle \lim_{n \rightarrow \infty} a_{n}= \varphi$.

The second example is an application of image processing. If you want to transmit an image it is necessary to convert the rows and columns forming the image into a serial data stream that will be transmitted through a communication channel. Among the possible ways to do it, the most efficient require that in the binary stream consecutives ones aren’t allowed. Now we define with $a_{n}$ the number of possible binary sequence of length n and the first step is to find an expression for $a_{n}$. For n=1 we have the sequences 0 and 1 so that is $a_{1}=2$. For n=2 we have the sequences 00, 01 and 10 [11 isn’t allowed…] so that is $a_{2}=3$. For n=3 we have the sequences 000, 001, 010, 100 and 101 [011, 110 and 111 aren’t allowed…] so that is $a_{3}=5$. Proceeding for larger values of n, it is not too difficult to ‘discover’ that is $a_{n}=f_{n+1}$,i.e. the $a_{n}$ is the Fibonacci’s sequence shifted by one element. The second step is the computation of the so calledchannel capacity, i.e. the maximum possible amount of information transmitted through the channel with 1 Hz bandwidth in 1 second. According to Shannon’s theory, the channel capacity is our case is…

$\displaystyle C=\lim_{n \rightarrow \infty} \frac{\log a_{n}}{n}$ (1.14)

… where the logarithm is ‘base 2’. Taking into account the (1.10) and that $a_{n}=f_{n+1}$ we obtain with simple steps…

$\displaystyle C= \lim_{n \rightarrow \infty} \frac{1}{n}\ \frac{\log (\varphi^{n+1}- \varphi^{-n-1})}{\sqrt{5}}= \lim_{n \rightarrow \infty} \frac{n+1}{n}\ \log \varphi = \log \varphi =.69424191363…$

In my opinion the reported material supplies to the reader an powerful and ‘easy to use’ tool for the solution of second order homogeneous DE with constant coefficients. At this point a spontaneous question: what to do in case of non constant coefficients?... In that case a general solving procedure is hard to find and often it is necessary to use anad hocapproach. As example let’s consider the second order DE…

$\displaystyle a_{n+2}- 2\ x\ a_{n+1}+2\ (n+1)\ a_{n}=0$ (1.15)

A solution of (1.15) is found using the so calledHermite Polynomialsthat are solution of the second order differential equation...

$\displaystyle y^{\ ''} -2\ x\ y^{\ '} +2\ n\ y=0$ (1.16)

… and are explicitly written as…

$\displaystyle H_{n}(x)= (2 x)^{n} - \frac{n\ (n-1)}{1!}\ (2 x)^{n-2} + \frac{n\ (n-1)\ (n-2)}{2!}\ (2x)^{n-4}-…$ (1.17)

Among the properties of Hermite Polynomial there is the recursive relation…

$\displaystyle H_{n+1}(x)= 2\ x\ H_{n}(x)-2\ n\ H_{n-1}(x)$ (1.18)

... and from that we derive that a solution of (1.15) is...

$\displaystyle a_{n}= H_{n}(x)$ (1.19)

The (1.19) is a solution of (1.16) but we know that to construct the general solution we need another solution independent from it and now we illustrate a general procedure to obtain, given a solution of the (1.1), another solution independent from it. If $u_{n}$ and $v_{n}$ are solutions of (1.1), then setting $\displaystyle z_{n}=\frac{u_{n}}{v_{n}}$ and substituting we obtain…

$\displaystyle v_{n+2}\ (z_{n+2}-z_{n+1})+ (v_{n+2}+ \alpha_{n}\ v_{n+1})\ (z_{n+1}-z_{n})=0$ (1.20)

… which is first order in $\displaystyle w_{n}=z_{n+1}-z_{n}$. In the case of (1.15) the (1.20) becomes…

$\displaystyle w_{n+1} + \{ 1-\frac{2\ x\ H_{n+1}(x)}{H_{n+2}(x)}\}\ w_{n}=0$ (1.21)

… the solution of which is the desired goal.

Of course what is reported here is only a short introduction and the interested reader is recommended to consult specialized literature…

Comments and questions should be posted here: