1.  Introduction to Difference Equations

Given a function y = f(t), its first difference is defined as the difference between the value  of the  function when the  argument  assumes the value t + h, h 持 0,  and the value of the function corresponding to the value t of the argument. In symbols, Ay = f(t + h) 一 f(t). It should be noted that it is not important if whether the values run forwards  or  backwards,  namely  we  could  also  define  the  first  difference  of  the function as Ay = f(t) 一 f(t 一 h).

Without  any  loss  of generality  we  can  assume  unit  increments  of the  dependent variable, i.e. Ay = f(t + 1) 一 f(t) or equivalently Ay = f(t) 一 f(t 一 1).

If  we  consider  successive  equally  –  spaced  values  of  the  independent  variable (t + 1, t + 2, t + 3 … ) we can obtain successive first differences:

Ayt = f(t + 1) 一 f(t) = yt+1 一 yt

Ayt+1 = f(t + 2) 一 f(t + 1) = yt+2 一 yt+1

Ayt+2 = f(t + 3) 一 f(t + 2) = yt+3 一 yt+2

and  so  on.  We  can  also  compute  the  second  differences,  namely  the  sequence  of differences between two successive first differences:

A2yt = Ayt+1 一 Ayt = (yt+2 一 yt+1) 一 (yt+1 一 yt) = yt+2 一 2yt+1 + yt

and  so  on .  The  superscript   2 means  that  the  operation  of  the  computing  the difference has been repeated twice, i .e. that the difference operator A has been applied twice .

Proceeding   on   a   similar  way  we   could  compute  the   differences  between  two successive second differences and obtain the third differences and so on .

We  can  now  define  an  ordinary  difference  equation  as  a  functional  equation involving one or more of the differences Ayt,A2yt etc., of an unknown function of time. Since the argument t varies in a discontinuous way, taking on equally spaced values, it follows that our unknown function will be defined only corresponding to these values of t (i.e. the graph of the function will be succession of separate points).

We call that equation ordinary because the unknown function is only a function of one  argument.  When  the  partial  differences  of a  function  having  more  than  one argument are involved, the equation becomes a partial difference equation .

The order of a difference equation is that of the highest difference appearing in the equation.  If,  for  example, the  highest  difference  contained  is the  second, then  the equation   is   the   second   order;   note   that   the   equation   is   of  the   second   order independently of the fact that the lower – order differences are or are not contained in the equation.

Usually  we  find  the  difference  equation,  as  we  have  already  mentioned  above, expressed in terms of values of the function at different points of time . In that form, the order of an equation is given by the highest difference between time subscripts .

For instance the ordinary difference equation yt+2 一 2yt = b is a difference equation of a second order, as the highest difference between the time subscripts is 2.

Theorem A

The general solution of a difference equation of order n is a function of t involving exactly n arbitrary constants.

1.1.The Homogeneous Equation

Definition

A  difference  equation  is  called  homogeneous  when  the  following  Theorem  B  is satisfied for any A.

Theorem B

If y1(t) is a solution of the homogeneous equation, then Ay1(t), where A is an arbitrary constant, is also a solution.

Theorem C

If y1(t),y2(t) are two distinct (i.e. linearly independent) solutions of the homogeneous equation (n 持 1),    then    A1y1(t) + A2y2(t)  is    also    a    solution   for    any    two constants A1,A2.

1.2.The Non – Homogeneous Equation

Theorem D

If  t is any particular solution of the non – homogeneous equation, the general solution of the same  equation  is  obtained adding   t to  the general solution  of  the  corresponding homogeneous equation, namely

y(t) = t + f(t;A1,A2, … ,An)

is the general solution of the non – homogeneous equation.

Thus the general solution of the homogeneous equation is only a part of the general solution of the non – homogeneous equation, and so it is not “general” with respect to  the  latter.  This  means  that  the  expression  “general  solution”  must  always  be qualified. As a matter of terminology note that the expression “particular solution” is  used:  in  the  sense  of a  solution  obtained  from  the  general  solution  by  giving specific values to the arbitrary constants and in the sense of any single non – general solution of the homogeneous equation. The expression  “complementary function” is   used   to   indicate   the   general   solution   of  the   homogeneous   equation   when considered as a part of the general solution of the non – homogeneous equation.

1.3.Method for solving non – homogeneous equations

I . Find a particular solution t of the non – homogenous equation.

II . Put g(t) 三 0 and solve the resulting homogeneous equation.

III . Add the two results.

The particular solution of the non – homogeneous equation will depend on the form of the known function g(t).

2.   The Method of Undetermined Coefficients

