Difference equation tutorial: draft of part II

[chisigma]

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 called linear 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 that any solution 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 [called characteristic 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 as Fibonacci sequence because the Italian mathematician Leonardo Pisano known as Fibonacci first [in Western…] described it in the book Liber Abaci in 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 as golden 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 called channel 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 an ad hoc approach. 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 called Hermite Polynomials that 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:

http://mathhelpboards.com/commentary-threads-53/commentary-difference-equation-tutorial-draft-part-ii-4232.html

 

[chisigma]

2. Linear second order non homogeneous difference equations

The second order difference equation…

$\displaystyle a_{n+2}+ \alpha_{n}\ a_{n+1} + \beta_{n}\ a_{n}= \gamma_{n}$ (2.1)

… is called linear non homogeneous. Like the $\alpha_{n}$ and the $\beta_{n}$, the $\gamma_{n}$ depend from n. First step is to demonstrate that if $u_{n}$ and $v_{n}$ are independent solutions of the homogeneous DE [the (2.1) where for all n is $\displaystyle \gamma_{n}=0$...] and $w_{n}$ is a particular solution of the (2.1), then the general solution of the (2.1) is…

$\displaystyle a_{n}= c_{1}\ u_{n} + c_{2}\ v_{n} + w_{n}$ (2.2)

… where $c_{1}$ and $c_{2}$ are arbitrary constants. If the (2.2) is the general solution of the (2.1) and $w_{n}$ a particular solution of the (2.1), then setting $\displaystyle d_{n}=a_{n}-w_{n}$ we have...

$\displaystyle d_{n+2}+\alpha_{n}\ d_{n+1} + \beta_{n}\ d_{n}=0$ (2.3)

The (2.3) is homogeneous and has general solution $\displaystyle d_{n}=c_{1}\ u_{n} + c_{2}\ v_{n}$ so that is $\displaystyle a_{n}=d_{n}+w_{n}$ and the (2.2) is demonstrated. Respect to the homogeneous case, the solution of a non homogeneous DE requires as further step to find a particular solution $w_{n}$ and now we illustrate a possible procedure to achieve that using as example again the Fibonacci’s DE…

$\displaystyle a_{n+2}-a_{n+1}-a_{n}=c\ x^{n}$ (2.4)

Here $\gamma_{n}$ is an exponential sequence so that a spontaneous approach is to search $w_{n}$ among the exponential sequences and this approach works in most cases. Setting $w_{n}=\chi\ x^{n}$ in (2.2) we obtain $\displaystyle \chi= \frac{c}{x^{2}-x-1}$ so that the general solution of (2.4) is…

$\displaystyle a_{n}= c_{1}\ \varphi^{n} + c_{2}\ \varphi^{-n} + \frac{c\ x^{n}}{x^{2}-x-1}$ (2.5)

… where the constant $\varphi$ is the ‘golden ratio’ defined in the previous section. It is obvious that the approach is valid only if $\displaystyle x^{2}-x-1 \ne 0$... what to do if is $\displaystyle x^{2}-x-1=0$?... in this case searching a function of the type $\displaystyle w_{n}= \chi\ n\ x^{n}$ we obtain $\displaystyle \chi=\frac{c}{2 x^{2}-x} \implies w_{n}= \frac{c\ n\ x^{n}}{2 x^{2}-x}$.

A sort of ‘useful manual’ dedicated to the problem of finding a $w_{n}$ given the $\gamma_{n}$ is illustrated in the following table…

$\displaystyle \gamma_{n}=c\ x^{n} \implies w_{n}=\chi\ x^{n}$

$\displaystyle \gamma_{n}=n^{m} \implies w_{n}=\chi_{0}+\chi_{1}\ n + \chi_{2}\ n^{2}+…+ \chi_{m}\ n^{m}$

$\displaystyle \gamma_{n}=n^{m}\ x^{n} \implies w_{n}=x^{n}\ (\chi_{0}+\chi_{1}\ n + \chi_{2}\ n^{2}+…+ \chi_{m}\ n^{m})$

$\displaystyle \gamma_{n}=\sin \omega n$ or $\displaystyle \gamma_{n}=\cos \omega n \implies w_{n}= \chi_{1}\ \sin \omega n + \chi_{2}\ \cos \omega n$

$\displaystyle \gamma_{n}=x^{n}\ \sin \omega n$ or $\displaystyle \gamma_{n}=x^{n}\ \cos \omega n \implies w_{n}= x^{n}\ (\chi_{1}\ \sin \omega n + \chi_{2}\ \cos \omega n)$

table 2.1


Some caution is to be adopted using the table 2.1 because the $w_{n}$ are valid only if the sequences themselves aren’t solution of the homogeneous DE and if that is the case a different procedure must be adopted. As example let’s consider the following DE, known as ‘national income equation’…

$\displaystyle i_{n+2}-2\ a\ i_{n+1} + a\ i_{n}=1$ (2.5)

… where a and I are constant. First we suppose that $0<a<1$. The characteristic equation of the homogeneous DE is $\displaystyle r^{2}-2\ a\ r\ + a=0$ and its solution are…

$\displaystyle r=a \pm \sqrt{a^{2}-a}= \sqrt{a}\ e^{\pm i\ \theta}$ (2.6)

... where $\displaystyle \theta= \tan^{-1} \sqrt{\frac{1-a}{a}}$, so that the solution of (2.5) is…

$\displaystyle i_{n}= a^{\frac{n}{2}}\ (c_{1}\ \sin n\ \theta + c_{2}\ \cos n\ \theta) + w_{n}$ (2.7)

Here $\gamma_{n}=1$ is a constant and the table 2.1 suggests that also $w_{n}$ is a constant. With little efforts you find that is $\displaystyle w_{n}= \frac{1}{1-a}$. Now it is interesting to observe what it happens if in (2.5) is $a=1$. The characteristic equation becomes $\displaystyle r^{2}-2\ r +1=0$ and it has the only solution $r=1$ with multiplicity 2, so that the solution is…

$\displaystyle i_{n}= c_{1}+ c_{2}\ n + w_{n}$ (2.8)

The procedure for finding $w_{n}$ previously adopted and based on the table 2.1 in that case doesn't work because $w_{n}=\chi$ and also $w_{n}=\chi\ n$ are solutions of the homogeneous DE. If we set however $w_{n}=\chi\ n^{2}$ we are 'lucky' and the $w_{n}$ is particular solution of (2.5) with $a=1$ when $\chi=\frac{1}{2}$. In a successive section a more flexible approach to this type of problems based on the Z-Transform will be illustrated.

We now conclude this section illustrating how a second order non homogeneous DE can simplify the solution of some integrals. Let’s suppose to have the definite integral…

$\displaystyle I_{n}= \int_{0}^{1} \frac{x^{n}}{x^{2}+x+1}\ dx$ (2.9)

The standard solution of (1) through a primitive is hard because it involves non elementary functions, so that an alternative approach is quite welcome. The 'trivial' identity...

$\displaystyle \frac{x^{n}}{x^{2}+x+1}= x^{n-2} - \frac{x^{n-1}}{x^{2}+x+1} - \frac{x^{n-2}}{x^{2}+x+1}$ (2.10)

... leads to the linear second order non homogeneous DE...

$\displaystyle I_{n+2}+ I_{n+1}+ I_{n}= \frac{1}{n+1}$ (2.11)

The (2.11) and the knowledge of the integrals...

$\displaystyle I_{0}=\int_{0}^{1} \frac{dx}{x^{2}+x+1}= \frac{2}{\sqrt{3}}\ (\tan^{-1} \sqrt{3}-\tan^{-1} \frac{1}{\sqrt{3}})= .604599788078…$

$\displaystyle I_{1}=\int_{0}^{1} \frac{x}{x^{2}+x+1}\ dx= \frac{\ln 3}{2} - \frac{1}{\sqrt{3}}\ (\tan^{-1} \sqrt{3}-\tan^{-1} \frac{1}{\sqrt{3}})=.247006250295...$

... permit a comfortable computing of the integral (2.9) for n=2,3,...

 

[chisigma]

3. Non linear second order difference equations

It is easy to guess that the attack to a non linear second order difference equation is much harder respect to the first order case and almost always an ad hoc approach is required. An interesting example of difference equation a closed form solution of which can be found is the following...

$\displaystyle a_{n+2} = (h_{n} + \frac {a_{n+1}}{a_{n}})\ a_{n+1}$ (3.1)

... where $h_{n}$ is a known sequence. Now we intend to demonstrate that, if the initial values $a_{0} \ne 0$ and $a_{1}$ are defined, the solution of (3.1) is given by...

$\displaystyle a_{n}= a_{1}\ \prod_{k=0}^{n-2} (\frac{a_{1}}{a_{0}} + \sum_{j=0}^{k} h_{j})$ (3.2)

The demonstration is based on the induction principle, i.e. if (3.2) is true for n=m-1 and n=m, then it is true for n=m+1. From (3.1) we have…

$\displaystyle a_{m+1}= \frac{a^{2}_{m}}{a_{m-1}}+ h_{m-1}\ a_{m}$

… so that using (3.2) we can write…

$\displaystyle a_{m+1}= \{ a_{1}\ \prod_{k=0}^{m-2} (\frac{a_{1}}{a_{0}} + \sum_{j=0}^{k} h_{j})\}\ (\frac{a_{1}}{a_{0}}+ \sum_{j=0}^{m-2} h_{j}) + h_{m-1}\ a_{1}\ \prod_{k=0}^{m-2} (\frac{a_{1}}{a_{0}} + \sum_{j=0}^{k} h_{j})= a_{1} \prod_{k=0}^{m-1} (\frac{a_{1}}{a_{0}} + \sum_{j=0}^{k} h_{j}) $

Because if we set in (3.1) $n=2$ and $n=3$ we obtain...

$\displaystyle a_{2}= \frac{a_{1}^{2}}{a_{0}} + h_{0}\ a_{1}$

$\displaystyle a_{3}= \frac{a_{1}^{3}}{a_{0}^{2}} + (2\ h_{0}+ h_{1})\ \frac {a_{1}^{2}}{a_{0}} + (h_{0}^{2} + h_{1}\ h_{0}) a_{1}$

… and (3.2) is verified, by induction the (3.2) is verified for all n. Some considerations about the convergence of the solution given by (3.2)...

a) if $\displaystyle \frac{a_{1}}{a_{0}}>1$ the sequence $a_{n}$ diverges...

