3.4E: An Application to Linear Recurrences Exercises

Exercises for 1

solutions

2

Solve the following linear recurrences.

1. \(x_{k+2} = 3x_{k} + 2x_{k+1}\), where \(x_{0} = 1\) and \(x_{1} = 1\).
2. \(x_{k+2} = 2x_{k} - x_{k+1}\), where \(x_{0} = 1\) and \(x_{1} = 2\).
3. \(x_{k+2} = 2x_{k} + x_{k+1}\), where \(x_{0} = 0\) and \(x_{1} = 1\).
4. \(x_{k+2} = 6x_{k} - x_{k+1}\), where \(x_{0} = 1\) and \(x_{1} = 1\).

2. \(x_k = \frac{1}{3} \left[ 4 - (-2)^k \right]\)
3. \(x_k = \frac{1}{5} \left[ 2^{k+2} + (-3)^k \right]\)

Solve the following linear recurrences.

1. \(x_{k+3} = 6x_{k+2} - 11x_{k+1} + 6x_{k}\), where \(x_{0} = 1\), \(x_{1} = 0\), and \(x_{2} = 1\).
2. \(x_{k+3} = -2x_{k+2} + x_{k+1} + 2x_{k}\), where \(x_{0} = 1\), \(x_{1} = 0\), and \(x_{2} = 1\).

[Hint: Use \(\mathbf{v}_k = \left[ \begin{array}{c} x_k \\ x_{k+1}\\ x_{k+2} \end{array}\right]\).]

2. \(x_k = \frac{1}{2} \left[ (-1)^k + 1 \right]\)

In Example [exa:009969] suppose buses are also allowed to park, and let \(x_{k}\) denote the number of ways a row of \(k\) parking spaces can be filled with cars, trucks, and buses.

1. If trucks and buses take up 2 and 3 spaces respectively, show that \(x_{k+3} = x_{k} + x_{k+1} + x_{k+2}\) for each \(k\), and use this recurrence to compute \(x_{10}\). [Hint: The eigenvalues are of little use.]
2. If buses take up 4 spaces, find a recurrence for the \(x_{k}\) and compute \(x_{10}\).

2. \(x_{k+4} = x_k + x_{k+2} + x_{k+3}; x_{10} = 169\)

A man must climb a flight of \(k\) steps. He always takes one or two steps at a time. Thus he can climb 3 steps in the following ways: 1, 1, 1; 1, 2; or 2, 1. Find \(s_{k}\), the number of ways he can climb the flight of \(k\) steps. [Hint: Fibonacci.]

How many “words” of \(k\) letters can be made from the letters \(\{a, b\}\) if there are no adjacent \(a\)’s?

\(\frac{1}{2\sqrt{5}} \left[ 3 +\sqrt{5} \right] \lambda_1^k + (-3 + \sqrt{5}) \lambda_2^k\) where \(\lambda_1 = \frac{1}{2} (1 + \sqrt{5})\) and \(\lambda_2 = \frac{1}{2} (1 - \sqrt{5})\).

How many sequences of \(k\) flips of a coin are there with no HH?

Find \(x_{k}\), the number of ways to make a stack of \(k\) poker chips if only red, blue, and gold chips are used and no two gold chips are adjacent. [Hint: Show that \(x_{k+2} = 2x_{k+1} + 2x_{k}\) by considering how many stacks have a red, blue, or gold chip on top.]

\(\frac{1}{2\sqrt{3}} \left[ 2 +\sqrt{3} \right] \lambda_1^k + (-2 + \sqrt{3}) \lambda_2^k\) where \(\lambda_1 = 1 + \sqrt{3}\) and \(\lambda_2 = 1 - \sqrt{3}\).

A nuclear reactor contains \(\alpha\)- and \(\beta\)-particles. In every second each \(\alpha\)-particle splits into three \(\beta\)-particles, and each \(\beta\)-particle splits into an \(\alpha\)-particle and two \(\beta\)-particles. If there is a single \(\alpha\)-particle in the reactor at time \(t = 0\), how many \(\alpha\)-particles are there at \(t = 20\) seconds? [Hint: Let \(x_{k}\) and \(y_{k}\) denote the number of \(\alpha\)- and \(\beta\)-particles at time \(t = k\) seconds. Find \(x_{k+1}\) and \(y_{k+1}\) in terms of \(x_{k}\) and \(y_{k}\).]

