Return to computing page for the first course APMA0330
Return to computing page for the second course APMA0340
Return to Mathematica tutorial for the first course APMA0330
Return to Mathematica tutorial for the second course APMA0340
Return to the main page for the course APMA0330
Return to the main page for the course APMA0340
Our object of interest is a sequence (either finite or infinite) of numbers rather than continuous functions. Generally speaking, a sequence is a particular example of a piecewise function that has constant value during some fixed interval. Traditionally, a sequence is denoted by \( {\bf a} = \left\{ a_n \right\}_{n \ge 0} = \left\{ a_0 , a_1 , a_2 , \ldots \right\} \) or simply { a_{n} }. We will consider sequences where the index runs from zero to infinity (or some finite number. However, there are known cases when context requires sequences with subscripts from minus infinity to infinity. More often than not, the elements of a sequence are defined implicitly via some equation.
A recurrence or recurrence relation is an equation that relates different members of a sequence of numbers \( {\bf a} = \left\{ a_n \right\}_{n \ge 0} = \left\{ a_0 , a_1 , a_2 , \ldots \right\} , \) where a_{n} are the values to be determined. A solution of a recurrence is any sequence that satisfies the recurrence throughout its range.
The order of a recurrence relation is the difference between the largest and smallest subscripts of the members of the sequence that appear in the equation. The general form of a recurrence relation of order p is
\( a_n = f(n, a_{n-1} , a_{n-2} , \ldots , a_{n-p}) \) for some function f. A recurrence of a finite order is usually referred to as a difference equation. A full history recurrence is one that depends on all the previous functions.
Our primary interest in recurrences comes from two sources: discretization of differential equations and representation of their solutions in the form of infinite series. Since computers love recurrences, computer science and numerical analysis courses cover this topic in more detail and from different prospective than we do (and need). Now it is right time to classify recurrences further and give some examples.
If in the difference equation \( x_n = f\left( n, x_{n-1} , x_{n-2} , \ldots , x_{n-p} \right) \) of order p, the function f is linear in all its arguments, then the equation is called linear. The first and second order linear difference equations have the following form:
\( a_n x_n + b_n x_{n-1} = f_n \) first order linear equation,
\( a_n x_n + b_n x_{n-1} + c_n x_{n-2} = f_n \) second order linear equation,
where {f_{n}}, {a_{n}}, {b_{n}}, and {c_{n}} are given (known) sequences. When all members of these sequences except {f_{n}} do not depend on n, the difference equation is said to have constant coefficients; otherwise, these difference equations are said to have variable coefficients.
The sequence {f_{n}} is called a nonhomogeneous sequence, or forcing/input sequence of the difference equation. If all elements of {f_{n}} are zero, then the linear difference equation is called a homogeneous equation; otherwise, we call it nonhomogeneous or inhomogeneous.
A difference equation usually has infinitely many solutions. In order to pin down a solution, we have to know one or more of its elements. If we have a difference equation of order p, we need to specify p sequential values of the sequence, called the initial conditions. Do, for first order recurrences, we have to specify only one element of the sequence {x_{n}}, say the first one x_{0}=a; for the second order difference equations we have to know two elements: x_{0}=a and x_{1}=b; and so forth. It should be noted that the unique solution of a recurrence may be specified by imposing restrictions other than initial conditions.
Recurrences, although a very tedious computation method by hand, is very simple to do in Mathematica. The best way to learn how to do recurrences in Mathematica are by examples, and a perfect example for this topic is the Fibonacci integer sequence.
Example:
We can define the Fibonacci recurrence (which is a second order difference equation \( F_{n+2} =
F_{n+1} + F_n , \quad F_0 = 0, \ F_1 =1 \) ) as
Another efficient way to define the Fibonacci recurrence is to use the explicit formula (which is not available for most
other nonlinear recurrences): `
For instance, imagine that we started with a single pair of male and female rabbits. If these rabbits and their descendants reproduced at top speed ("like bunnies") for 7777 years, without any deaths, we would have enough rabbits to cover the entire state of Rhode Island.
■
Example:
The number of Dyck words with n parenthesis pairs satisfies the full history recurrence:
Dyck words and language are named after the German mathematician Walther von Dyck.
■
There are known two basic methods to find a solution of homogeneous constant coefficient difference equation\( x_{n+p} = a_p x_{n+p-1} + a_{p-1} x_{n+p-2} + \cdots + a_1 x_n : \) test substitution \( x_{n} = r^n \) and method of generating functions. The former reduces the problem to a polynomial equation, called the characteristic equation, and the solution depends on its roots: whether they are real, multiple, or complex. The latter is more powerful and could be applied to nonhomogeneous equations as well. Till some extend, the generating function method resembles application of the Laplace transform for solving differential equations. We illustrate their applications in the following examples.
Example:
Consider a homogeneous second order difference equation subject to some initial conditions:
Here the first pair represents the coefficients of the difference equation of order 2; next pair tells Mathematica the first two initial values of the recurrence. The final number (10) is the number of terms the user wants to see as output. Another option:
So we get exactly the same answer for the first 10 terms in the required sequence. On the other hand, Mathematica has a special command to determine the general solution:
The algebraic equation \( r^2 -6r +1 =0 \) is called the characteristic equation for the given recurrence. Correspondingly, the polynomial \( r^2 -6r +1 \) is referred to as the characteristic polynomial. Since the characteristic equation has two distinct real roots
Solve[r^2 - 6*r + 1 == 0, r]
{{r -> 3 - 2 Sqrt[2]}, {r -> 3 + 2 Sqrt[2]}}
the general solution of the given difference equation of the second order is
where A and B are some constants to be determined. Substitution of the general form into the initial conditions yields
\[
y_0 = A+ B =1, \qquad y_1 = A\,\left( 3+2\sqrt{2} \right) + B \,\left( 3-2\sqrt{2} \right) =3 .
\]
This system of algebraic equations is easy to solve: \( A = B = \frac{1}{2} . \)
Now we apply the generating function method. Let Y(z) be the generating function for the (unknown) sequence y_{n}:
\[
Y(z) = \sum_{n\ge 0} y_n z^n .
\]
Multiplying both sides of the recurrence \( y_{n+2} = 6\,y_{n+1} - y_n \) by z^{n+2} and summing the results, we obtain
The characteristic polynomial of the given recurrence relation is \( r^3 -6\,r^2 +12\,r -8 = (r-2)^3 . \) So it has only one triple root (of multiplicity 3) r = 2. Now we seek the general solution in the form
The characteristic polynomial of the given recurrence relation is
\( r^2 -2r +10 =0, \) which has two complex conjugate roots: \( r = 1 \pm 3{\bf j} . \) We represent these wo roots in polar form:
Consider some population when its size is measured by possible fixed interval in time. Thus, we can describe the population size by a sequence { x_{n} }, with x_{0} denoting the initial population size, x_{1} the population size at the next generation measured at time t_{1}, x_{2} the population size at the next generation measured at time t_{2}, and so on. Usually the time interval between generations is taken to be a constant.
For example, suppose the population changes only through births and deaths, so
that x_{n+1} - x_{n} is the number of births minus the number of deaths over the time interval from t_{n} to t_{n+1}. Suppose further that the birth and death rates are constants b and d, respectively. Then
where r=1+b-d. This is the linear homogeneous difference equation of order 1. If initial population x_{0} is know, then population at any time t_{n} is: \( x_n = r^n x_0 . \)
Consider another recurrence that generates the Pell numbers:
Rivera-Figueroa, A. and Rivera-Rebolledo, J.M., A new method to solve the second-order linear difference equations with constant coefficients, International Journal of Mathematical Education in Science and Technology, Volume 47, 2016 - Issue 4, pp. 636--649. https://doi.org/10.1080/0020739X.2015.1091517
Tisdell, C.C., Critical perspectives of the ‘new’ difference equation solution method of Rivera-Figueroa and Rivera-Rebolledo, International Journal of Mathematical Education in Science and Technology, 2018, https://doi.org/10.1080/0020739X.2018.1469796
Return to the main page (APMA0330)
Return to the Part 1 (Plotting)
Return to the Part 2 (First Order ODEs)
Return to the Part 3 (Numerical Methods)
Return to the Part 4 (Second and Higher Order ODEs)
Return to the Part 5 (Series and Recurrences)
Return to the Part 6 (Laplace Transform)
Return to the Part 7 (Boundary Value Problems)