ads Recurrence Relations

Section 8.3 Recurrence Relations

In this section we will begin our study of recurrence relations and their solutions. Our primary focus will be on the class of finite order linear recurrence relations with constant coefficients (shortened to finite order linear relations). First, we will examine closed form expressions from which these relations arise. Second, we will present an algorithm for solving them. In later sections we will consider some other common relations (8.4) and introduce two additional tools for studying recurrence relations: generating functions (8.5) and matrix methods (Chapter 12).

🔗

Subsection 8.3.1 Definition and Terminology

🔗

Definition 8.3.1. Recurrence Relation.

🔗

Let

S

be a sequence of numbers. A recurrence relation on

S

is a formula that relates all but a finite number of terms of

S

to previous terms of

S .

That is, there is a

k_{0}

in the domain of

S

such that if

k \geq k_{0},

then

S (k)

is expressed in terms of some (and possibly all) of the terms that precede

S (k) .

If the domain of

S

{0, 1, 2, \dots},

the terms

S (0), S (1), . . ., S (k_{0} - 1)

are not defined by the recurrence formula. Their values are the initial conditions (or boundary conditions, or basis) that complete the definition of

S .

Example 8.3.2. Some Examples of Recurrence Relations.

The Fibonacci sequence is defined by the recurrence relation $F_{k} = F_{k - 2} + F_{k - 1},$ $k \geq 2,$ with the initial conditions $F_{0} = 1$ and $F_{1} = 1 .$ The recurrence relation is called a second-order relation because $F_{k}$ depends on the two previous terms of $F .$ Recall that the sequence $C$ in Section 8.2, Example 8.2.2, can be defined with the same recurrence relation, but with different initial conditions.
The relation $T (k) = 2 T (k - 1)^{2} - k T (k - 3)$ is a third-order recurrence relation. If values of $T (0),$ $T (1),$ and $T (2)$ are specified, then $T$ is completely defined.
The recurrence relation $S (n) = S (⌊ n / 2 ⌋) + 5,$ $n > 0,$ with $S (0) = 0$ has infinite order. To determine $S (n)$ when $n$ is even, you must go back $n / 2$ terms. Since $n / 2$ grows unbounded with $n,$ no finite order can be given to $S .$

🔗

Subsection 8.3.2 Solving Recurrence Relations

🔗

Sequences are often most easily defined with a recurrence relation; however, the calculation of terms by directly applying a recurrence relation can be time-consuming. The process of determining a closed form expression for the terms of a sequence from its recurrence relation is called solving the relation. There is no single technique or algorithm that can be used to solve all recurrence relations. In fact, some recurrence relations cannot be solved. The relation that defines

T

above is one such example. Most of the recurrence relations that you are likely to encounter in the future are classified as finite order linear recurrence relations with constant coefficients. This class is the one that we will spend most of our time with in this chapter.

🔗

Definition 8.3.3. $n^{t h}$ Order Linear Recurrence Relation.

🔗

Let

S

be a sequence of numbers with domain

k \geq 0 .

n^{th}

order linear recurrence relation on

S

with constant coefficients is a recurrence relation that can be written in the form

S (k) + C_{1} S (k - 1) + . . . + C_{n} S (k - n) = f (k) for k \geq n

🔗

where

C_{1}, C_{2}, \dots, C_{n}

are constants and

f

is a numeric function that is defined for

k \geq n .

🔗

Note: We will shorten the name of this class of relations to

n^{th}

order linear relations. Therefore, in further discussions,

S (k) + 2 k S (k - 1) = 0

would not be considered a first-order linear relation.

Example 8.3.4. Some Finite Order Linear Relations.

The Fibonacci sequence is defined by the second-order linear relation because $F_{k} - F_{k - 1} - F_{k - 2} = 0$
The relation $P (j) + 2 P (j - 3) = j^{2}$ is a third-order linear relation. In this case, $C_{1} = C_{2} = 0 .$
The relation $A (k) = 2 (A (k - 1) + k)$ can be written as $A (k) - 2 A (k - 1) = 2 k .$ Therefore, it is a first-order linear relation.

🔗

Subsection 8.3.3 Recurrence Relations Obtained from “Solutions”

🔗

Before giving an algorithm for solving finite order linear relations, we will examine recurrence relations that arise from certain closed form expressions. The closed form expressions are selected so that we will obtain finite order linear relations from them. This approach may seem a bit contrived, but if you were to write down a few simple algebraic expressions, chances are that most of them would be similar to the ones we are about to examine.

🔗

For our first example, consider

D,

defined by

D (k) = 5 \cdot 2^{k},

k \geq 0 .

k \geq 1,

D (k) = 5 \cdot 2^{k} = 2 \cdot 5 \cdot 2^{k - 1} = 2 D (k - 1) .

Therefore,

D

satisfies the first order linear relation