The annual yield of wheat in a certain country has been found to equal the average of the yield in the previous two years. If the yields in 1990 and 1991 were 10 and 12 million tons respectively, find a formula for the yield \(k\) years after 1990. What is the long-term average yield?

\(\frac{34}{3} - \frac{4}{3}\left( -\frac{1}{2} \right)^k\). Long term 11\(\frac{1}{3}\) million tons.

Find the general solution to the recurrence \(x_{k+1} = rx_{k} + c\) where \(r\) and \(c\) are constants. [Hint: Consider the cases \(r = 1\) and \(r \neq\) 1 separately. If \(r \neq 1\), you will need the identity \(1 + r + r^2 + \cdots + r^{n-1} = \frac{1 - r^n}{1-r}\) for \(n \geq 1\).]

Consider the length \(3\) recurrence \(x_{k+3} = ax_{k} + bx_{k+1} + cx_{k+2}\).

1. If \(\mathbf{v}_k = \left[ \begin{array}{c} x_k \\ x_{k+1} \\ x_{k+2} \end{array}\right]\) and \(A = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 0 & 0 & 1 \\ a & b & c \end{array}\right]\) show that \(\mathbf{v}_{k+1} = A\mathbf{v}_{k}\).
2. [Hint: Show directly that \(A\mathbf{x} = \lambda\mathbf{x}\).]
3. of length \(4\).

2. \(A \left[ \begin{array}{c} 1 \\ \lambda \\ \lambda^2 \end{array}\right] = \left[ \begin{array}{c} \lambda \\ \lambda^2 \\ a + b\lambda + c\lambda^2 \end{array}\right] = \left[ \begin{array}{c} \lambda \\ \lambda^2 \\ \lambda^3 \end{array}\right] = \lambda \left[ \begin{array}{c} 1 \\ \lambda \\ \lambda^2 \end{array}\right]\)

Consider the recurrence

\[x_{k+2} = ax_{k+1} + bx_{k} + c \nonumber \]

where \(c\) may not be zero.

1. If \(a + b \neq 1\) show that \(p\) can be found such that, if we set \(y_{k} = x_{k} + p\), then \(y_{k+2} = ay_{k+1} + by_{k}\). [Hence, the sequence \(x_{k}\) can be found provided \(y_{k}\) can be found by the methods of this section (or otherwise).]
2. Use (a) to solve \(x_{k+2} = x_{k+1} + 6x_{k} + 5\) where \(x_{0} = 1\) and \(x_{1} = 1\).

2. \(x_k = \frac{11}{10} 3^k + \frac{11}{15}(-2)^k - \frac{5}{6}\)

Consider the recurrence

\[\label{eq:exrecurrence1} x_{k+2} = ax_{k+1} + bx_k + c(k) \]

where \(c(k)\) is a function of \(k\), and consider the related recurrence

\[\label{eq:exrecurrence2} x_{k+2} = ax_{k+1} + bx_k \]

Suppose that \(x_{k} = p_{k}\) is a particular solution of Equation [eq:exrecurrence1].

1. If \(q_{k}\) is any solution of Equation [eq:exrecurrence2], show that \(q_{k} + p_{k}\) is a solution of Equation [eq:exrecurrence1].
2. Show that every solution of Equation [eq:exrecurrence1] arises as in (a) as the sum of a solution of Equation [eq:exrecurrence2] plus the particular solution \(p_{k}\) of Equation [eq:exrecurrence1].

1. \(p_{k+2} + q_{k+2} = \left[ ap_{k+1} + bp_k + c(k) \right] + \left[ aq_{k+1} + bq_k \right] = a(p_{k+1} + q_{k+1}) + b(p_k+q_k) + c(k)\)