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).

Subsection8.3.1Definition and Terminology¶ permalink

Definition8.3.1Recurrence 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\) is \(\{0,1,2,\textrm{...}\}\), the terms \(S
(0), S(1), . . . , S\left(k_0-1\right)\) are not defined by the recurrence formula.Their values are the initial conditions (or boundary conditions,
or basis) that complete the definition of \(S\).

Example8.3.2Some 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, 8.2.2, can be defined with the same recurrence relation, but with different initial conditions.

The relation \(T(k) = 2T(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(\lfloor n/2\rfloor ) + 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\).

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.

Definition8.3.3\(n^{th}\) Order Linear Recurrence Relation

Let \(S\) be a sequence of numbers with domain \(k\geq 0\). An \(n^{\textrm{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)\textrm{ for }k \geq n\]
where \(C_1, C_2, \ldots , 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^{\textrm{th}}\) order linear relations. Therefore, in further discussions, \(S(k)
+ 2k S(k - 1) = 0\) would not be considered a first-order linear relation.

Example8.3.4Some 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) + 2P(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) - 2A(k - 1) = 2k\). Therefore, it is a first-order linear relation.

Subsection8.3.3Recurrence relations obtained from “solutions”¶ permalink

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\). If \(k \geq 1\),
\(\quad\)\(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:

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

\( \textrm{Original equation}\)

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

\( \textrm{Substitute } k-1 \textrm{ for } k \)

\(\textrm{ and multipy by } 3\)

\(\)

\(\textrm{Subtract the second equation}\)

\(\textrm{from the first.}\)

\(C(k)-3C(k-1)=-2^k-2k+3\)

\(3^{k-1} \textrm{ term is eliminated.} \)

\( \textrm{ This is a first order relation}\).

\(2C(k-1)-6C(k-2)=-2^k-2(2(k-1))+6)\)

\(\textrm{Substitute } k-1 \textrm{ for } k \textrm{ in the}\)

\(\textrm{third equation, multiply. by } 2\).

\(\)

\(\textrm{Subtract the 4th equation from the 3rd.}\)

\( C(k)-5C(k-1)+6C(k-2)=2k-7\)

\(2^{k+1}\textrm{term is eliminated.}\)

