Chapter 11. Recurrences

The recursive definition of the Fibonacci numbers is well-known: if is the Fibonacci number then

We are interested in an explicit form of the numbers for all natural numbers . Actually, the problem is to solve an equation where the unknown is given recursively, in which case the equation is called a recurrence equation. The solution can be considered as a function over natural numbers, because is defined for all . Such recurrence equations are also known as difference equations, but could be named as discrete differential equations for their similarities to differential equations.

Definition 11.1 A k order recurrence equation is an equation of the form

where has to be given in an explicit form.

For a unique determination of , initial values must be given. Usually these values are . These can be considered as initial conditions. In case of the equation for Fibonacci-numbers, which is of second order, two initial values must be given.

A sequence satisfying equation (11.1) and the corresponding initial conditions is called a particular solution. If all particular solutions of equation (11.1) can be obtained from the sequence , by adequately choosing of the constants , then this sequence is a general solution.

Solving recurrence equations is not an easy task. In this chapter we will discuss methods which can be used in special cases. For simplicity of writing we will use the notation instead of as it appears in several books (sequences can be considered as functions over natural numbers).

The chapter is divided into three sections. In Section 11.1 we deal with solving linear recurrence equations, in Section 11.2 with generating functions and their use in solving recurrence equations and in Section 11.3 we focus our attention on the numerical solution of recurrence equations.

11.1. 11.1 Linear recurrence equations

If the recurrence equation is of the form

where are functions defined over natural numbers, , and has to be given explicitly, then the recurrence equation is linear. If is the zero function, then the equation is homogeneous, otherwise nonhomogeneous. If all the functions are constant, the equation is called a linear recurrence equation with constant coefficients.

11.1.1. 11.1.1 Linear homogeneous equations with constant coefficients

Let the equation be

where are real constants, . If initial conditions are given (usually ), then the general solution of this equation can be uniquely given.

To solve the equation let us consider its characteristic equation

a polynomial equation with real coefficients. This equation has roots in the field of complex numbers. It can easily be seen after a simple substitution that if is a real solution of the characteristic equation, then is a solution of (11.2), for arbitrary .

The general solution of equation (11.2) is

where () are the linearly independent solutions of equation (11.2). The constants can be determined from the initial conditions by solving a system of equations.

The linearly independent solutions are supplied by the roots of the characteristic equation in the following way. A fundamental solution of equation (11.2) can be associated with each root of the characteristic equation. Let us consider the following cases.

Distinct real roots. Let be distinct real roots of the characteristic equation. Then

are solutions of equation (11.2), and

is also a solution, for arbitrary constants . If , then (11.4) is the general solution of the recurrence equation.

Example 11.1 Solve the recurrence equation

The corresponding characteristic equation is

with the solutions

These are distinct real solutions, so the general solution of the equation is

The constants and can be determined using the initial conditions. From , the following system of equations can be obtained.

The solution of this system of equations is . Therefore the general solution is

which is the th Fibonacci number .

Multiple real roots. Let be a real root of the characteristic equation with multiplicity . Then

are solutions of equation (11.2) (fundamental solutions corresponding to ), and

is also a solution, for any constants . If the characteristic equation has no other solutions, then (11.5) is a general solution of the recurrence equation.

Example 11.2 Solve the recurrence equation

The characteristic equation is

with a solution with multiplicity 2. Then

is a general solution of the recurrence equation.

From the initial conditions we have

From this system of equations , so the general solution is

Distinct complex roots. If the complex number , written in trigonometric form, is a root of the characteristic equation, then its conjugate is also a root, because the coefficients of the characteristic equation are real numbers. Then

are solutions of equation (11.2) and

is also a solution, for any constants and . If these are the only solutions of a second order characteristic equation, then (11.6) is a general solution.

Example 11.3 Solve the recurrence equation

The corresponding characteristic equation is

with roots and . These can be written in trigonometric form as and . Therefore

is a general solution of the recurrence equation. From the initial conditions