The  method  of  undetermined  coefficients  is  extremely  useful  for  solving  linear models in economics. That method suggests the following general approach: to find a particular  solution  of the non – homogeneous  equation, try  a  function having the same form of 6)?( but with undetermined constants (i.e. if 6)?( is a constant, try an undetermined  constant;  if it  is  an  exponential  function,  try  the  same  exponential function with  an undetermined multiplicative  constant,  and  so  on).  Substitute this function, in the non –homogeneous equation and determine the coefficients so that the equation to be satisfied.

The above described method is called the method of undetermined coefficients. In general to apply that method first guess the form of the solution and then verify the guess and solve the undetermined coefficients.

2.1.Example using the Method of Undetermined Coefficients

Polynomial Guess

Solve 人才+t 一 S人才 = t? + Z subject to 人0 = 0.

First we solve the Homogenous Equation (H.E .) which is as follows:

Let  人才 = Y才 丰 0 which  is  a  non  –  trivial  solution  and  then  substitute  into  the Homogeneous Equation.

人才+t 一 S人才 = 0 一

Y才+t 一 SY才 = 0 一

Y才 )Y 一 S( = 0 一

Y = S

Hence the solution of the H.E. i.e. the complementary function equals: 人才(o) = VY才 = VS才

In  the  second  step  we  will  solve  the  Non  –  Homogeneous  Equation  (N.H.E)  by guessing a solution in the form of a first order polynomial guess function in ?. (Why we do so?? Because the non – homogenous part of our equation is of this form) .

人才 = D? + q Dup 人才+t = D)? + t( + q

Substitute  now  the  above  relations  into  our  first  order  difference  equation  and  it follows that:

yt+1 一 5yt = 3t + 2 一

[a(t + 1) + b] 一 5(at + b) = 3t + 2 一

at + a + b 一 5at 一 5b = 3t + 2 一

一4at 一 4b + a = 3t + 2 一

(一4a)t + (a 一 4b) = 3t + 2.

Now we have to equate the coefficients from both sides which yield a linear system in two unknown parameters, which are the so called undetermined coefficients.

(a一4一) 一 (a = 一)

Therefore, the solution of the N.H.E., i.e. the particular solution (P .S.), equals:

t = 一  t 一 

The General Solution (G.S.) equals to the sum of the C.F . and the P.S. and it is as follows:

yt = yt(c) + t 一

yt = A5t 一  t 一 

We can also use the initial condition in order to determine the arbitrary constant A in the G.S., and that will be as follows:

y0 = 0 = A50 一  0 一  一 0 = A 一  一 A =

Therefore the G.S. equals

yt =  5t 一  t 一  Vt

Homework

   You could try to solve yt+1 一 3yt = 4t subject to y0 = 0. Hint: Use an

exponential guess function and follow the method.

There also other methods that you could apply to solve Difference Equations of first or higher order. Such methods are the Method of Lag Operators and the Method of Forward or Backward Substitution (depending on the nature of the variable, if they are forward or backward looking).

3.  Discrete Time Dynamic Programming

In   mathematics,   computer   science,   economics   and   other   sciences,   Dynamic Programming is a method for solving complex problems by breaking them down into simpler   subproblems.   It   is   applicable   to  problems   exhibiting  the  properties   of overlapping    subproblems    and    optimal    substructure.    Dynamic    programming algorithms are used for optimization.

The  term  Dynamic  Programming  was  originally  used  in  the   1940s  by  Richard Bellman to describe the process of solving problems where one needs to find the best decisions sequentially . The word dynamic was chosen by Bellman to capture the time – varying aspect of the problems. The word programming referred to the use of the method to find an optimal program.

Dynamic Programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler subproblems in a recursive manner. While  some decision problems cannot be taken apart this way, decisions that span several points in  time  do  often  break  apart  recursively;  Bellman  called  this  the  “Principle  of Optimality” . If subproblems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the subproblems. In the optimization literature this relationship is called the Bellman equation .

In terms of mathematical optimization , dynamic programming refers to simplifying a decision by breaking it down into a sequence of decisions steps over time. That is done  by  defining  a  sequence  of value  functions V1, V2, … Vn,  with  an  argument  y representing the state of the system at times i e [1,n]. The definition of Vn(y) is the value obtained in state y at the last time n. The values at earlier times can be found by working backwards, using a recursive relationship called the Bellman equation .

The  method  of  Dynamic  Programming  is  best  understood  by  studying  finite  – horizon problems first. These problems are often encountered in making life – cycle planning decisions  on  optimal  consumption, savings, portfolio choice  etc. Below we are going to present a motivation example.

3.1.Application in Dynamic Programming

Problem

Suppose that there is a consumer who lives over the periods t = 0, 1, 2, … T and must decide how much to consume and how much to save in each period.

Let   ct denote the consumption in period t and assume that consumer derives utility from  consuming which  is given by the following utility  function u(ct) = ln(ct) as long as the consumer lives.

Assume also that the consumer discounts the future utility by a factor  b (shows the degree of impatience of the consumer) each period, where 0 想 b 想 1.

Let wt be an asset in period t. Assume that the initial value of the asset w0 > 0 and suppose  that  this  period  asset  and  consumption  determine  next  period’s  asset  as follows:

wt+1 = wt 一 ct

Assume also that this asset cannot be negative and that wT 三 0.

Answer the following questions .

1.   Formulate and write explicitly the dynamic consumer’s decision problem.

2.   Apply   the   Method   of  Dynamic   Programming   and   formulate   the   Bellman Equation.

3.   Solve the problem applying the Method of Undetermined Coefficients .

Hint: Try the guess function  of the  form  Vt (wt) = A + Bln(wt) and  determine coefficients A, B.