b) if $\displaystyle \frac{a_{1}}{a_{0}}=1$ the sequence $a_{n}$ converges only if converges the series $\displaystyle \sum_{k=0}^{\infty} \sum_{j=0}^{k} h_{j}$...

c) if $\displaystyle \frac{a_{1}}{a_{0}}<1$ the sequence $a_{n}$ tends to 0 if converges the series $\displaystyle \sum_{k=0}^{\infty} \sum_{j=0}^{k} h_{j}$...

The example we have supplied shows clearly how difficult almost always is the approach to such a type of difference equation. In some circumstances the task is more comfortable, for example when we can transform the second order difference equation into a first order one as in that case...

$\displaystyle a_{n+2}= \gamma\ \frac{a_{n}}{1+a_{n+1}\ a_{n}}\ \gamma>0$ (3.3)

The (3.3) with the substitution $\displaystyle x_{n}= a_{n}\ a_{n+1}$ becomes...

$\displaystyle x_{n+1}= \gamma\ \frac{x_{n}}{1+x_{n}}$

... that can be solved with the procedure described in the section I solving the equation...

$\displaystyle \Delta_{n} = x_{n+1}-x_{n}= \gamma \frac{x_{n}}{1+x_{n}} = f(x_{n})$

The function $\displaystyle f(x)= \gamma\ \frac{x}{1+x} - x$ in the particular case $\gamma=3$ is illustrated here...