D (k) - 2 D (k - 1) = 0

and the initial condition

D (0) = 5

serves as an initial condition for

D .

🔗

As a second example, consider

C (k) = 3^{k - 1} + 2^{k + 1} + k

k \geq 0 .

Quite a bit more algebraic manipulation is required to get our result:

🔗

Table 8.3.5.

$C (k) = 3^{k - 1} + 2^{k + 1} + k$	$Original equation$
$3 C (k - 1) = 3^{k - 1} + 3 \cdot 2^{k} + 3 (k - 1)$	$Substitute k - 1 for k$
	$and multiply by 3$
	$Subtract the second equation$
	$from the first.$
$C (k) - 3 C (k - 1) = - 2^{k} - 2 k + 3$	$3^{k - 1} term is eliminated.$
	$This is a first order relation .$
$2 C (k - 1) - 6 C (k - 2) = - 2^{k} - 2 (2 (k - 1)) + 6$	$Substitute k - 1 for k in the$
	$third equation, multiply by 2 .$
	$Subtract the 4th equation from the 3rd.$
$C (k) - 5 C (k - 1) + 6 C (k - 2) = 2 k - 7$	$2^{k + 1} term is eliminated.$
	$This is 2nd order relation.$

🔗

The recurrence relation that we have just obtained, defined for

k \geq 2,

together with the initial conditions

C (0) = 7 / 3

and

C (1) = 6,

define

C .

🔗

Table 8.3.6 summarizes our results together with a few other examples that we will let the reader derive. Based on these results, we might conjecture that any closed form expression for a sequence that combines exponential expressions and polynomial expressions will be solutions of finite order linear relations. Not only is this true, but the converse is true: a finite order linear relation defines a closed form expression that is similar to the ones that were just examined. The only additional information that is needed is a set of initial conditions.

🔗

Table 8.3.6. Recurrence Relations Obtained from Given Sequences

Closed Form Expression	Recurrence Relation
$D (k) = 5 \cdot 2^{k}$	$D (k) - 2 D (k - 1) = 0$
$C (k) = 3^{k - 1} + 2^{k + 1} + k$	$C (k) - 2 C (k - 1) - 6 C (k - 2) = 2 k - 7$
$Q (k) = 2 k + 9$	$Q (k) - Q (k - 1) = 2$
$A (k) = k^{2} - k$	$A (k) - 2 A (k - 1) + A (k - 2) = 2$
$B (k) = 2 k^{2} + 1$	$B (k) - 2 B (k - 1) + B (k - 2) = 4$
$G (k) = 2 \cdot 4^{k} - 5 (- 3)^{k}$	$G (k) - G (k - 1) + 12 G (k - 2) = 0$
$J (k) = (3 + k) 2^{k}$	$J (k) - 4 J (k - 1) + 4 J (k - 2) = 0$

🔗

Definition 8.3.7. Homogeneous Recurrence Relation.

🔗

n^{t h}

order linear relation is homogeneous if

f (k) = 0

for all

k .

For each recurrence relation

S (k) + C_{1} S (k - 1) + \dots + C_{n} S (k - n) = f (k),

the associated homogeneous relation is

S (k) + C_{1} S (k - 1) + \dots + C_{n} S (k - n) = 0

Example 8.3.8. First Order Homogeneous Recurrence Relations.

D (k) - 2 D (k - 1) = 0

is a first-order homogeneous relation. Since it can also be written as

D (k) = 2 D (k - 1),

it should be no surprise that it arose from an expression that involves powers of 2. More generally, you would expect that the solution of

L (k) - a L (k - 1)

would involve

a^{k} .

Actually, the solution is

L (k) = L (0) a^{k},

where the value of

L (0)

is given by the initial condition.

Example 8.3.9. A Second Order Example.

Consider the second-order homogeneous relation

S (k) - 7 S (k - 1) + 12 S (k - 2) = 0

together with the initial conditions

S (0) = 4

and

S (1) = 4 .

From our discussion above, we can predict that the solution to this relation involves terms of the form

b a^{k},

where

b

and

a

are nonzero constants that must be determined. If the solution were to equal this quantity exactly, then

\begin{array}{ccc} S (k) = b a^{k} \\ S (k - 1) = b a^{k - 1} \\ S (k - 2) = b a^{k - 2} \end{array}

Substitute these expressions into the recurrence relation to get

b a^{k} - 7 b a^{k - 1} + 12 b a^{k - 2} = 0

Each term on the left-hand side of this equation has a factor of

b a^{k - 2},

which is nonzero. Dividing through by this common factor yields

\begin{matrix} (8.3.1) & a^{2} - 7 a + 12 = (a - 3) (a - 4) = 0 \end{matrix}

Therefore, the only possible values of

a

are 3 and 4. Equation (8.3.1) is called the characteristic equation of the recurrence relation. The fact is that our original recurrence relation is true for any sequence of the form

