The file RecurrenceEquations.mth defines functions for finding exact solutions of first and second order difference equations and of linear-geometric recurrence equations.  The function definitions in the file are automatically loaded when any of its functions are first used.


LIN1_DIFFERENCE(p, q, x, x0, y0) simplifies to a specific solution of a recurrence equation having the form

y(x+1) = p(x)·y(x) + q(x)

for the initial condition y=y0 at x=x0.  Note that linear first order difference equations can always be put in this form.  For a general instead of a specific solution, make x0 and y0 unassigned variables.  A convenient way to do this is to give LIN1_DIFFERENCE only three arguments.


For example, to solve the difference equation  y(m+1) = m·y(m) + (m+1)!  for the initial condition y=2 at x=1, enter and simplify the expression

LIN1_DIFFERENCE(m, (m+1)!, m, 1, 2)

to produce the algebraic solution

⎡  2           ⎤          
⎢ m      m     ⎥          
⎢———— + ——— + 1⎥·(m - 1)! 
⎣  2     2     ⎦          


To verify that it satisfies the initial condition, substitute m=1 into the solution, and see that it simplifies to 2.  To verify that it satisfies the difference equation  y(m+1) = m·y(m) + (m+1)! , substitute m+1 for m in the above solution, and see that that result equals m times the solution plus (m+1)! .  Note that the best way to check that two dissimilar looking expressions are actually equal is to subtract one from the other and see if the result is 0.


The result of LIN1_DIFFERENCE may contain products or sums that Derive could not simplify to a closed-form.  A closed-form solution for all x > x0 may not even exist in terms of Derive's built-in defined functions.  However:


RECURRENCE1(r, x, y, x0, y0, n) simplifies to the matrix

[[x0,  y0],  [x0+1,  y(x0+1)],  ...,  [x0+n,  y(x0+n)]]

where y satisfies the (perhaps nonlinear) first order difference equation  y(x+1) = r(x, y(x)).  Here y(x) should be represented by a variable y rather than a function in expression r.  Depending on r and your goal, it may be more appropriate to approximate rather than simplify when using RECURRENCE1.  Either way, you can then plot the resulting two-column matrix.


GEOMETRIC1(k, p, q, x, x0, y0) simplifies to a solution of the first order linear-geometric recurrence equation y(k·x) = p(x)·y(x) + q(x), where k is a particular number, such as 2 or 3.  The complexity analysis of "divide and conquer" algorithms often entails a linear-geometric recurrence equation.


CLAIRAUT_DIF(p, q, d, x, y, c) simplifies to an implicit algebraic general solution of the equation p(y-x·d) = q(d), where variable y represents y(x) and variable d represents the forward first difference y(x+1) - y(x).  This solution is in terms of x and a symbolic arbitrary constant c.  For example, to find a general solution of the difference equation

(y(x+1) - x·(y(x+1) - y(x)))² = (y(x+1) - y(x))²

enter and simplify the expression

CLAIRAUT_DIF((y - x·d)^2, d^2)

to give

 2  2              2    2     
c ·x  - 2·c·x·y + y  - c  = 0 


LIN2_CCF(p, q, r, x, c1, c2) simplifies to a general solution of the constant coefficient second order linear difference equation y(x+2) + p·y(x+1) + q·y(x) = r(x), in terms of two symbolic constants c1 and c2.  Note that the result may contain one or more sums for which Derive can not find a closed-form.


LIN2_CCF_BV(p, q, r, x, x0, y0, x2, y2,) is similar to LIN2_CCF, but simplifies to a specific solution that satisfies the boundary conditions y=y0 at x=x0 and y=y2 at x=x2.


Other Utility File LibraryG5BS2R 

Created with the Personal Edition of HelpNDoc: Free HTML Help documentation generator