Skip to main content

Section 4.3 Linear Recurrence Relations

Alex Jordan

Subsection 4.3.1 Linear Recurrence Realtions

Consider a sequence where a few initial terms are given, and then each successive term is defined using the terms that preceded it. For instance, we might begin a sequence with \(\set{a_1,a_2,\ldots}=\set{1,2,\ldots}\) and then require \(a_n=3a_{n-1}-a_{n-2}\text{.}\) This establishes all of the terms that follow. For instance,

\begin{align*} a_3&=3a_2-a_1&a_4&=3a_3-a_2\\ &=3(2)-1&&=3(5)-2\\ &=5&&=13 \end{align*}

and in this way the sequence elements will all be determined: \(\set{1,2,5,13,34,\ldots}\text{.}\) Sequences such as this are of special interest, and motivate us to introduce vocabulary for referring to them.

Definition 4.3.1. Linear Recurrence Relation.

When the terms of a sequence \(\set{a_n}\) admit a relation of the form \(a_n=L(a_{n-1},\ldots,a_{n-k})\text{,}\) where \(k\) is fixed, and \(L\) is a linear function on \(k\) variables, we refer to the relation as a linear recurrence of depth \(k\text{.}\) The first several terms of the sequence may or may not respect the recurrence relation; but it is required that once \(n\) is large enough, the recurrence relation holds.

Subsection 4.3.2 Examples

Male honeybees (also known as drones) hatch from unfertilized eggs, and so they have a mother but no father. Female honeybees (both queens and workers) hatch from fertilized eggs, and so each female honeybee has two parents (one of each sex). This leads to an interesting family tree for any single honeybee. If we consider a male, he only has one parent. That parent must have been female, so our male had two grandparents. As we continue to count, we will ignore any possibility for tangled family trees, which is admittedly unrealistic. Figure Figure 4.3.3 displays the bees family tree going back several generations.

Figure 4.3.3. Honeybee Ancestors

If we define \(a_n\) to be the number of ancestors at level \(n\text{,}\) where level 1 has our drone's parent, level 2 has his grandparents, and so on, then we see in Figure Figure 4.3.3 the sequence \(\set{a_1,a_2,\ldots}=\set{1,2,3,5,8,\ldots}\text{.}\) Note that every bee, regardless of sex, has precisely one mother and precisely one grandfather. The bees at level \(n-1\) have their mother at level \(n\text{,}\) and the bees at level \(n-2\) have their grandfather at level \(n\text{.}\) Since this accounts for all of the bees at level \(n\text{,}\) partitioned according to sex, it tells us that

\begin{equation*} a_n=a_{n-1}+a_{n-2}\text{,} \end{equation*}

giving us a recurrence relation. The linear function \(L\) referred to in Definition Definition 4.3.1 is defined simply by \(L(x,y)=x+y\text{,}\) and we have \(a_n=L(a_{n-1},a_{n-2})\text{.}\)

A certain subspecies of elderberry tree produces its fruit in berry clusters. A branch that is “new wood” (that just sprouted the previous season) will produce one fruit cluster, and it will sprout one new branch. The following year, any “new wood” branches become “seasoned wood”, and produce three berry clusters and sprout two more branches. Finally, in the year that follows, any “seasoned wood” branches become “old wood”, and produce neither berry clusters nor sprout new branches.

If we start at year 1 with just a single branch of “new wood”, then on year \(n\text{,}\) how many berry clusters will we have? Some notation will help. In year \(n\text{,}\) let \(b_n\) represent the number of berry clusters, \(w_n\) be the number of “new wood” branches, and \(s_n\) be the number of “seasoned wood” branches. The description of how branches and berry clusters are formed tells us

\begin{align*} b_n&=w_n+3s_n\\ w_n&=w_{n-1}+2s_{n-1}\\ s_n&=w_{n-1}\text{,} \end{align*}

and this in turn tells us that

\begin{align*} b_n&=w_n+3s_n\\ &=(w_{n-1}+2s_{n-1})+3w_{n-1}\\ &=(w_{n-1}+3s_{n-1})+3w_{n-1}-s_{n-1}\\ &=b_{n-1}+(3w_{n-2}+6s_{n-2})-w_{n-2}\\ &=b_{n-1}+2w_{n-2}+6s_{n-2}\\ &=b_{n-1}+2b_{n-2}\text{.} \end{align*}

Thus the number of berry clusters in year \(n\) satisfies the recurrence relation \(b_n=b_{n-1}+2b_{n-2}\text{.}\) The linear function \(L\) referred to in Definition Definition 4.3.1 is defined by \(L(x,y)=x+2y\text{,}\) and we have \(b_n=L(b_{n-1},b_{n-2})\text{.}\) The initial terms are \(\set{b_1,b_2,\ldots}=\set{1,4,\ldots}\text{.}\)

Well, we've seen a few examples of linear recurrence relations, but what does any of this have to do with linear algebra? Consider what would happen if you needed to know the hundredth term of a recursive sequence, knowing only the values of the first few terms and a recurrence relation. You could tediously compute away, calculating each term in the sequence until you reached the hundredth term. Fortunately, matrix diagonalization will provide us with a much more efficient technique.

The Fibonacci Sequence is a famous sequence with a simple linear recurrence relation. The sequence begins \(\set{f_1,f_2,\ldots}=\set{1,1,\ldots}\) and has the recurrence relation

\begin{equation*} f_n=f_{n-1}+f_{n-2}\text{.} \end{equation*}

(This is the same recurrence relation as with the bees in Example Example 4.3.2, but for the bees the initial terms of the sequence were \(\set{1,2,\ldots}\text{.}\)) This gives us the Fibonacci Sequence

\begin{equation*} \set{f_1,f_2,\ldots}=\set{1,1,2,3,5,8,13,21,35,\ldots}\text{,} \end{equation*}

which arises several places in nature and mathematics. For example, we can see these same values arising in the ancestor count of honeybees from Example Example 4.3.2.

We are setting out to find a simple formula for \(f_n\text{,}\) so that if needed, we could compute something like the hundredth Fibonacci number quickly and avoid calculating each value along the way. We casually make the observation that

\begin{align*} f_n&=f_{n-1}+f_{n-2}\\ f_{n-1}&=f_{n-1}\text{.} \end{align*}

Experience with linear algebra makes us realize that these two equations can be viewed as a single matrix equation:

\begin{align*} \colvector{f_n\\f_{n-1}}&=\begin{bmatrix}1&1\\1&0\end{bmatrix}\colvector{f_{n-1}\\f_{n-2}}\text{.} \end{align*}

So a pair of adjacent Fibonacci numbers \(\colvector{f_n\\f_{n-1}}\) can be obtained from multiplying the matrix \(A=\begin{bmatrix}1&1\\1&0\end{bmatrix}\) with the previous pair of adjacent Fibonacci numbers. This implies that

\begin{equation*} \colvector{f_n\\f_{n-1}}=A^{n-2}\colvector{f_2\\f_1}=A^{n-2}\colvector{1\\1}\text{.} \end{equation*}

If we can diagonalize the matrix \(A\text{,}\) we will be able to take a great shortcut for evaluating the right hand side.

Diagonalizing \(A\text{,}\) we find

\begin{align*} A=\begin{bmatrix}1&1\\1&0\end{bmatrix}&=\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G&0\\0&g\end{bmatrix}\inverse{\begin{bmatrix}G&g\\1&1\end{bmatrix}}\\ &=\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G&0\\0&g\end{bmatrix}\frac{1}{\sqrt{5}}\begin{bmatrix}1&-g\\-1&G\end{bmatrix}\text{,} \end{align*}