S (k) = b_{1} 3^{k} + b_{2} 4^{k},

where

b_{1}

and

b_{2}

are real numbers. This set of sequences is called the general solution of the recurrence relation. If we didn’t have initial conditions for

S,

we would stop here. The initial conditions make it possible for us to find definite values for

b_{1}

and

b_{2} .

{\begin{matrix} S (0) = 4 \\ S (1) = 4 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} 3^{0} + b_{2} 4^{0} = 4 \\ b_{1} 3^{1} + b_{2} 4^{1} = 4 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} + b_{2} = 4 \\ 3 b_{1} + 4 b_{2} = 4 \end{matrix}}

The solution of this set of simultaneous equations is

b_{1} = 12

and

b_{2} = - 8

and so the solution is

S (k) = 12 \cdot 3^{k} - 8 \cdot 4^{k} .

🔗

Definition 8.3.10. Characteristic Equation.

🔗

The characteristic equation of the homogeneous

n^{th}

order linear relation

S (k) + C_{1} S (k - 1) + \dots + C_{n} S (k - n) = 0

is the

n

th degree polynomial equation

a^{n} + \sum_{j = 1}^{n} C_{j} a^{n - j} = a^{n} + C_{1} a^{n - 1} + \dots + C_{n - 1} a + C_{n} = 0

🔗

The left-hand side of this equation is called the characteristic polynomial. The roots of the characteristic polynomial are called the characteristic roots of the equation.

Example 8.3.11. Some characteristic equations.

The characteristic equation of $F (k) - F (k - 1) - F (k - 2) = 0$ is $a^{2} - a - 1 = 0 .$
The characteristic equation of $Q (k) + 2 Q (k - 1) - 3 Q (k - 2) - 6 Q (k - 4) = 0$ is $a^{4} + 2 a^{3} - 3 a^{2} - 6 = 0.$ Note that the absence of a $Q (k - 3)$ term means that there is not an $x^{4 - 3} = x$ term appearing in the characteristic equation.

🔗

Algorithm 8.3.12. Algorithm for Solving Homogeneous Finite Order Linear Relations.

🔗

Write out the characteristic equation of the relation $S (k) + C_{1} S (k - 1) + \dots + C_{n} S (k - n) = 0,$ which is $a^{n} + C_{1} a^{n - 1} + \dots + C_{n - 1} a + C_{n} = 0 .$
Find all roots of the characteristic equation, the characteristic roots.
If there are $n$ distinct characteristic roots, $a_{1}, a_{2}, \dots a_{n},$ then the general solution of the recurrence relation is $S (k) = b_{1} a_{1}^{k} + b_{2} a_{2}^{k} + \dots + b_{n} a_{n}^{k} .$ If there are fewer than $n$ characteristic roots, then at least one root is a multiple root. If $a_{j}$ is a double root, then the $b_{j} a_{j}^{k}$ term is replaced with $(b_{j, 0} + b_{j, 1} k) a_{j}^{k} .$ In general, if $a_{j}$ is a root of multiplicity $p,$ then the $b_{j} a_{j}^{k}$ term is replaced with $(b_{j, 0} + b_{j, 1} k + \dots + b_{j, (p - 1)} k^{p - 1}) a_{j}^{k} .$
If $n$ initial conditions are given, we get $n$ linear equations in $n$ unknowns (the ${b_{j}}^{'} s$ from Step 3) by substitution. If possible, solve these equations to determine a final form for $S (k) .$

🔗

Although this algorithm is valid for all values of

n,

there are limits to the size of

n

for which the algorithm is feasible. Using just a pencil and paper, we can always solve second-order equations. The quadratic formula for the roots of

a x^{2} + b x + c = 0

x = \frac{- b \pm \sqrt{b^{2} - 4 a c}}{2 a}

🔗

The solutions of

a^{2} + C_{1} a + C_{2} = 0

are then

\frac{1}{2} (- C_{1} + \sqrt{C_{1}^{2} - 4 C_{2}}) and \frac{1}{2} (- C_{1} - \sqrt{C_{1}^{2} - 4 C_{2}})

🔗

Although cubic and quartic formulas exist, they are too lengthy to introduce here. For this reason, the only higher-order relations (

n \geq 3

) that you could be expected to solve by hand are ones for which there is an easy factorization of the characteristic polynomial.

Example 8.3.13. A solution using the algorithm.

Suppose that

T

is defined by

T (k) = 7 T (k - 1) - 10 T (k - 2),

with

T (0) = 4

and

T (1) = 17 .

We can solve this recurrence relation with Algorithm 8.3.12:

Note that we have written the recurrence relation in “nonstandard” form. To avoid errors in this easy step, you might consider a rearrangement of the equation to, in this case, $T (k) - 7 T (k - 1) + 10 T (k - 2) = 0 .$ Therefore, the characteristic equation is $a^{2} - 7 a + 10 = 0 .$
The characteristic roots are $\frac{1}{2} (7 + \sqrt{49 - 40}) = 5$ and $\frac{1}{2} (7 - \sqrt{49 - 40}) = 2 .$ These roots can be just as easily obtained by factoring the characteristic polynomial into $(a - 5) (a - 2) .$
The general solution of the recurrence relation is $T (k) = b_{1} 2^{k} + b_{2} 5^{k} .$
${\begin{matrix} T (0) = 4 \\ T (1) = 17 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} 2^{0} + b_{2} 5^{0} = 4 \\ b_{1} 2^{1} + b_{2} 5^{1} = 17 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} + b_{2} = 4 \\ 2 b_{1} + 5 b_{2} = 17 \end{matrix}}$ The simultaneous equations have the solution $b_{1} = 1$ and $b_{2} = 3 .$ Therefore, $T (k) = 2^{k} + 3 \cdot 5^{k} .$