\(\textrm{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.5 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.

Closed Form Expression

Recurrence Relation

\(D(k)=5\cdot 2^k\)

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

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

\(C(k)-2C(k-1)-6C(k-2)=2k-7\)

\(Q(k)=2k + 9\)

\(Q(k)-Q(k-1)=2\)

\(A(k)=k^2-k\)

\(A(k)-2A(k-1)+A(k-2)=2\)

\(B(k)=2 k^2+1\)

\(B(k)-2B(k-1)+B(k-2)=4\)

\(G(k)=2\cdot 4^k-5(-3)^k\)

\(G(k)-G(k-1)+12G(k-2)=0\)

\(J(k)=(3+k) 2^k\)

\(J(k)-4J(k-1)+4J(k-2)=0\)

Table8.3.5Recurrence relations obtained from given sequences

Definition8.3.6Homogeneous Recurrence Relation

An \(n^{th}\) order linear relation is homogeneous if \(f(k)
= 0\) for all \(k\). For each recurrence relation \(S(k) + C_1S(k - 1) +\ldots + C_n S(k - n) = f(k)\), the associated homogeneous relation is \(S(k)
+ C_1S(k - 1) +\ldots + C_n S(k - n) =0\)

Example8.3.7First Order Homogeneous Recurrence Relations

\(D(k) - 2D(k - 1) = 0\) is a first-order homogeneous relation. Since it can also be written as \(D(k) = 2D(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.

Example8.3.8A Second Order Example

Consider the second-order homogeneous relation \(S(k) - 7S(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
\[\quad \quad \quad \begin{array}{ccc}
S(k)=b a^k & & \\
S(k-1)=b a^{k-1} & \textrm{ } & \textrm{ } \\
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{gather}
a^2 - 7a + 12 = (a - 3) (a - 4) = 0\label{eq-characteristic-example}\tag{8.3.1}
\end{gather}

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_24^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\).
\[\left\{
\begin{array}{c}
S(0)=4 \\
S(1)=4 \\
\end{array}
\right\}\textrm{ }\Rightarrow \left\{
\begin{array}{c}
b_13^0+b_24^0=4 \\
b_13^1+b_24^1=4 \\
\end{array}
\right\}\textrm{ }\Rightarrow \left\{
\begin{array}{c}
b_1+b_2=4 \\
3b_1+4b_2=4 \\
\end{array}
\right\}\textrm{ }\]

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\).

Definition8.3.9Characteristic Equation

The characteristic equation of the homogeneous \(n^{\textrm{th}}\) order linear relation \(S(k) + C_1 S(k- 1) +\ldots + 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_1a^{n-1}+\cdots +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.

Example8.3.10Some 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) + 2Q(k - 1) - 3Q(k - 2) - 6 Q(k- 4) = 0\) is \(a^4+ 2a^3 - 3a^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.

Algorithm8.3.11Algorithm for Solving Homogeneous Finite-order Linear Relations

Write out the characteristic equation of the relation \(S(k) + C_1S(k - 1) +\ldots + C_n S(k - n) =0\), which is \(a^n+ C_1a^{n-1}+\cdots
+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_1a_1{}^k+ b_2a_2{}^k+\cdots +b_na_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_ja_j{}^k\) term is replaced with \(\left(b_{j 0}+b_{j 1}k\right)a_j{}^k\). In general, if \(a_j\)
is a root of multiplicity \(p\), then the \(b_ja_j{}^k\) term is replaced with \(\left(b_{j 0}+b_{j 1}k+\cdots +b_{j(p-1)}k^{p-1}\right)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\) is
\[x=\frac{-b\pm \sqrt{b^2-4 a c}}{2 a}\]
The solutions of \(a^2+ C_1a + C_2 = 0\) are then
\[\frac{1}{2}\left(-C_1+\sqrt{C_1{}^2-4 C_2}\right)\textrm{ and }\frac{1}{2}\left(-C_1-\sqrt{C_1{}^2-4 C_2}\right)\]

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.

Example8.3.12A solution using the algorithm

Suppose that \(T\) is defined by \(T(k) =7T(k-1)-10T(k-2)\), with \(T(0) = 4\) and \(T(1) = 17\). We can solve this
recurrence relation with Algorithm 8.3.11:

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) -7T(k-1)+10T(k-2)=0\). Therefore, the characteristic equation is \(a^2 -7a + 10 = 0\).

The characteristic roots are \(\frac{1}{2}\left(7+\sqrt{49-40}\right)=5\) and \(\frac{1}{2}\left(7-\sqrt{49-40}\right)=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_12^k+ b_25^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.)

Example8.3.13Solution of a Third Order Recurrence Relation.

The characteristic equation is \(a^3 - 7a + 6 = 0\).

The only rational roots that we can attempt are \(\pm 1, \pm 2, \pm 3, \textrm{and} \pm 6\). By checking these, we obtain the three roots 1,
2, and \(-3\).

The general solution is \(S(k) =b_11^k+b_22^k+b_3(-3){}^k\). The first term can simply be written \(b_1\) .

\(\left\{
\begin{array}{c}
S(0)=8 \\
S(1)=6 \\
S(2)=22 \\
\end{array}
\right\}\textrm{ }\Rightarrow \left\{
\begin{array}{c}
b_1+b_2+b_3=8 \\
b_1+2b_2-3b_3=6 \\
b_1+4b_2+9b_3=22 \\
\end{array}
\right\}\textrm{ }\)
You can solve this system by elimination to obtain \(b_1=5\), \(b_2=2\), and \(b_3=1\). Therefore,
\(\quad\)\(S(k) = 5 + 2\cdot 2^k + (-3)^k = 5 + 2^{k+1} + (-3)^k\)

Example8.3.14Solution with a Double Characteristic Root

Solve \(D(k) - 8D(k - I) + 16D(k - 2) = 0\), where \(D(2) = 16\) and \(D(3) = 80\).

Characteristic equation: \(a^2- 8a + 16 = 0\).

\(a^2- 8a + 16 = (a - 4)^2\). Therefore, there is a double characteristic root, 4.

General solution: \(D(k) = \left(b_{10}+b_{11}k\right)4^k\).

Subsection8.3.4Solution of Nonhomogeneous Finite Order Linear Relations¶ permalink

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.

Algorithm8.3.15Algorithm for Solving Nonhomogeneous Finite-order Linear Relations

To solve the recurrence relation \(S(k) + C_1S(k - 1) +\ldots + 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.11). 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.16).

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, if possible, to get a complete solution.

The associated homogeneous relation,\(S(k) + 5S(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 + 5d = 9\), or \(6d = 9\). Therefore, \(S^{(p)}(k)=1.5\).

The general solution of the recurrence relation is
\(\quad\)\(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\).
\(\quad\)\(S(0) = 6 \Rightarrow \textrm{ }b(-5)^0+ 1.5 = 6\textrm{ }\Rightarrow \textrm{ }b\textrm{ }+ 1.5 = 6\)
Therefore, \(b = 4.5\) and \(S(k) = 4.5(-5)^k + 1.5\).

Example8.3.18Solution of a Nonhomogeneous Second Order Recurrence Relation

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.08A\) added
to it, so that the new balance is \(A+0.08A = (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 \(\left(1+\frac{0.035}{12}\right) \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.

Example8.3.20A 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{equation*}\begin{split}
d 2^k = 1.08d 2^{k-1}+2^k & \Rightarrow (2d) 2^{k-1} = 1.08d 2^{k-1}+ 2\cdot 2^{k-1}\\
& \Rightarrow 2d = 1.08 d + 2\\
&\Rightarrow .92d = 2 \\
&\Rightarrow d= 2.174 \textrm{ to the nearest thousandth})
\end{split}\end{equation*}
Therefore \(B^{(p)}(k)=2.174\cdot 2^k\).

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 8.3.22 for a more complete description of this rule.

Substitute \(d k 4^k\) into the recurrence relation for \(S(k)\):
\begin{equation*}\begin{array}{c}
d k 4^k-3d (k-1) 4^{k-1}-4d (k-2) 4^{k-2}=4^k\\
16d k 4^{k-2}-12d (k-1) 4^{k-2}-4d (k-2) 4^{k-2}=4^k\\
\end{array}\end{equation*}
Each term on the left-hand side has a factor of \(4^{k-2}\)
\begin{equation*} 16 d k - 12d(k - 1) - 4d(k - 2) = 4^220 d = 16 \Rightarrow d=0.8\end{equation*}
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\]

Observation8.3.22When 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.16 by \(k^p\), where \(k\) is the
index of the sequence.

Example8.3.23Examples of matching bases

If \(S(k) - 9S(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)- 6S(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)-12Q(j-2)=(-3)^j+ 6\cdot 4^j\), the characteristic roots are \(-3\) and 4. The form of the particular solution will
be \(d_1j (-3)^j+ d_2j\cdot 4^j\).

If \(S(k) - 9S(k - 1) + 8S(k- 2) = 9k + 1 = (9k + 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\left(d_0+ d_1k\right)\).

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).

Subsection8.3.5Exercises for Section 8.3¶ permalink

Solve the following sets of recurrence relations and initial conditions:

Find a closed form expression for \(P(k)\) in Exercise 3 of Section 8.2.

13

Find a closed form expression for the terms of the Fibonacci sequence (see Example 8.1.4).

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.1(c)). Its recurrence relation is the same as that of the Fibonacci sequence. Determine a closed form expression for \(C_r\),
\(r \geq 1\).

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

Therefore the final solution is
\(F(n)=\left(1\left/\sqrt{5}\right.\right)\left[\left(\left.\left(1+\sqrt{5}\right)\right/2\right)^{n+1}-\left(\left.\left(1-\sqrt{5}\right)\right/2\right)^{n+1}\right]\)

\(C_r=F(r+1)\)

14

If \(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:

\(D(n)=2D(n-1)+1 \textrm{ for } n \geq 2 \textrm{ 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 payment would be called an
annuity (see Example 8.3.20).

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.

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 \textrm{$}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) - 2B(k - 1) + \left(1 - C ^2\right)B(k - 2)
= C^2\), with initial conditions \(B(0) = 1\) and \(B(1) = 1\). If \(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.001S(k - 1) - 2.004002S(k - 2) = 0.0001\) and
\(S_a(k) + S_a(k - 1) - 2S_a(k - 2) = 0\).