where \(G\) is the larger (positive) golden ratio \(\frac{1+\sqrt{5}}{2}\text{,}\) and \(g\) is the smaller (negative) golden ratio \(\frac{1-\sqrt{5}}{2}\text{,}\) and \(G\) and \(g\) are the eigenvalues of \(A\text{.}\)

Now let's return to the issue of finding the \(n\)th Fibonacci number. In the following, we will make use of the fact that \(1-g=G\text{.}\) We have

\begin{align*} \colvector{f_n\\f_{n-1}}&=A^{n-2}\colvector{1\\1}\\ &=\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G&0\\0&g\end{bmatrix}^{n-2}\frac{1}{\sqrt{5}}\begin{bmatrix}1&-g\\-1&G\end{bmatrix}\colvector{1\\1}\\ &=\frac{1}{\sqrt{5}}\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G^{n-2}&0\\0&g^{n-2}\end{bmatrix}\colvector{1-g\\-1+G}\\ &=\frac{1}{\sqrt{5}}\begin{bmatrix}G^{n-1}&g^{n-1}\\G^{n-2}&g^{n-2}\end{bmatrix}\colvector{G\\-g}\\ \colvector{f_n\\f_{n-1}}&=\frac{1}{\sqrt{5}}\colvector{G^{n}-g^{n}\\G^{n-1}-g^{n-1}}\text{.} \end{align*}

Thus we have found a fairly simple formula for the \(n\)th Fibonacci number:

\begin{align} f_n&=\frac{1}{\sqrt{5}}\left(G^n-g^n\right)\notag\\ &=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\text{.}\label{fibonacci-formula}\tag{4.3.1} \end{align}

We could stop here, but with this formula we can make one nice simplification. Since \(\left\vert g\right\vert<1\text{,}\) for large \(n\text{,}\) the term \(\frac{1}{\sqrt{5}}g^n\) in this formula is very small, and can be neglected if we round the other term to the nearest whole number. In fact we are so fortunate in this regard that we can make that simplification for all \(n\geq1\text{.}\) So we have an even simpler formula for the \(n\)th Fibonacci number:

\begin{align} f_n&=\operatorname{round}\left(\frac{1}{\sqrt{5}}G^n\right)\notag\\ &=\operatorname{round}\left(\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\right)\text{.}\label{simplified-fibonacci-formula}\tag{4.3.2} \end{align}

Subsection 4.3.3 The general approach

Can we generalize what happened with the Fibonacci numbers in Example Example 4.3.5? We began with a recurrence relation

\begin{equation*} a_{n}=L(a_{n-1},\ldots,a_{n-k})=c_{n-1}a_{n-1}+\cdots+c_{n-k}a_{n-k}\text{.} \end{equation*}

We considered a trivial additional equation

\begin{equation*} a_{n-1}=a_{n-1}\text{.} \end{equation*}

In general, we may need to consider more such trivial equations, and we can obtain the system of equations

\begin{align*} a_{n}&=c_{n-1}a_{n-1}+\cdots+c_{n-(k-1)}a_{n-(k-1)}+c_{n-k}a_{n-k}\\ a_{n-1}&=\phantom{c_{n-1}}a_{n-1}\\ \vdots&=\phantom{c_{n-1}a_{n-1}+{}}\ddots\\ a_{n-(k-1)}&=\phantom{c_{n-1}a_{n-1}+\cdots+c_{n-(k-1)}}a_{n-(k-1)}\text{,} \end{align*}

which we interpret as a matrix equation

\begin{align} \colvector{a_n\\a_{n-1}\\\vdots\\a_{n-(k-1)}}&=\begin{bmatrix}c_{n-1}&c_{n-2}&\cdots&c_{n-(k-1)}&c_{n-k}\\1&0&\cdots&0&0\\0&1&\ddots&0&0\\\vdots&\ddots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\end{bmatrix}\colvector{a_{n-1}\\a_{n-2}\\\vdots\\a_{n-k}}\notag\\ \vect{a}_n&=A\vect{a}_{n-1}\text{.}\label{eq-matrix-recursion}\tag{4.3.3} \end{align}

If we know the first \(k\) terms of the sequence, then we know the vector \(\vect{a}_{k}\text{,}\) and we can recursively apply equation (4.3.3) to get that

\begin{equation*} \vect{a}_n=A^{n-k}\vect{a}_{k}\text{.} \end{equation*}

Generally, raising a matrix \(A\) to high powers would be difficult or time-consuming. But if we can diagonalize \(A\) first (or at least find its Jordan canonical form discussed in Section Section 3.3) it becomes fast and easy. For now let's assume that \(A\) is diagonalizable. If \(D\) is a diagonal matrix similar to \(A\text{,}\) having the eigenvalues of \(A\) for its entries, and \(A=PD\inverse{P}\text{,}\) then

\begin{align} \vect{a}_n&=A^{n-k}\vect{a}_{k}\notag\\ \vect{a}_n&=PD^{n-k}\inverse{P}\vect{a}_{k}\text{.}\label{recurrence-diagonal-equation}\tag{4.3.4} \end{align}

There are two ways to proceed to find a formula for \(a_{n}\text{.}\) If we have an explicit diagonalization of \(A\) (meaning we explicitly know \(P\text{,}\) \(D\text{,}\) and \(\inverse{P}\)) then we can simply multiply the right hand side through, and the first element of the resulting vector gives a formula for \(a_{n}\text{.}\)

It may be difficult to explicitly diagonalize \(A\) though, since finding \(\inverse{P}\) can take time. If that's the case, we don't actually need to explicitly work out the right side of (4.3.4). We can just acknowledge that when all is said and done on the right side, the result will be a linear combination of the eigenvalues of \(A\) raised to the \(n\)th power. To find the coefficients of this linear combination, we can consider them as variables, and use the known initial values of the sequence to set up a system of equations that will determine the coefficients.

These considerations lead us to:

The first item has been proved already in the discussion leading to this theorem.

For the second item, we know from the general diagonalization technique that the \(j\)th column of \(P\) needs to be an eignevector for \(A\) with eigenvalue \(\lambda_j\text{.}\) To find such an eigenvector, we examine the equation

\begin{align*} \left(A-\lambda_jI\right)\vect{x}_j&=\vect{0}\\ \begin{bmatrix}c_{n-1}-\lambda_j&c_{n-2}&\cdots&c_{n-(k-1)}&c_{n-k}\\1&-\lambda_j&\cdots&0&0\\0&1&\ddots&0&0\\\vdots&\ddots&\ddots&\vdots&\vdots\\0&0&\cdots&1&-\lambda_j\end{bmatrix}\vect{x}_j&=\vect{0}\text{.} \end{align*}

We already know this matrix has rank \(n-1\) since \(\lambda_j\) is an eigenvalue, and the bottom \(n-1\) rows are clearly linearly independent. So we can ignore the top row. Row reducing the remaining rows is then rather easy, and reveals that \(\vect{x}_j=\transpose{\begin{bmatrix}\lambda_j^{n-1}&\lambda_j^{n-2}&\cdots&1\end{bmatrix}}\text{.}\) This establishes the form of \(P\) specified in the claim.

Lastly, if \(J\) from the first item was diagonal with distinct eignenvalues as in the second item, and we were to multiply out the matrix product from the first item, we would have a linear combination of the powers of the eigenvalues. So \(a_n=\sum_{i=1}^{n}x_i\lambda_i^n\text{.}\)