🔗

Here is one rule that might come in handy: If the coefficients of the characteristic polynomial are all integers, with the constant term equal to

m,

then the only possible rational characteristic roots are divisors of

m

(both positive and negative).

🔗

With the aid of a computer (or possibly only a calculator), we can increase

n .

Approximations of the characteristic roots can be obtained by any of several well-known methods, some of which are part of standard software packages. There is no general rule that specifies the values of

n

for which numerical approximations will be feasible. The accuracy that you get will depend on the relation that you try to solve. (See Exercise 17 of this section.)

Example 8.3.14. Solution of a Third Order Recurrence Relation.

Solve

S (k) - 7 S (k - 2) + 6 S (k - 3) = 0,

where

S (0) = 8,

S (1) = 6,

and

S (2) = 22 .

The characteristic equation is $a^{3} - 7 a + 6 = 0 .$
The only rational roots that we can attempt are $\pm 1, \pm 2, \pm 3, and \pm 6 .$ By checking these, we obtain the three roots 1, 2, and $- 3 .$
The general solution is $S (k) = b_{1} 1^{k} + b_{2} 2^{k} + b_{3} (- 3)^{k} .$ The first term can simply be written $b_{1}$ .
${\begin{matrix} S (0) = 8 \\ S (1) = 6 \\ S (2) = 22 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} + b_{2} + b_{3} = 8 \\ b_{1} + 2 b_{2} - 3 b_{3} = 6 \\ b_{1} + 4 b_{2} + 9 b_{3} = 22 \end{matrix}}$ You can solve this system by elimination to obtain $b_{1} = 5,$ $b_{2} = 2,$ and $b_{3} = 1 .$ Therefore, $S (k) = 5 + 2 \cdot 2^{k} + (- 3)^{k} = 5 + 2^{k + 1} + (- 3)^{k}$

Example 8.3.15. Solution with a Double Characteristic Root.

Solve

D (k) - 8 D (k - 1) + 16 D (k - 2) = 0,

where

D (2) = 16

and

D (3) = 80 .

Characteristic equation: $a^{2} - 8 a + 16 = 0 .$
$a^{2} - 8 a + 16 = (a - 4)^{2} .$ Therefore, there is a double characteristic root, 4.
General solution: $D (k) = (b_{1, 0} + b_{1, 1} k) 4^{k} .$
$\begin{aligned} {\begin{array}{c} D (2) = 16 \\ D (3) = 80 \end{array}} & \Rightarrow {\begin{array}{c} (b_{1, 0} + b_{1, 1} 2) 4^{2} = 16 \\ (b_{1, 0} + b_{1, 1} 3) 4^{3} = 80 \end{array}} \\ \Rightarrow {\begin{array}{c} 16 b_{1, 0} + 32 b_{1, 1} = 16 \\ 64 b_{1, 0} + 192 b_{1, 1} = 80 \end{array}} \Rightarrow {\begin{array}{c} b_{1, 0} = \frac{1}{2} \\ b_{1, 1} = \frac{1}{4} \end{array}} \end{aligned}$

Therefore $D (k) = (1 / 2 + (1 / 4) k) 4^{k} = (2 + k) 4^{k - 1} .$

🔗

Subsection 8.3.4 Solution of Nonhomogeneous Finite Order Linear Relations

🔗

Our algorithm for nonhomogeneous relations will not be as complete as for the homogeneous case. This is due to the fact that different right-hand sides (

f (k)

’s) call for different rules in obtaining a particular solution.

🔗

Algorithm 8.3.16. Algorithm for Solving Nonhomogeneous Finite Order Linear Relations.

🔗

To solve the recurrence relation

S (k) + C_{1} S (k - 1) + \dots + C_{n} S (k - n) = f (k)

🔗