Therefore . Hence the general solution is

Multiple complex roots. If the complex number written in trigonometric form as is a root of the characteristic equation with multiplicity , then its conjugate is also a root with multiplicity . Then

and

are solutions of the recurrence equation (11.2). Then

is also a solution, where are arbitrary constants, which can be determined from the initial conditions. This solution is general if the characteristic equation has no other roots.

Example 11.4 Solve the recurrence equation

The characteristic equation is

which can be written as . The complex numbers and are double roots. The trigonometric form of these are

respectively. Therefore the general solution is

From the initial conditions we obtain

that is

Solving this system of equations , , and . Thus the general solution is

Using these four cases all linear homogeneous equations with constant coefficients can be solved, if we can solve their characteristic equations.

Example 11.5 Solve the recurrence equation

The characteristic equation is

with roots 2, and . Therefore the general solution is

After determining the constants we obtain

The general solution. The characteristic equation of the th order linear homogeneous equation (11.2) has roots in the field of complex numbers, which are not necessarily distinct. Let these roots be the following:

real, with multiplicity (),

real, with multiplicity (),

real, with multiplicity (), complex, with multiplicity (),

complex, with multiplicity (),

complex, with multiplicity ().

Since the equation has roots, .

In this case the general solution of equation (11.2) is

where

are constants, which can be determined from the initial conditions.

The above statements can be summarised in the following theorem.

Theorem 11.2 Let be an integer and real numbers with . The general solution of the linear recurrence equation (11.2) can be obtained as a linear combination of the terms , where are the roots of the characteristic equation (11.3) with multiplicity () and the coefficients of the linear combination depend on the initial conditions.

The proof of the theorem is left to the Reader (see Exercise 11.1-5).

The algorithm for the general solution is the following.

Linear-Homogeneous

  1  determine the characteristic equation of the recurrence equation   2  find all roots of the characteristic equation with their multiplicities   3  find the general solution (11.7) based on the roots   4  determine the constants of (11.7) using the initial conditions, if these exists. 

11.1.2. 11.1.2 Linear nonhomogeneous recurrence equations

Consider the linear nonhomogeneous recurrence equation with constant coefficients

where are real constants, , and is not the zero function.

The corresponding linear homogeneous equation (11.2) can be solved using Theorem 11.2. If a particular solution of equation (11.8) is known, then equation (11.8) can be solved.

Theorem 11.3 Let be an integer, real numbers, . If is a particular solution of the linear nonhomogeneous equation (11.8) and is a general solution of the linear homogeneous equation (11.2), then

is a general solution of the equation (11.8).

The proof of the theorem is left to the Reader (see Exercise 11.1-6).

Example 11.6 Solve the recurrence equation

First we solve the homogeneous equation

and obtain the general solution

since the roots of the characteristic equation are and 1. It is easy to see that

is a solution of the nonhomogeneous equation. Therefore the general solution is

The constants and can be determined using the initial conditions. Thus,

A particular solution can be obtained using the method of variation of constants. However, there are cases when there is an easier way of finding a particular solution. In Figure 11.1 we can see types of functions , for which a particular solution can be obtained in the given form in the table. The constants can be obtained by substitutions.

Figure 11.1.  The form of particular solutions.

The form of particular solutions.


In the previous example , so the first case can be used with and . Therefore we try to find a particular solution of the form . After substitution we obtain , thus the particular solution is

Exercises

11.1-1 Solve the recurrence equation

(Here is the optimal number of moves in the problem of the Towers of Hanoi.)

11.1-2 Analyse the problem of the Towers of Hanoi if discs have to be moved from stick to stick in such a way that no disc can be moved directly from to and vice versa.

Hint. Show that if the optimal number of moves is denoted by , and , then .

11.1-3 Solve the recurrence equation

11.1-4 Solve the linear nonhomogeneous recurrence equation

Hint. Try to find a particular solution of the form .

11.1-5 Prove Theorem 11.2.

11.1-6 Prove Theorem 11.3.