Suppose \(a_1=1\text{,}\) \(a_2=4\text{,}\) \(a_3=6\text{,}\) and \(a_n=5a_{n-1}-2a_{n-2}-8a_{n-3}\text{.}\) Let's find a formula for the general term of the sequence \(a_n\text{.}\)

We need to consider the matrix

\begin{equation*} A=\begin{bmatrix}5&-2&-8\\1&0&0\\0&1&0\end{bmatrix}\text{.} \end{equation*}

While we could explicitly diagonalize this matrix, it might turn out to be a bit tedious since the matrix is \(3\times3\text{.}\) Instead we just find its eigenvalues: \(4,2,-1\text{.}\) The three distinct eigenvalues tell us that \(A\) is indeed diagonalizable, and then it follows from Theorem Theorem 4.3.6 that \(a_n=x_1(4^n)+x_2(2)^n+x_3(-1)^n\) for some as-yet unknown constants \(x_1,x_2,x_3\text{.}\) Considering \(n=1\text{,}\) \(n=2\text{,}\) and \(n=3\text{,}\) we have the system of equations

\begin{align*} 4x_1+2x_2-x_3&=1\\ 16x_1+4x_2+x_3&=4\\ 64x_1+8x_2-x_3&=6\text{.} \end{align*}

This system can be solved using row reduction, and yields \(x_1=0\text{,}\) \(x_2=\frac{5}{6}\text{,}\) and \(x_3=\frac{2}{3}\text{.}\) Therefore \(a_n=\frac{5}{6}2^{n}+\frac{2}{3}(-1)^{n}\text{.}\) (We should compute several terms of the sequence with this formula and compare to terms of the sequence that come from using its recurrence relation as a check that we made no mistakes.)

Exercises 4.3.4 Exercises

1.

Solve the recurrence relation \(b_n=2b_{n-1}+3b_{n-2}\) where \(b_1=1\) and \(b_2=2\text{.}\) Use your solution to find \(b_{20}\text{.}\)

Solution

We need to diagonalize the matrix \(\begin{bmatrix}2&3\\1&0\end{bmatrix}\text{.}\) One possible diagonalization is

\begin{equation*} \begin{bmatrix}2&3\\1&0\end{bmatrix}=\begin{bmatrix}3&-1\\1&1\end{bmatrix}\begin{bmatrix}3&0\\0&-1\end{bmatrix}\frac{1}{4}\begin{bmatrix}1&1\\-1&3\end{bmatrix}\text{.} \end{equation*}

This tells us that

\begin{align*} b_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}3&-1\\1&1\end{bmatrix}\begin{bmatrix}3^{n-2}&0\\0&(-1)^{n-2}\end{bmatrix}\frac{1}{4}\begin{bmatrix}1&1\\-1&3\end{bmatrix}\colvector{2\\1}\\ &=\frac{1}{4}\begin{bmatrix}3&-1\end{bmatrix}\begin{bmatrix}3^{n-2}&0\\0&(-1)^{n-2}\end{bmatrix}\colvector{3\\1}\\ &=\frac{1}{4}\begin{bmatrix}3^{n-1}&(-1)^{n-1}\end{bmatrix}\colvector{3\\1}\\ &=\frac{1}{4}\left(3^{n}+(-1)^{n-1}\right)\text{.} \end{align*}

So \(b_{20}=\frac{1}{4}\left(3^{20}-1\right)=3486784400\text{.}\)

2.

Solve the recurrence relation \(c_n=3c_{n-1}+c_{n-2}\) where \(c_1=0\) and \(c_2=2\text{.}\) Use your solution to find \(c_{20}\text{.}\)

Solution

We need to diagonalize the matrix \(\begin{bmatrix}3&1\\1&0\end{bmatrix}\text{.}\) Its eigenvalues are \(\lambda=\frac{3+\sqrt{13}}{2}\) and \(\mu=\frac{3-\sqrt{13}}{2}\text{,}\) and one possible diagonalization is

\begin{equation*} \begin{bmatrix}3&1\\1&0\end{bmatrix}=\begin{bmatrix}\lambda&\mu\\1&1\end{bmatrix}\begin{bmatrix}\lambda&0\\0&\mu\end{bmatrix}\frac{1}{\sqrt{13}}\begin{bmatrix}1&-\mu\\-1&\lambda\end{bmatrix}\text{.} \end{equation*}

This tells us that

\begin{align*} c_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}\lambda&\mu\\1&1\end{bmatrix}\begin{bmatrix}\lambda^{n-2}&0\\0&\mu^{n-2}\end{bmatrix}\frac{1}{\sqrt{13}}\begin{bmatrix}1&-\mu\\-1&\lambda\end{bmatrix}\colvector{2\\0}\\ &=\frac{1}{\sqrt{13}}\begin{bmatrix}\lambda&\mu\end{bmatrix}\begin{bmatrix}\lambda^{n-2}&0\\0&\mu^{n-2}\end{bmatrix}\colvector{2\\-2}\\ &=\frac{1}{\sqrt{13}}\begin{bmatrix}\lambda^{n-1}&\mu^{n-1}\end{bmatrix}\colvector{2\\-2}\\ &=\frac{2}{\sqrt{13}}\left(\lambda^{n-1}-\mu^{n-1}\right)\\ &=\frac{2}{\sqrt{13}}\left(\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\right)\text{.} \end{align*}

So \(c_{20}=\frac{2}{\sqrt{13}}\left(\left(\frac{3+\sqrt{13}}{2}\right)^{19}-\left(\frac{3-\sqrt{13}}{2}\right)^{19}\right)=4006458938\text{.}\)

3.

Solve the recurrence relation \(d_n=2d_{n-1}-5d_{n-2}\) where \(d_1=1\) and \(d_2=8\text{.}\) Use your solution to find \(d_{20}\text{.}\)

Solution

We need to diagonalize the matrix \(\begin{bmatrix}2&-5\\1&0\end{bmatrix}\text{.}\) Its eigenvalues are \(\lambda=1+2i\) and \(\mu=1-2i\text{,}\) and one possible diagonalization is

\begin{equation*} \begin{bmatrix}2&-5\\1&0\end{bmatrix}=\begin{bmatrix}\lambda&\mu\\1&1\end{bmatrix}\begin{bmatrix}\lambda&0\\0&\mu\end{bmatrix}\frac{1}{4i}\begin{bmatrix}1&-\mu\\-1&\lambda\end{bmatrix}\text{.} \end{equation*}

This tells us that

\begin{align*} d_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}\lambda&\mu\\1&1\end{bmatrix}\begin{bmatrix}\lambda^{n-2}&0\\0&\mu^{n-2}\end{bmatrix}\frac{1}{4i}\begin{bmatrix}1&-\mu\\-1&\lambda\end{bmatrix}\colvector{8\\1}\\ &=\frac{1}{4i}\begin{bmatrix}\lambda&\mu\end{bmatrix}\begin{bmatrix}\lambda^{n-2}&0\\0&\mu^{n-2}\end{bmatrix}\colvector{7+2i\\-7+2i}\\ &=\frac{1}{4i}\begin{bmatrix}\lambda^{n-1}&\mu^{n-1}\end{bmatrix}\colvector{7+2i\\-7+2i}\\ &=\frac{1}{4i}\left((7+2i)\lambda^{n-1}+(-7+2i)\mu^{n-1}\right)\\ &=\frac{1}{4i}\left((7+2i)(1+2i)^{n-1}+(-7+2i)(1-2i)^{n-1}\right)\text{.} \end{align*}