View attachment 651

fig. 3.1

Its roots are $x=0$ and $x=\gamma-1$ and, with the only exception of the case $\gamma=1$, the higher is an attractive fixed point and the lower a repulsive fixed point. We have three different cases...a) $\displaystyle \gamma > 1$ where for any $\displaystyle x_{0} > 0$ the sequence $x_{n}$ converges at $x=\gamma-1$...

b) $\displaystyle \gamma = 1$ where for any $\displaystyle x_{0} \ne 0$ the sequence $x_{n}$ diverges...

c) $\displaystyle 0< \gamma < 1$ where for any $\displaystyle x_{0} > \gamma-1 $ the sequence $x_{n}$ converges at $x=0$...

A similar and also more comfortable procedure can be followed if in the difference equation the term in $a_{n+1}$ is missing, like in that case...

$\displaystyle a_{n+2}= a^{4}_{n} - 2\ a^{2}_{n}$ (3.4)

The term in $a_{n=1}$ is missing, so that we can split the sequence $a_{n}$ into two subsequence, one with n even and the other with n odd, each of them satisfying the first order difference equation...

$\displaystyle x_{n+1}= x^{4}_{n} - 2\ x^{2}_{n}$

... that can be written in the form...

$\displaystyle \Delta_{n}= x_{n+1}-x_{n} = x^{4}_{n} - 2\ x^{2}_{n} - x_{n} = f(x_{n})$

The function $\displaystyle f(x)= x^{4} - 2\ x^{2} - x$ is represented here...

View attachment 652fig. 3.2

There are two attractive fixed points in $x=-1$ and $x=0$ and two repulsive fixed points in $\displaystyle x = \frac{1 \pm \sqrt{5}}{2}$, so that with an approriate choise of $a_{0}$ and $a_{1}$ the solution converges to the periodic sequence -1,0,-1,0,...

As previously precised what is reported here is only a short introduction and the interested reader is recommended to consult specialized literature…

Kind regards

$\chi$ $\sigma$