Write the associated homogeneous relation and find its general solution (Steps (a) through (c) of Algorithm 8.3.12). Call this the homogeneous solution, $S^{(h)} (k) .$
Start to obtain what is called a particular solution, $S^{(p)} (k)$ of the recurrence relation by taking an educated guess at the form of a particular solution. For a large class of right-hand sides, this is not really a guess, since the particular solution is often the same type of function as $f (k)$ (see Table 8.3.17).
Substitute your guess from Step 2 into the recurrence relation. If you made a good guess, you should be able to determine the unknown coefficients of your guess. If you made a wrong guess, it should be apparent from the result of this substitution, so go back to Step 2.
The general solution of the recurrence relation is the sum of the homogeneous and particular solutions. If no conditions are given, then you are finished. If $n$ initial conditions are given, they will translate to $n$ linear equations in $n$ unknowns and solve the system to get a complete solution.

🔗

Table 8.3.17. Particular solutions for given right-hand sides

Right Hand Side, $f (k)$	Form of Particular Solution, $S^{(p)} (k)$
Constant, $q$	Constant, $d$
Linear Function, $q_{0} + q_{1} k$	Linear Function, $d_{0} + d_{1} k$
$m^{t h}$ degree polynomial, $q_{0} + q_{1} k + \dots + q_{m} k^{m}$	$m^{t h}$ degree polynomial, $d_{0} + d_{1} k + \dots + d_{m} k^{m}$
exponential function, $q a^{k}$	exponential function, $d a^{k}$

Example 8.3.18. Solution of a Nonhomogeneous First Order Recurrence Relation.

Solve

S (k) + 5 S (k - 1) = 9,

with

S (0) = 6 .

The associated homogeneous relation, $S (k) + 5 S (k - 1) = 0$ has the characteristic equation $a + 5 = 0;$ therefore, $a = - 5 .$ The homogeneous solution is $S^{(h)} (k) = b (- 5)^{k} .$
Since the right-hand side is a constant, we guess that the particular solution will be a constant, $d .$
If we substitute $S^{(p)} (k) = d$ into the recurrence relation, we get $d + 5 d = 9,$ or $6 d = 9 .$ Therefore, $S^{(p)} (k) = 1.5 .$
The general solution of the recurrence relation is $S (k) = S^{(h)} (k) + S^{(p)} (k) = b (- 5)^{k} + 1.5$ The initial condition will give us one equation to solve in order to determine $b .$ $S (0) = 6 \Rightarrow b (- 5)^{0} + 1.5 = 6 \Rightarrow b + 1.5 = 6$ Therefore, $b = 4.5$ and $S (k) = 4.5 (- 5)^{k} + 1.5 .$

Example 8.3.19. Solution of a Nonhomogeneous Second Order Recurrence Relation.

Consider

T (k) - 7 T (k - 1) + 10 T (k - 2) = 6 + 8 k

with

T (0) = 1

and

T (1) = 2 .

From Example 8.3.13, we know that $T^{(h)} (k) = b_{1} 2^{k} + b_{2} 5^{k} .$ Caution:Don’t apply the initial conditions to $T^{(h)}$ until you add $T^{(p)}!$
Since the right-hand side is a linear polynomial, $T^{(p)}$ is linear; that is, $T^{(p)} (k) = d_{0} + d_{1} k .$
Substitution into the recurrence relation yields: $(d_{0} + d_{1} k) - 7 (d_{0} + d_{1} (k - 1)) + 10 (d_{0} + d_{1} (k - 2)) = 6 + 8 k$ $\Rightarrow (4 d_{0} - 13 d_{1}) + (4 d_{1}) k = 6 + 8 k$ Two polynomials are equal only if their coefficients are equal. Therefore, ${\begin{matrix} 4 d_{0} - 13 d_{1} = 6 \\ 4 d_{1} = 8 \end{matrix}} \Rightarrow {\begin{matrix} d_{0} = 8 \\ d_{1} = 2 \end{matrix}}$
Use the general solution $T (k) = b_{1} 2^{k} + b_{2} 5^{k} + 8 + 2 k$ and the initial conditions to get a final solution: ${\begin{matrix} T (0) = 1 \\ T (1) = 2 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} + b_{2} + 8 = 1 \\ 2 b_{1} + 5 b_{2} + 10 = 2 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} + b_{2} = - 7 \\ 2 b_{1} + 5 b_{2} = - 8 \end{matrix}} \Rightarrow {\begin{matrix} b_{1} = - 9 \\ b_{2} = 2 \end{matrix}}$

Therefore, $T (k) = - 9 \cdot 2^{k} + 2 \cdot 5^{k} + 8 + 2 k .$

🔗

Note 8.3.20. A quick note on interest rates.

🔗

When a quantity, such as a savings account balance, is increased by some fixed percent, it is most easily computed with a multiplier. In the case of an

8 %

increase, the multiplier is 1.08 because any original amount

A,

has

0.08 A