In the following, we use a trigonometric method to evaluate powers of complex numbers. There are other ways to evaluate such powers, but this way works well:

\begin{align*} d_{20}&=\frac{1}{4i}\left((7+2i)(1+2i)^{19}+(-7+2i)(1-2i)^{19}\right)\\ &=\frac{\sqrt{5}^{19}}{4i}\left((7+2i)\left(\frac{1+2i}{\sqrt{5}}\right)^{19}+(-7+2i)\left(\frac{1-2i}{\sqrt{5}}\right)^{19}\right)\\ &=\frac{\sqrt{5}^{19}}{4i}\left((7+2i)\left(e^{i\arctan(2)}\right)^{19}+(-7+2i)\left(e^{-i\arctan(2)}\right)^{19}\right)\\ &=\frac{\sqrt{5}^{19}}{4i}\left((7+2i)e^{19i\arctan(2)}+(-7+2i)e^{-19i\arctan(2)}\right)\\ &=\frac{\sqrt{5}^{19}}{4i}\left(14i\sin(19\arctan(2))+4i\cos(19\arctan(2))\right)\\ &=\sqrt{5}^{19}\left(\frac{7}{2}\sin(19\arctan(2))+\cos(19\arctan(2))\right)\\ &=9959262\text{.} \end{align*}

These exercises use the same recurrence relation that the Fibonacci numbers have. You can use the work from Example 4.3.5 to assist with your calculations.

4.

Solve the recurrence relation from Example Example 4.3.2 that gives the number of ancestors of level \(n\) for a male honeybee. How many great\(^{20}\) grandparents does a male honeybee have?

Solution

Since the recurrence relation is the same as for the Fibonacci numbers, but now we have a series with initial terms \(\set{a_1,a_2,\ldots}=\set{1,2,\ldots}\text{,}\) we can write

\begin{align*} \colvector{a_n\\a_{n-1}}&=\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G&0\\0&g\end{bmatrix}^{n-2}\frac{1}{\sqrt{5}}\begin{bmatrix}1&-g\\-1&G\end{bmatrix}\colvector{2\\1}\\ &=\frac{1}{\sqrt{5}}\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G^{n-2}&0\\0&g^{n-2}\end{bmatrix}\colvector{2-g\\-2+G}\\ &=\frac{1}{\sqrt{5}}\begin{bmatrix}G^{n-1}&g^{n-1}\\*&*\end{bmatrix}\colvector{1+G\\-1-g}\\ &=\frac{1}{\sqrt{5}}\colvector{(1+G)G^{n-1}-(1+g)g^{n-1}\\*}\text{.} \end{align*}

And so we have found:

\begin{align*} a_n&=\frac{1}{\sqrt{5}}\left((1+G)G^{n-1}-(1+g)g^{n-1}\right)\\ &=\frac{1}{\sqrt{5}}\left(\left(\frac{3+\sqrt{5}}{2}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{3-\sqrt{5}}{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right)\text{.} \end{align*}

We can use this to compute how many great\(^{20}\) grandparents a male honeybee has. Note that a great\(^{0}\) grandparent is already a level 2 ancestor, so we are looking for \(a_{22}\text{.}\)

\begin{align*} a_{22}&=\frac{1}{\sqrt{5}}\left(\left(\frac{3+\sqrt{5}}{2}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{21}-\left(\frac{3-\sqrt{5}}{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{21}\right)\\ &=28657\text{.} \end{align*}

So a male honeybee has 28657 ancestors at the 22nd level. That is, he has 28657 great\(^{20}\) grandparents.

5.

The Lucas numbers arise in nature for similar reasons to the Fibonacci numbers. They have the same recurrence relation \(\ell_n=\ell_{n-1}+\ell_{n-2}\text{,}\) but the initial terms are \(\set{\ell_1,\ell_2,\ldots}=\set{2,1,\ldots}\text{.}\) Find a formula for the \(n\)th Lucas number similar to the formula for the Fibonacci numbers given in (4.3.1).

Solution

Since the recurrence relation is the same as for the Fibonacci numbers, but now we have a series with initial terms \(\set{\ell_1,\ell_2,\ldots}=\set{2,1,\ldots}\text{,}\) we can write

\begin{align*} \colvector{\ell_n\\\ell_{n-1}}&=\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G&0\\0&g\end{bmatrix}^{n-2}\frac{1}{\sqrt{5}}\begin{bmatrix}1&-g\\-1&G\end{bmatrix}\colvector{1\\2}\\ &=\frac{1}{\sqrt{5}}\begin{bmatrix}G&g\\1&1\end{bmatrix}\begin{bmatrix}G^{n-2}&0\\0&g^{n-2}\end{bmatrix}\colvector{1-2g\\-1+2G}\\ &=\frac{1}{\sqrt{5}}\begin{bmatrix}G^{n-1}&g^{n-1}\\*&*\end{bmatrix}\colvector{G-g\\G-g}\\ &=\frac{G-g}{\sqrt{5}}\colvector{G^{n-1}+g^{n-1}\\*}\\ &=\colvector{G^{n-1}+g^{n-1}\\*}\text{.} \end{align*}

And so we have found:

\begin{align*} \ell_n&=G^{n-1}+g^{n-1}\\ &=\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}+\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\text{.} \end{align*}
6.

Solve the recurrence relation from Example Example 4.3.4 that gives the number of fruit clusters on an elderberry branch after \(n\) years. How many berry clusters will a branch and its children be producing when the branch is \(6\) years old?

Solution

We have to solve the recurrence relation \(b_n=b_{n-1}+2b_{n-2}\) with \(\set{b_1,b_2,\ldots}=\set{1,4,\ldots}\text{.}\) We need to diagonalize the matrix \(\begin{bmatrix}1&2\\1&0\end{bmatrix}\text{.}\) One possible diagonalization is

\begin{equation*} \begin{bmatrix}1&2\\1&0\end{bmatrix}=\begin{bmatrix}2&-1\\1&1\end{bmatrix}\begin{bmatrix}2&0\\0&-1\end{bmatrix}\frac{1}{3}\begin{bmatrix}1&1\\-1&2\end{bmatrix}\text{.} \end{equation*}

This tells us that

\begin{align*} b_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}2&-1\\1&1\end{bmatrix}\begin{bmatrix}2^{n-2}&0\\0&(-1)^{n-2}\end{bmatrix}\frac{1}{3}\begin{bmatrix}1&1\\-1&2\end{bmatrix}\colvector{4\\1}\\ &=\frac{1}{3}\begin{bmatrix}2&-1\end{bmatrix}\begin{bmatrix}2^{n-2}&0\\0&(-1)^{n-2}\end{bmatrix}\colvector{5\\-2}\\ &=\frac{1}{3}\begin{bmatrix}2^{n-1}&(-1)^{n-1}\end{bmatrix}\colvector{5\\-2}\\ &=\frac{1}{3}\left(5(2)^{n-1}-2(-1)^{n-1}\right)\text{.} \end{align*}

So \(b_{6}=\frac{1}{3}\left(5(2)^{5}+2\right)=54\text{.}\) If the recurrence holds, there will be \(54\) berry clusters in the \(6\)th year.

7.

Solve the recurrence relation \(b_n=6b_{n-1}+b_{n-2}-30b_{n-3}\) where \(b_1=0\text{,}\) \(b_2=1\text{,}\) and \(b_3=2\text{.}\)

Solution

The associated matrix to this system is \(3\times3\text{,}\) and so an explicit diagonalization may be tedious. Instead, we use the last part of Theorem Theorem 4.3.6. We consider the matrix \(A=\begin{bmatrix}6&1&-30\\1&0&0\\0&1&0\end{bmatrix}\) and calculate its eigenvalues: \(5,3,-2\text{.}\) Since these are distinct, \(A\) is diagonalizable, and the second part of Theorem Theorem 4.3.6 tells us that \(b_n=x_1(5)^n+x_2(3)^n+x_3(-2)^n\text{.}\) The initial terms of the sequence \(\set{b_n}\) provide us with the system of equations:

\begin{align*} 5x_1+3x_2-2x_3&=0\\ 25x_1+9x_2+4x_3&=1\\ 125x_1+27x_2-8x_3&=2\text{.} \end{align*}

This system can be solved using row reduction, yielding \(x_1=\frac{1}{70}\text{,}\) \(x_2=\frac{1}{30}\text{,}\) and \(x_3=\frac{3}{35}\text{.}\) So

\begin{equation*} b_n=\frac{5^n}{70}+\frac{3^n}{30}+\frac{3(-2)^n}{35}\text{.} \end{equation*}
8.

Solve the recurrence relation \(c_n=c_{n-1}+3c_{n-2}+c_{n-3}\) where \(c_1=1\text{,}\) \(c_2=1\text{,}\) and \(c_3=1\text{.}\)

Solution

The associated matrix to this system is \(3\times3\text{,}\) and so an explicit diagonalization may be tedious. Instead, we use the last part of Theorem Theorem 4.3.6. We consider the matrix \(A=\begin{bmatrix}1&3&1\\1&0&0\\0&1&0\end{bmatrix}\) and calculate its eigenvalues: \(1+\sqrt{2},1-\sqrt{2},-1\text{.}\) Since these are distinct, \(A\) is diagonalizable, and the second part of Theorem Theorem 4.3.6 tells us that \(c_n=x_1\left(1+\sqrt{2}\right)^n+x_2\left(1-\sqrt{2}\right)^n+x_3(-1)^n\text{.}\) The initial terms of the sequence \(\set{c_n}\) provide us with the system of equations:

\begin{align*} \left(1+\sqrt{2}\right)x_1+\left(1-\sqrt{2}\right)x_2-x_3&=1\\ \left(3+2\sqrt{2}\right)x_1+\left(3-2\sqrt{2}\right)x_2+x_3&=1\\ \left(7+5\sqrt{2}\right)x_1+\left(7-5\sqrt{2}\right)x_2-x_3&=1\text{.} \end{align*}

This system can be solved using row reduction, yielding \(x_1=-2+\frac{3\sqrt{2}}{2}\text{,}\) \(x_2=-2-\frac{3\sqrt{2}}{2}\text{,}\) and \(x_3=1\text{.}\) So

\begin{equation*} c_n=\left(-2+\frac{3\sqrt{2}}{2}\right)\left(1+\sqrt{2}\right)^n+\left(-2-\frac{3\sqrt{2}}{2}\right)\left(1-\sqrt{2}\right)^n+(-1)^n\text{.} \end{equation*}
9.

Solve the recurrence relation \(d_n=2d_{n-1}+d_{n-2}-d_{n-3}\) where \(d_1=2\text{,}\) \(d_2=1\text{,}\) and \(d_3=4\text{.}\) Warning: the characteristic polynomial for the matrix in this exercise does not have rational roots. Either find approximate roots, or use the Cardano/Tartaglia/del Ferro solution to cubic equations to find exact roots.

Solution

The associated matrix to this system is \(3\times3\text{.}\) We will use the explicit diagonalization provided by Theorem Theorem 4.3.6 and use a formula for inverting a Vandermonde matrix. (Alternatively, you could give up on finding an exact solution and work entirely with decimal approximations.) We consider the matrix \(A=\begin{bmatrix}2&1&-1\\1&0&0\\0&1&0\end{bmatrix}\) and calculate its eigenvalues using the Cardano/Tartaglia/del Ferro solution to cubic equations:

\begin{align*} \kappa&=\frac{2}{3}+\frac{1}{3}\sqrt[3]{\frac{7+21i\sqrt{3}}{2}}+\frac{1}{3}\sqrt[3]{\frac{7-21i\sqrt{3}}{2}}\\ &\approx2.24698\ldots\\ \lambda&=\frac{2}{3}+\frac{e^{4\pi i/3}}{3}\sqrt[3]{\frac{7+21i\sqrt{3}}{2}}+\frac{e^{2\pi i/3}}{3}\sqrt[3]{\frac{7-21i\sqrt{3}}{2}}\\ &\approx0.55496\ldots\\ \mu&=\frac{2}{3}+\frac{e^{2\pi i/3}}{3}\sqrt[3]{\frac{7+21i\sqrt{3}}{2}}+\frac{e^{4\pi i/3}}{3}\sqrt[3]{\frac{7-21i\sqrt{3}}{2}}\\ &\approx-0.80194\ldots\text{.} \end{align*}

Since these are distinct, \(A\) is diagonalizable. Theorem Theorem 4.3.6 tells us that

\begin{align*} d_n&=\transpose{\colvector{1\\0\\0}}\begin{bmatrix}\kappa^2&\lambda^2&\mu^2\\\kappa&\lambda&\mu\\1&1&1\end{bmatrix}\begin{bmatrix}\kappa&0&0\\0&\lambda&0\\0&0&\mu\end{bmatrix}^{n-3}\inverse{\begin{bmatrix}\kappa^2&\lambda^2&\mu^2\\\kappa&\lambda&\mu\\1&1&1\end{bmatrix}}\colvector{4\\1\\2}\\ &=\transpose{\colvector{\kappa^2\\\lambda^2\\\mu^2}}\begin{bmatrix}\kappa^{n-3}&0&0\\0&\lambda^{n-3}&0\\0&0&\mu^{n-3}\end{bmatrix}\frac{\begin{bmatrix}\lambda-\mu&-\lambda^2+\mu^2&\lambda\mu(\lambda-\mu)\\-\kappa+\mu&\kappa^2-\mu^2&-\kappa\mu(\kappa-\mu)\\\kappa-\lambda&-\kappa^2+\lambda^2&\kappa\lambda(\kappa-\lambda)\end{bmatrix}}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\colvector{4\\1\\2}\\ &=\frac{\begin{bmatrix}\kappa^{n-1}&\lambda^{n-1}&\mu^{n-1}\end{bmatrix}}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\colvector{4\lambda-4\mu-\lambda^2+\mu^2+2\lambda\mu(\lambda-\mu)\\-4\kappa+4\mu+\kappa^2-\mu^2-2\kappa\mu(\kappa-\mu)\\4\kappa-4\lambda-\kappa^2+\lambda^2+2\kappa\lambda(\kappa-\lambda)}\\ &=\frac{4\lambda-4\mu-\lambda^2+\mu^2+2\lambda\mu(\lambda-\mu)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\kappa^{n-1}\\ &\phantom{{}={}}+\frac{-4\kappa+4\mu+\kappa^2-\mu^2-2\kappa\mu(\kappa-\mu)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\lambda^{n-1}\\ &\phantom{{}={}}+\frac{4\kappa-4\lambda-\kappa^2+\lambda^2+2\kappa\lambda(\kappa-\lambda)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\mu^{n-1}\\ &\approx(0.6507083\ldots)(2.2469796\ldots)^{n-1}\\ &\phantom{{}={}}+(0.45686604\ldots)(0.55495813\ldots)^{n-1}\\ &\phantom{{}={}}+(0.89242566\ldots)(-0.8019377\ldots)^{n-1}\text{.} \end{align*}

Note that since the latter two eigenvalues have absolute value smaller than \(1\text{,}\) the corresponding terms in the formula for \(d_n\) are negligible when \(n\) is large. So for large \(n\text{,}\)

\begin{align*} d_n&=\operatorname{round}\left(\frac{4\lambda-4\mu-\lambda^2+\mu^2+2\lambda\mu(\lambda-\mu)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\kappa^{n-1}\right)\\ &\approx\operatorname{round}\left((0.6507083\ldots)(2.2469796\ldots)^{n-1}\right)\text{.} \end{align*}

We can verify by inspection that this holds for \(n\geq4\text{.}\)

10.

The Tribonacci numbers have the first few terms \(\set{t_1,t_2,t_3,\ldots}=\set{1,1,2,\ldots}\) and satisfy the recursion \(t_n=t_{n-1}+t_{n-2}+t_{n-3}\text{.}\) Find a formula for the \(n\)th Tribonacci number.

Solution

The associated matrix to this system is \(3\times3\text{.}\) We will use the explicit diagonalization provided by Theorem Theorem 4.3.6 and use a formula for inverting a Vandermonde matrix. (Alternatively, you could give up on finding an exact solution and work entirely with decimal approximations.) We consider the matrix \(A=\begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}\) and calculate its eigenvalues using the Cardano/Tartaglia/del Ferro solution to cubic equations:

\begin{align*} \kappa&=\frac{1}{3}+\frac{1}{3}\sqrt[3]{19+3\sqrt{33}}+\frac{1}{3}\sqrt[3]{19-3\sqrt{33}}\\ &\approx1.8392867\ldots\\ \lambda&=\frac{1}{3}+\frac{e^{4\pi i/3}}{3}\sqrt[3]{19+3\sqrt{33}}+\frac{e^{2\pi i/3}}{3}\sqrt[3]{19-3\sqrt{33}}\\ &\approx-0.41964\ldots-0.60629\ldots{}i\\ \mu&=\frac{1}{3}+\frac{e^{2\pi i/3}}{3}\sqrt[3]{19+3\sqrt{33}}+\frac{e^{4\pi i/3}}{3}\sqrt[3]{19-3\sqrt{33}}\\ &\approx-0.41964\ldots+0.60629\ldots{}i\text{.} \end{align*}

Since these are distinct, \(A\) is diagonalizable. Theorem Theorem 4.3.6 tells us that

\begin{align*} t_n&=\transpose{\colvector{1\\0\\0}}\begin{bmatrix}\kappa^2&\lambda^2&\mu^2\\\kappa&\lambda&\mu\\1&1&1\end{bmatrix}\begin{bmatrix}\kappa&0&0\\0&\lambda&0\\0&0&\mu\end{bmatrix}^{n-3}\inverse{\begin{bmatrix}\kappa^2&\lambda^2&\mu^2\\\kappa&\lambda&\mu\\1&1&1\end{bmatrix}}\colvector{2\\1\\1}\\ &=\transpose{\colvector{\kappa^2\\\lambda^2\\\mu^2}}\begin{bmatrix}\kappa^{n-3}&0&0\\0&\lambda^{n-3}&0\\0&0&\mu^{n-3}\end{bmatrix}\frac{\begin{bmatrix}\lambda-\mu&-\lambda^2+\mu^2&\lambda\mu(\lambda-\mu)\\-\kappa+\mu&\kappa^2-\mu^2&-\kappa\mu(\kappa-\mu)\\\kappa-\lambda&-\kappa^2+\lambda^2&\kappa\lambda(\kappa-\lambda)\end{bmatrix}}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\colvector{2\\1\\1}\\ &=\frac{\begin{bmatrix}\kappa^{n-1}&\lambda^{n-1}&\mu^{n-1}\end{bmatrix}}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\colvector{2\lambda-2\mu-\lambda^2+\mu^2+\lambda\mu(\lambda-\mu)\\-2\kappa+2\mu+\kappa^2-\mu^2-\kappa\mu(\kappa-\mu)\\2\kappa-2\lambda-\kappa^2+\lambda^2+\kappa\lambda(\kappa-\lambda)}\\ &=\frac{2\lambda-2\mu-\lambda^2+\mu^2+\lambda\mu(\lambda-\mu)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\kappa^{n-1}\\ &\phantom{{}={}}+\frac{-2\kappa+2\mu+\kappa^2-\mu^2-\kappa\mu(\kappa-\mu)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\lambda^{n-1}\\ &\phantom{{}={}}+\frac{2\kappa-2\lambda-\kappa^2+\lambda^2+\kappa\lambda(\kappa-\lambda)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\mu^{n-1}\\ &\approx(0.6184199\ldots)(1.83929286\ldots)^{n-1}\\ &\phantom{{}={}}+(0.19079\ldots+0.0187\ldots{}i)(-0.4196433\ldots-0.6062907\ldots{}i)^{n-1}\\ &\phantom{{}={}}+(0.19079\ldots-0.0187\ldots{}i)(-0.4196433\ldots+0.6062907\ldots{}i)^{n-1}\text{.} \end{align*}

Note that since the latter two eigenvalues have absolute value smaller than \(1\text{,}\) the corresponding terms in the formula for \(t_n\) are negligible when \(n\) is large. So for large \(n\text{,}\)

\begin{align*} t_n&=\operatorname{round}\left(\frac{2\lambda-2\mu-\lambda^2+\mu^2+\lambda\mu(\lambda-\mu)}{(\kappa-\lambda)(\kappa-\mu)(\lambda-\mu)}\kappa^{n-1}\right)\\ &\approx\operatorname{round}\left((0.6184199\ldots)(1.83929286\ldots)^{n-1}\right)\text{.} \end{align*}

We can verify by inspection that this holds for \(n\geq1\text{.}\)

11.

A certain species of rat typically has a life span of just over one year, and females can birth a litter every three months. When a female is born, three months later her first litter will have four pups (two female and two male). Her three subsequent litters will each have six pups (three female and three male), and then she will have no more litters. When a ship laid anchor off the shore of a remote tropical island, eight very young rats of this type (four female and four male) jumped ship and swam to colonize the island. From that point on, every three months, more litters were born. This island has no predators, and for several years the rat population grew and had no constraints from food or space limitations.

  1. Use this information to formulate a linear recurrence relation for \(r_n\text{,}\) the number of female pups born in the \(n\)th litter. To be clear, \(r_1=8\text{,}\) corresponding to the \(8\) female pups born to the original four females three months after the colonization.
  2. If you have the right tools, solve the recurrence and find a formula for \(r_n\text{.}\) The associated matrix is \(4\times4\text{,}\) so it's not likely that you will solve this recurrence by hand. Only two of the four eigenvalues are real. You will probably need to use approximate eigenvalues and eigenvectors.
Solution

In year \(n\text{,}\) the previous litter's female rats will birth a litter that has two females. Each of the three previous generations will give birth to litters with three females. This tells us that

\begin{equation*} r_n=2r_{n-1}+3r_{n-2}+3r_{n-3}+3r_{n-4}\text{.} \end{equation*}

The associated matrix has characteristic polynomial \(t^4-2t^3-3t^2-3t-3\text{,}\) and its eigenvalues are

\begin{align*} \kappa&=1+\sqrt[3]{\frac{5+\sqrt{21}}{2}}+\sqrt[3]{\frac{5-\sqrt{21}}{2}}\\ &\approx3.27901\ldots\\ \lambda&=1+e^{4\pi i/3}\sqrt[3]{\frac{5+\sqrt{21}}{2}}+e^{2\pi i/3}\sqrt[3]{\frac{5-\sqrt{21}}{2}}\\ &\approx-0.139509\ldots-0.946279\ldots{}i\\ \mu&=1+e^{2\pi i/3}\sqrt[3]{\frac{5+\sqrt{21}}{2}}+e^{4\pi i/3}\sqrt[3]{\frac{5-\sqrt{21}}{2}}\\ &\approx-0.139509\ldots+0.946279\ldots{}i\\ \nu&=-1\text{.} \end{align*}

Since these are distinct, \(A\) is diagonalizable. Inverting the matrix \(P\) from Theorem Theorem 4.3.6 will be rather difficult here. The formula for the inverse of a Vandermonde matrix of dimension \(4\) or greater is difficult to apply. Instead, we relax the search for an exact solution to a search for an approximate solution, using decimal approximations. We'll do this with the last part of Theorem Theorem 4.3.6. The theorem tells us that

\begin{equation*} r_n=x_1\kappa^n+x_2\lambda^n+x_3\mu^n+x_4(-1)^n\text{.} \end{equation*}

Using the first terms of the sequence \(\set{r_1,r_2,r_3,r_4,\ldots}=\set{8,28,92,304,\ldots}\text{,}\) and using decimal approximations, we have the system of equations

\begin{align*} 3.279018x_1+(-0.139509-0.946279i)x_2+ (-0.139509+0.946279i)x_3-x_4&=8\\ 10.75196x_1+(-0.875982+0.264029i)x_2+ (-0.875982-0.264029i)x_3+x_4&=28\\ 35.25589x_1+(0.372053+0.792089i) x_2+ (0.372053-0.792089i) x_3-x_4&=92\\ 115.6047x_1+(0.697632-0.462570i) x_2+ (0.697632+0.462570i) x_3+x_4&=304\text{,} \end{align*}

which can be solved using row reduction. Be careful when row reducing with approximate values. If at some stage, you find a value close to zero, it could be that the value should be zero, but the approximation has thrown it off by a small bit. The solution is approximately

\begin{align*} r_n&\approx2.61942\ldots(3.27901\ldots)^n\\ &\phantom{{}={}}+(0.404576\ldots+0.0502961\ldots{}i)(-0.139509\ldots-0.946279\ldots{}i)^n\\ &\phantom{{}={}}+(0.404576\ldots-0.0502961\ldots{}i)(-0.139509\ldots+0.946279\ldots{}i)^n\\ &\phantom{{}={}}+0.571437\ldots(-1)^n\text{.} \end{align*}

Not all matrices are diagonalizable. This block of exercises addresses recurrence relations that lead to non-diagonalizable \(2\times2\) matrices.

12.

Solve the recurrence relation \(u_n=6u_{n-1}-9u_{n-2}\) with \(u_1=2\) and \(u_2=5\text{.}\) You will not be able to diagonalize the associated matrix to this recursion. However with the right change of basis matrix, you can express the matrix in Jordan canonical form (see Section Section 3.3). This will show the matrix is similar to a matrix of the form \(\begin{bmatrix}\lambda&1\\0&\lambda\end{bmatrix}\text{.}\) Although this is not diagonal, it is still easy to raise matrices like this to large powers.

Solution

We need to investigate the matrix \(A=\begin{bmatrix}6&-9\\1&0\end{bmatrix}\text{.}\) We find its characteristic polynomial to be \(x^2-6x+9\text{,}\) with \(3\) as a repeated eigenvalue. \(A\) can't be diagonalizable, or else it would be similar to \(3I\text{,}\) in which case it would have to equal \(3I\text{.}\) So \(A\) is similar to a matrix of the form \(\begin{bmatrix}3&1\\0&3\end{bmatrix}\text{.}\) There are many ways to explicitly realize this relationship, but one way is

\begin{equation*} \begin{bmatrix}6&-9\\1&0\end{bmatrix}=\begin{bmatrix}3&4\\1&1\end{bmatrix}\begin{bmatrix}3&1\\0&3\end{bmatrix}\begin{bmatrix}-1&4\\1&-3\end{bmatrix}\text{.} \end{equation*}

Now we can apply Theorem Theorem 4.3.6:

\begin{align*} u_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}3&4\\1&1\end{bmatrix}\begin{bmatrix}3&1\\0&3\end{bmatrix}^{n-2}\begin{bmatrix}-1&4\\1&-3\end{bmatrix}\colvector{5\\2}\\ &=\begin{bmatrix}3&4\end{bmatrix}\begin{bmatrix}3^{n-2}&(n-2)3^{n-3}\\0&3^{n-2}\end{bmatrix}\colvector{3\\-1}\\ &=\begin{bmatrix}3^{n-1}&(n-2)3^{n-2}+4\cdot3^{n-2}\end{bmatrix}\colvector{3\\-1}\\ &=3^{n}-(n+2)3^{n-2}\text{.} \end{align*}
13.

Since \(2\times2\) matrices are either diagonalizable over \(\complexes\) or similar to a matrix of the form \(\begin{bmatrix}\lambda&1\\0&\lambda\end{bmatrix}\text{,}\) we can explicitly solve a generic linear recursion of depth \(2\text{.}\) Let \(c_1, c_2, a_1, a_2\) be four real numbers.

  1. If \(\set{a_1,a_2,\ldots}\) are the first two terms to a sequence that satisfies the recursion \(a_n=c_1a_{n-1}+c_2a_{n-2}\text{,}\) and \(c_1^2+4c_2\neq0\text{,}\) solve the recursion. (Find a formula for \(a_n\) in terms of \(c_1, c_2, a_1, a_2\text{.}\))
  2. If \(\set{a_1,a_2,\ldots}\) are the first two terms to a sequence that satisfies the recursion \(a_n=c_1a_{n-1}+c_2a_{n-2}\text{,}\) and \(c_1^2+4c_2=0\text{,}\) solve the recursion. (Find a formula for \(a_n\) in terms of \(c_1, c_2, a_1, a_2\text{.}\))
Solution

  1. The matrix \(\begin{bmatrix}c_1&c_2\\1&0\end{bmatrix}\) has eigenvalues \(\lambda=\frac{c_1+\sqrt{c_1^2+4c_2}}{2}\) and \(\mu=\frac{c_1-\sqrt{c_1^2+4c_2}}{2}\text{.}\) Since \(c_1^2+4c_2\neq0\text{,}\) the eigenvalues are distinct, and so \(A\) is diagonalizable. It will be convenient to let \(\sigma=\frac{1}{\sqrt{c_1^2+4c_2}}\text{.}\) Theorem Theorem 4.3.6 tells us that

    \begin{align*} a_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}\lambda&\mu\\1&1\end{bmatrix}\begin{bmatrix}\lambda&0\\0&\mu\end{bmatrix}^{n-2}\frac{1}{\sigma}\begin{bmatrix}1&-\mu\\-1&\lambda\end{bmatrix}\colvector{a_2\\a_1}\\ &=\frac{1}{\sigma}\begin{bmatrix}\lambda&\mu\end{bmatrix}\begin{bmatrix}\lambda^{n-2}&0\\0&\mu^{n-2}\end{bmatrix}\colvector{a_2-\mu a_1\\-a_2+\lambda a_1}\\ &=\frac{1}{\sigma}\begin{bmatrix}\lambda^{n-1}&\mu^{n-1}\end{bmatrix}\colvector{a_2-\mu a_1\\-a_2+\lambda a_1}\\ &=\frac{1}{\sigma}\left(\left(a_2-\mu a_1\right)\lambda^{n-1}+\left(-a_2+\lambda a_1\right)\mu^{n-1}\right)\text{.}\\ &=\frac{1}{\sqrt{c_1^2+4c_2}}\left(\left(a_2-\frac{c_1-\sqrt{c_1^2+4c_2}}{2}a_1\right)\left(\frac{c_1+\sqrt{c_1^2+4c_2}}{2}\right)^{n-1}\right.\\ &\phantom{{}={}}+\left.\left(-a_2+\frac{c_1+\sqrt{c_1^2+4c_2}}{2}a_1\right)\left(\frac{c_1-\sqrt{c_1^2+4c_2}}{2}\right)^{n-1}\right)\text{.} \end{align*}

  2. The matrix \(\begin{bmatrix}c_1&c_2\\1&0\end{bmatrix}\) has only one eigenvalue, \(\lambda=\frac{c_1}{2}\text{,}\) since \(c_1^2+4c_2=0\text{.}\) \(A\) cannot be diagonalizable, since if it were, it would be similar to a scalar matrix and therefore would have to be a scalar matrix. So \(A\) is similar to the matrix \(\begin{bmatrix}\lambda&1\\0&\lambda\end{bmatrix}\text{.}\) One explicit realization of this similarity is given by

    \begin{equation*} \begin{bmatrix}c_1&c_2\\1&0\end{bmatrix}=\begin{bmatrix}\lambda&1+\lambda\\1&1\end{bmatrix}\begin{bmatrix}\lambda&1\\0&\lambda\end{bmatrix}\begin{bmatrix}-1&1+\lambda\\1&\lambda\end{bmatrix}\text{.} \end{equation*}

    Theorem Theorem 4.3.6 tells us that

    \begin{align*} u_n&=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}\lambda&1+\lambda\\1&1\end{bmatrix}\begin{bmatrix}\lambda&1\\0&\lambda\end{bmatrix}^{n-2}\begin{bmatrix}-1&1+\lambda\\1&\lambda\end{bmatrix}\colvector{a_2\\a_1}\\ &=\begin{bmatrix}\lambda&1+\lambda\end{bmatrix}\begin{bmatrix}\lambda^{n-2}&(n-2)\lambda^{n-3}\\0&\lambda^{n-2}\end{bmatrix}\colvector{-a_2+\left(1+\lambda\right)a_1\\a_2+\lambda a_1}\\ &=\begin{bmatrix}\lambda^{n-1}&(n-2)\lambda^{n-2}+\left(1+\lambda\right)\lambda^{n-2}\end{bmatrix}\colvector{-a_2+\left(1+\lambda\right)a_1\\a_2+\lambda a_1}\\ &=\left(-a_2+\left(1+\lambda\right)a_1\right)\lambda^{n-1}+\left(a_2+\lambda a_1\right)\left(n-1+\lambda\right)\lambda^{n-2}\text{.}\\ &=\left(-a_2+a_1+\frac{c_1}{2}a_1\right)\left(\frac{c_1}{2}\right)^{n-1}+\left(a_2+\frac{c_1}{2}a_1\right)\left(n-1+\frac{c_1}{2}\right)\left(\frac{c_1}{2}\right)^{n-2}\text{.} \end{align*}

These exercises make use of the formula in Equation (4.3.1). They don't necessarily require linear algebra, but since we found that formula, we might as well have some fun with it. These exercises may require knowledge of geometric sums and series.

14.

Encode the Fibonacci numbers into decimals and add them in the following way:

\begin{align*} &\phantom{{}+{}}0.1\\ &+0.01\\ &+0.002\\ &+0.0003\\ &+0.00005\\ &+0.000008\\ &+0.0000013\\ &\phantom{+{}}\vdots \end{align*}

What is the sum? (The answer can be expressed as a certain rational number.)

Solution

We have been asked to find the value of \(\sum_{n=1}^{\infty}\frac{f_n}{10^n}\text{.}\)

\begin{align*} \sum_{n=1}^{\infty}\frac{f_n}{10^n}&=\sum_{n=1}^{\infty}\frac{\frac{1}{\sqrt{5}}\left(G^n-g^n\right)}{10^n}\\ &=\frac{1}{\sqrt{5}}\sum_{n=1}^{\infty}\left(\left(\frac{G}{10}\right)^n-\left(\frac{g}{10}\right)^n\right)\\ &=\frac{1}{\sqrt{5}}\left(\frac{\frac{G}{10}}{1-\frac{G}{10}}-\frac{\frac{g}{10}}{1-\frac{g}{10}}\right)\\ &=\frac{1}{\sqrt{5}}\left(\frac{G}{10-G}-\frac{g}{10-g}\right)\\ &=\frac{1}{\sqrt{5}}\frac{10G-10g}{100-10G-10g+Gg}\\ &=\frac{1}{\sqrt{5}}\frac{10\sqrt{5}}{100-10G-10(1-G)+G(1-G)}\\ &=\frac{10}{100-10-1}\\ &=\frac{10}{89} \end{align*}
15.

Find the limit of the ratio of two consecutive Fibonacci numbers:

\begin{equation*} \lim\limits_{n\to\infty}\frac{f_{n+1}}{f_n}\text{.} \end{equation*}
Solution
\begin{align*} \lim_{n\to\infty}\frac{f_{n+1}}{f_n}&=\lim_{n\to\infty}\frac{\frac{1}{\sqrt{5}}\left(G^{n+1}-g^{n+1}\right)}{\frac{1}{\sqrt{5}}\left(G^{n}-g^{n}\right)}\\ &=\lim_{n\to\infty}\frac{G^{n+1}-g^{n+1}}{G^{n}-g^{n}}\\ &=\lim_{n\to\infty}\frac{G-g\left(\frac{g}{G}\right)^n}{1-\left(\frac{g}{G}\right)^{n}}\\ &=\frac{G-0}{1-0}\\ &=G \end{align*}
16.

Show that for the Fibonacci numbers \(\set{f_n}\text{,}\)

\begin{equation*} f_{n-1}^2+f_n^2=f_{2n-1}\text{.} \end{equation*}
Solution
\begin{align*} f_{n-1}^2+f_n^2&=\left(\frac{1}{\sqrt{5}}\left(G^{n-1}-g^{n-1}\right)\right)^2+\left(\frac{1}{\sqrt{5}}\left(G^{n}-g^{n}\right)\right)^2\\ &=\frac{1}{5}\left(G^{2n-2}-2g^{n-1}G^{n-1}+g^{2n-2}\right)+\frac{1}{5}\left(G^{2n}-2g^{n}G^{n}+g^{2n}\right)\\ &=\frac{1}{5}\left(G^{2n-2}-2g^{n-1}G^{n-1}+g^{2n-2}+G^{2n}-2g^{n}G^{n}+g^{2n}\right)\\ &=\frac{1}{5}\left(G^{2n-1}\left(\frac{1}{G}+G\right)-2g^{n-1}G^{n-1}(1+gG)+g^{2n-1}\left(\frac{1}{g}+g\right)\right)\\ &=\frac{1}{5}\left(G^{2n-1}\sqrt{5}-g^{2n-1}\sqrt{5}\right)\\ &=\frac{1}{\sqrt{5}}\left(G^{2n-1}-g^{2n-1}\right)\\ &=f_{2n-1} \end{align*}