added to it, so that the new balance is

A + 0.08 A = (1 + 0.08) A = 1.08 A .

🔗

Another example is that if the interest rate is

3.5 %,

the multiplier would be 1.035. This presumes that the interest is applied at the end of year for

3.5 %

annual interest, often called simple interest. If the interest is applied monthly, and we assume a simplifed case where each month has the same length, the multiplier after every month would be

(1 + \frac{0.035}{12}) \approx 1.00292 .

After a year passes, this multiplier would be applied 12 times, which is the same as multiplying by

{1.00292}^{12} \approx 1.03557 .

That increase from 1.035 to 1.03557 is the effect of compound interest.

Example 8.3.21. A Sort of Annuity.

Suppose you open a savings account that pays an annual interest rate of

8 % .

In addition, suppose you decide to deposit one dollar when you open the account, and you intend to double your deposit each year. Let

B (k)

be your balance after

k

years.

B

can be described by the relation

B (k) = 1.08 B (k - 1) + 2^{k},

with

S (0) = 1 .

If, instead of doubling the deposit each year, you deposited a constant amount,

q,

the

2^{k}

term would be replaced with

q .

A sequence of regular deposits such as this is called a simple annuity.

Returning to the original situation,

$B^{(h)} (k) = b_{1} (1.08)^{k}$
$B^{(p)} (k)$ should be of the form $d 2^{k} .$
$\begin{aligned} d 2^{k} = 1.08 d 2^{k - 1} + 2^{k} & \Rightarrow (2 d) 2^{k - 1} = 1.08 d 2^{k - 1} + 2 \cdot 2^{k - 1} \\ \Rightarrow 2 d = 1.08 d + 2 \\ \Rightarrow .92 d = 2 \\ \Rightarrow d = 2.174 to the nearest thousandth) \end{aligned}$

Therefore $B^{(p)} (k) = 2.174 \cdot 2^{k} .$
$B (0) = 1 \Rightarrow b_{1} + 2.174 = 1 \Rightarrow b_{1} = - 1.174$

Therefore, $B (k) = - 1.174 \cdot {1.08}^{k} + 2.174 \cdot 2^{k} .$

Example 8.3.22. Matching Roots.

Find the general solution to

S (k) - 3 S (k - 1) - 4 S (k - 2) = 4^{k} .

The characteristic roots of the associated homogeneous relation are $- 1$ and 4. Therefore, $S^{(h)} (k) = b_{1} (- 1)^{k} + b_{2} 4^{k} .$
A function of the form $d 4^{k}$ will not be a particular solution of the nonhomogeneous relation since it solves the associated homogeneous relation. When the right-hand side involves an exponential function with a base that equals a characteristic root,you should multiply your guess at a particular solution by $k .$ Our guess at $S^{(p)} (k)$ would then be $d k 4^{k}$ . See Observation 8.3.23 for a more complete description of this rule.
Substitute $d k 4^{k}$ into the recurrence relation for $S (k) :$

$\begin{matrix} d k 4^{k} - 3 d (k - 1) 4^{k - 1} - 4 d (k - 2) 4^{k - 2} = 4^{k} \\ 16 d k 4^{k - 2} - 12 d (k - 1) 4^{k - 2} - 4 d (k - 2) 4^{k - 2} = 4^{k} \end{matrix}$

Each term on the left-hand side has a factor of $4^{k - 2}$

$16 d k - 12 d (k - 1) - 4 d (k - 2) = 4^{2} 20 d = 16 \Rightarrow d = 0.8$

Therefore, $S^{(p)} (k) = 0.8 k 4^{k} .$
The general solution to the recurrence relation is

$S (k) = b_{1} (- 1)^{k} + b_{2} 4^{k} + 0.8 k 4^{k}$

🔗

Observation 8.3.23. When the base of right-hand side is equal to a characteristic root.

🔗

If the right-hand side of a nonhomogeneous relation involves an exponential with base

a,

and

a

is also a characteristic root of multiplicity

p,

then multiply your guess at a particular solution as prescribed in Table 8.3.17 by

k^{p},

where

k

is the index of the sequence.

Example 8.3.24. Examples of matching bases.

If $S (k) - 9 S (k - 1) + 20 S (k - 2) = 2 \cdot 5^{k},$ the characteristic roots are 4 and 5. Since 5 matches the base of the right side, $S^{(p)} (k)$ will take the form $d k 5^{k} .$
If $S (n) - 6 S (n - 1) + 9 S (n - 2) = 3^{n + 1}$ the only characteristic root is 3, but it is a double root (multiplicity 2). Therefore, the form of the particular solution is $d n^{2} 3^{n} .$
If $Q (j) - Q (j - 1) - 12 Q (j - 2) = (- 3)^{j} + 6 \cdot 4^{j},$ the characteristic roots are $- 3$ and 4. The form of the particular solution will be $d_{1} j (- 3)^{j} + d_{2} j \cdot 4^{j} .$
If $S (k) - 9 S (k - 1) + 8 S (k - 2) = 9 k + 1 = (9 k + 1) 1^{k},$ the characteristic roots are 1 and 8. If the right-hand side is a polynomial, as it is in this case, then the exponential factor $1^{k}$ can be introduced. The particular solution will take the form $k (d_{0} + d_{1} k) .$

🔗

We conclude this section with a comment on the situation in which the characteristic equation gives rise to complex roots. If we restrict the coefficients of our finite order linear relations to real numbers, or even to integers, we can still encounter characteristic equations whose roots are complex. Here, we will simply take the time to point out that our algorithms are still valid with complex characteristic roots, but the customary method for expressing the solutions of these relations is different. Since an understanding of these representations requires some background in complex numbers, we will simply suggest that an interested reader can refer to a more advanced treatment of recurrence relations (see also difference equations).

🔗

Exercises 8.3.5 Exercises

🔗

Exercise Group.

🔗

Solve the following sets of recurrence relations and initial conditions:

🔗

1.

🔗

S (k) - 10 S (k - 1) + 9 S (k - 2) = 0,

S (0) = 3,

S (1) = 11

Answer.

S (k) = 2 + 9^{k}

🔗

2.

🔗

S (k) - 9 S (k - 1) + 18 S (k - 2) = 0,

S (0) = 0,

S (1) = 3

🔗

3.

🔗

S (k) - 0.25 S (k - 1) = 0,

S (0) = 6

Answer.

S (k) = 6 (1 / 4)^{k}

🔗

4.

🔗

S (k) - 20 S (k - 1) + 100 S (k - 2) = 0,

S (0) = 2,

S (1) = 50

🔗

5.

🔗

S (k) - 2 S (k - 1) + S (k - 2) = 2, S (0) = 25, S (1) = 16

Answer.

S (k) = k^{2} - 10 k + 25

🔗

6.

🔗

S (k) - S (k - 1) - 6 S (k - 2) = - 30,

S (0) = 7,

S (1) = 6

🔗

7.

🔗

S (k) - 5 S (k - 1) = 5^{k}, S (0) = 3

Answer.

S (k) = (3 + k) 5^{k}

🔗

8.

🔗

S (k) - 5 S (k - 1) + 6 S (k - 2) = 2, S (0) = - 1, S (1) = 0

🔗

9.

🔗

S (k) - 4 S (k - 1) + 4 S (k - 2) = 3 k + 2^{k}, S (0) = 1, S (1) = 1

Answer.

S (k) = (12 + 3 k) + (k^{2} + 7 k - 22) 2^{k - 1}

🔗

10.

🔗

S (k) = r S (k - 1) + a,

S (0) = 0,

r, a \geq 0, r \neq 1

🔗

11.

🔗

S (k) - 4 S (k - 1) - 11 S (k - 2) + 30 S (k - 3) = 0,

S (0) = 0,

S (1) = - 35, S (2) = - 85

Answer.

S (k) = 4 (- 3)^{k} + 2^{k} - 5^{k + 1}

🔗

12.

🔗

Find a closed form expression for

P (k)

in Exercise 8.2.3.3 of Section 8.2.

🔗

13.

🔗

Find a closed form expression for the terms of the Fibonacci sequence (see Example 8.1.8).
The sequence $C$ was defined by $C_{r}$ = the number of strings of zeros and ones with length $r$ having no consecutive zeros (Example 8.2.2(c)). Its recurrence relation is the same as that of the Fibonacci sequence. Determine a closed form expression for $C_{r},$ $r \geq 1 .$

Answer.

The characteristic equation is $a^{2} - a - 1 = 0,$ which has solutions $α = (1 + \sqrt{5}) / 2$ and $β = (1 - \sqrt{5}) / 2,$ It is useful to point out that $α + β = 1$ and $α - β = \sqrt{5} .$ The general solution is $F (k) = b_{1} α^{k} + b_{2} β^{k} .$ Using the initial conditions, we obtain the system: $b_{1} + b_{2} = 1$ and $b_{1} α + b_{2} β = 1 .$ The solution to this system is $b_{1} = α / (α - β) = (5 + \sqrt{5}) / 2 \sqrt{5}$ and $b_{2} = β / (α - β) = (5 - \sqrt{5}) / 2 \sqrt{5}$

Therefore the final solution is

$\begin{aligned} F (n) & = \frac{α^{n + 1} - β^{n + 1}}{α - β} \\ = \frac{{((1 + \sqrt{5}) / 2)}^{n + 1} - {((1 - \sqrt{5}) / 2)}^{n + 1}}{\sqrt{5}} \end{aligned}$
$C_{r} = F (r + 1)$

🔗

14.

🔗

S (n) = \sum_{j = 1}^{n} g (j),

n \geq 1,

then

S

can be described with the recurrence relation

S (n) = S (n - 1) + g (n) .

For each of the following sequences that are defined using a summation, find a closed form expression:

🔗

$S (n) = \sum_{j = 1}^{n} j,$ $n \geq 1$
$Q (n) = \sum_{j = 1}^{n} j^{2},$ $n \geq 1$
$P (n) =$ $\sum_{j = 1}^{n} {(\frac{1}{2})}^{j},$ $n \geq 1$
$T (n) = \sum_{j = 1}^{n} j^{3},$ $n \geq 1$

🔗

15.

🔗

Let

D (n)

be the number of ways that the set

{1, 2, . . ., n},

n \geq 1,

can be partitioned into two nonempty subsets.

🔗

Find a recurrence relation for $D .$ (Hint: It will be a first-order linear relation.)
Solve the recurrence relation.

Answer.

For each two-block partition of ${1, 2, \dots, n - 1},$ there are two partitions we can create when we add $n,$ but there is one additional two-block partition to count for which one block is ${n} .$ Therefore, $D (n) = 2 D (n - 1) + 1 for n \geq 2 and D (1) = 0.$
$D (n) = 2^{n - 1} - 1$

🔗

16.

🔗

If you were to deposit a certain amount of money at the end of each year for a number of years, this sequence of payments would be called an annuity (see Example 8.3.21).

Find a closed form expression for the balance or value of an annuity that consists of payments of $q$ dollars at a rate of interest of $i .$ Note that for a normal annuity, the first payment is made after one year. However, assume that there is an initial balance $b_{0} .$ This will be convenient to apply our solution to the case of a loan.
With an interest rate of 5.5 percent, how much would you need to deposit into an annuity to have a value of one million dollars after 18 years?
The payment of a loan is a form of annuity in which the initial value is some negative amount (the amount of the loan) and the annuity ends when the value is raised to zero. How much could you borrow if you can afford to pay $5,000 per year for 25 years at 11 percent interest?

🔗

17.

🔗

Suppose that

C

is a small positive number. Consider the recurrence relation

B (k) - 2 B (k - 1) + (1 - C^{2}) B (k - 2) = C^{2},

with initial conditions

B (0) = 1

and

B (1) = 1 .

C

is small enough, we might consider approximating the relation by replacing

1 - C^{2}

with 1 and

C^{2}

with 0. Solve the original relation and its approximation. Let

B_{a}

a be the solution of the approximation. Compare closed form expressions for

B (k)

and

B_{a} (k) .

Their forms are very different because the characteristic roots of the original relation were close together and the approximation resulted in one double characteristic root. If characteristic roots of a relation are relatively far apart, this problem will not occur. For example, compare the general solutions of

S (k) + 1.001 S (k - 1) - 2.004002 S (k - 2) = 0.0001

and

S_{a} (k) + S_{a} (k - 1) - 2 S_{a} (k - 2) = 0 .

You have attempted of activities on this page.

Prev Top Next

Section 8.3 Recurrence Relations

Subsection 8.3.1 Definition and Terminology

Definition 8.3.1. Recurrence Relation.

Example 8.3.2. Some Examples of Recurrence Relations.

Subsection 8.3.2 Solving Recurrence Relations

Definition 8.3.3. nth Order Linear Recurrence Relation.

Example 8.3.4. Some Finite Order Linear Relations.

Subsection 8.3.3 Recurrence Relations Obtained from “Solutions”

Definition 8.3.7. Homogeneous Recurrence Relation.

Example 8.3.8. First Order Homogeneous Recurrence Relations.

Example 8.3.9. A Second Order Example.

Definition 8.3.10. Characteristic Equation.

Example 8.3.11. Some characteristic equations.

Algorithm 8.3.12. Algorithm for Solving Homogeneous Finite Order Linear Relations.

Example 8.3.13. A solution using the algorithm.

Example 8.3.14. Solution of a Third Order Recurrence Relation.

Example 8.3.15. Solution with a Double Characteristic Root.

Subsection 8.3.4 Solution of Nonhomogeneous Finite Order Linear Relations

Algorithm 8.3.16. Algorithm for Solving Nonhomogeneous Finite Order Linear Relations.

Example 8.3.18. Solution of a Nonhomogeneous First Order Recurrence Relation.

Example 8.3.19. Solution of a Nonhomogeneous Second Order Recurrence Relation.

Note 8.3.20. A quick note on interest rates.

Example 8.3.21. A Sort of Annuity.

Example 8.3.22. Matching Roots.

Observation 8.3.23. When the base of right-hand side is equal to a characteristic root.

Example 8.3.24. Examples of matching bases.

Exercises 8.3.5 Exercises

Exercise Group.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

Definition 8.3.3. $n^{t h}$ Order Linear Recurrence Relation.