8.2 Solving Linear Recurrence Relations

p535
Ex: 1-6

Definition

A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form

an=c1an−1+c2an−2+⋯+ckan−k\begin{aligned} a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k} \end{aligned}

where c1,c2,⋯ckc_1, c_2, \cdots c_k are real numbers, and ck≠0c_k \ne 0.

  • Linear - the right-hand side is a sum of previous terms of the sequence each multiplied by a function of nn.
  • Homogeneous - no terms occur that are not multiplies of aja_js.
  • Constants - the coefficients of the terms are constants
  • Degree - ana_n is expressed in terms of the previous kk terms of the sequence.

Example 1
The recurrence relation Pn=(1.11)Pn−1P_n = (1.11)P_{n-1} is a linear homogeneous recurrence relation of degree one. The recurrence relation fn=fn−1+fn−2f_n = f_{n-1} + f_{n-2} is a linear homogeneous recurrence relation of degree two. The recurrence relation an=an−5a n = a_{n-5} is a linear homogeneous recurrence relation of degree five.

Example 2
The recurrence relation an=an−1+an−2a_n = a_{n-1} + a_{n-2} is not linear. The recurrence relation Hn=2Hn−1+1H_n = 2H_{n-1} + 1 is not homogeneous. The recurrence relation Bn=nBn−1B_n = nB_{n-1} does not have constant
coefficients.

Homework

p545: 2, 4a,d,e,f,g, 8, 12, 14

2. Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are.
a. an=3an−2a_n=3a_{n-2}
b. an=3a_n=3
c. an=an−12a_n=a_{n-1}^2
d. an=an−1+2an−3a_n=a_{n-1} + 2a_{n-3}
e. an=an−1/na_n=a_{n-1}/n
f. an=an−1+an−2+n+3a_n=a_{n-1} + a_{n-2} + n + 3
g. an=4an−2+5an−4+9an−7a_n=4a_{n-2} + 5a_{n-4} + 9a_{n-7}

Solution

a. Linear, homogeneous, constant coefficient, and degree of 2.
b. Not recurrence relations.
c. Not linear.
d. Linear, homogeneous, constant coefficient, and degree of 3.
e. Coefficient is not constant.
f. Not homogenous.
g. Linear, homogeneous, constant coefficient, and degree of 7.

4. Solve these recurrence relations together with the initial conditions given.
a. an=an−1+6an−2a_n = a_{n-1} + 6a_{n-2}, for n≥2,a0=3,a1=6n \geq 2, a_0 = 3, a_1 = 6

Solution

The degree is 22. Characteristic equation is r2−r−6=0r^2-r-6=0. Its roots are r=3,−2r=3, -2.

an=c1(3)n+c2(−2)na0=c1+c2=3a1=3c1−2c2=6⇒c1=125,c2=35an=125⋅3n+35⋅(−2)n\begin{aligned} a_n &= c_1(3)^n + c_2(-2)^n\\ a_0 &= c_1 + c_2 = 3\\ a_1 &= 3c_1 - 2c_2 = 6\\ &\To c_1 = \frac{12}{5}, c_2= \frac{3}{5}\\ a_n &= \frac{12}{5} \cdot 3^n + \frac{3}{5} \cdot (-2)^n \end{aligned}

d. an=2an−1−an−2a_n = 2a_{n-1} - a_{n-2}, for n≥2,a0=4,a1=1n \geq 2, a_0 = 4, a_1 = 1

Solution

The degree is 22. Characteristic equation is r2−2r+1=0r^2-2r+1=0. Its only root is r=1r=1.

an=c1(1)n+c2⋅n(1)na0=c1=4a1=c1+c2=1⇒c1=4,c2=−3an=4−3n\begin{aligned} a_n &= c_1 (1)^n + c_2 \cdot n(1)^n\\ a_0 &= c_1 = 4\\ a_1 &= c_1 + c_2 = 1\\ &\To c_1=4, c_2=-3\\ a_n &= 4 - 3n \end{aligned}

e. an=an−2a_n = a_{n-2}, for n≥2,a0=5,a1=−1n \geq 2, a_0 = 5, a_1 = -1

Solution

The degree is 22. Characteristic equation is r2−1=0r^2-1=0. Its roots are r=1,−1r=1, -1.

an=c1(1)n+c2(−1)na0=c1+c2=5a1=c1−c2=−1⇒c1=2,c2=3an=2+3⋅(−1)n\begin{aligned} a_n &= c_1 (1)^n + c_2 (-1)^n\\ a_0 &= c_1 + c_2 = 5\\ a_1 &= c_1 - c_2 = -1\\ &\To c_1=2, c_2=3\\ a_n &= 2 + 3 \cdot (-1)^n \end{aligned}

f. an=−6an−1−9an−2a_n = -6a_{n-1} - 9a_{n-2}, for n≥2,a0=3,a1=−3n \geq 2, a_0 = 3, a_1 = -3

Solution

The degree is 22. Characteristic equation is r2+6r+9=0r^2 + 6r + 9=0. Its only root is r=−3r=-3.

an=c1(−3)n+c2⋅n(−3)na0=c1=3a1=−3c1−3c2=−3⇒c1=3,c2=−2an=3⋅(−3)n−2n⋅(−3)n\begin{aligned} a_n &= c_1 (-3)^n + c_2 \cdot n(-3)^n\\ a_0 &= c_1 = 3\\ a_1 &= -3c_1 - 3c_2 = -3\\ &\To c_1=3, c_2=-2\\ a_n &= 3\cdot (-3)^n - 2n \cdot (-3)^n \end{aligned}

g. an+2=−4an+1+5ana_{n+2} = -4a_{n+1} + 5a_n, for n≥0,a0=2,a1=8n \geq 0, a_0 = 2, a_1 = 8

Solution

The degree is 22. Characteristic equation is r2+4r−5=0r^2 + 4r-5=0. Its roots are r=1,−5r=1, -5.

an=c1(1)n+c2(−5)na0=c1+c2=2a1=c1−5c2=8⇒c1=3,c2=−1an=3−(−5)n\begin{aligned} a_n &= c_1 (1)^n + c_2 (-5)^n\\ a_0 &= c_1 + c_2 = 2\\ a_1 &= c_1 - 5c_2 = 8\\ &\To c_1=3, c_2=-1\\ a_n &= 3 - (-5)^n \end{aligned}

8. A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years.
a. Find a recurrence relation for {Ln}\{L_n\}, where LnL_n is the number of lobsters caught in year nn, under the assumption for this model.
b. Find LnL_n if 100,000100,000 lobsters were caught in year 11 and 300,000300,000 were caught in year 22.

Solution

Ln=Ln−12+Ln−22 for n≥3L1=100000L2=300000\begin{aligned} L_n &= \frac{L_{n-1}}{2} + \frac{L_{n-2}}{2} &\text{ for } n\geq 3\\ L_1 &= 100000 \quad L_2= 300000 \end{aligned}

The degree is 2. Characteristic equation is r2−12r−12=0r^2-\frac{1}{2}r-\frac{1}{2}=0. Its roots are r=1,−12r=1, -\frac{1}{2}.

Ln=c1(1)n+c2(−12)nL1=c1−12c2=100000L2=c1+14c2=300000⇒c1=7000003,c2=8000003Ln=7000003+8000003⋅(−12)n\begin{aligned} L_n &= c_1 (1)^n + c_2 (-\frac{1}{2})^n\\ L_1 &= c_1 - \frac{1}{2}c_2 = 100000\\ L_2 &= c_1 + \frac{1}{4}c_2 = 300000\\ &\To c_1=\frac{700000}{3}, c_2=\frac{800000}{3}\\ L_n &= \frac{700000}{3} + \frac{800000}{3} \cdot (-\frac{1}{2})^n \end{aligned}

12. Find the solution to an=2an−1+an−2−2an−3a_n = 2a_{n-1} + a_{n-2} - 2a_{n-3} for n=3,4,5⋯n = 3, 4, 5 \cdots, with a0=3,a1=6a_0 = 3, a_1 = 6, and a2=0a_2 = 0.

Solution

The degree is 3. Characteristic equation is r3−2r2−r+2=0r^3 - 2r^2 -r + 2=0. Its roots are r=1,2,−1r=1, 2, -1.

an=c1(1)n+c2(2)n+c3(−1)na0=c1+c2+c3=3a1=c1+2c2−c3=6a2=c1+4c2+c3=0⇒c1=6,c2=−1,c3=−2an=6−2n−2(−1)n\begin{aligned} a_n &= c_1 (1)^n + c_2 (2)^n + c_3 (-1)^n\\ a_0 &= c_1 + c_2 +c_3 = 3\\ a_1 &= c_1 + 2c_2 -c_3 = 6\\ a_2 &= c_1 + 4c_2 +c_3 = 0\\ &\To c_1=6, c_2=-1, c_3=-2\\ a_n &= 6-2^n - 2(-1)^n \end{aligned}

14. Find the solution to an=5an−2−4an−4a_n = 5a_{n-2} - 4a_{n-4} with a0=3,a1=2,a2=6a_0 = 3, a_1 = 2, a_2 = 6, and a3=8a_3 = 8.

Solution

The degree is 4. Characteristic equation is r4−5r2+4=0r^4 - 5r^2 + 4=0. Its roots are r=1,−1,2,−2r=1, -1, 2, -2.

an=c1(1)n+c2(−1)n+c3(2)n+c4(−2)na0=c1+c2+c3+c4=3a1=c1−c2+2c3−2c4=2a2=c1+c2+4c3+4c4=6a3=c1−c2+8c3−8c4=8⇒c1=1,c2=1,c3=1,c4=0an=1+(−1)n+2n\begin{aligned} a_n &= c_1 (1)^n + c_2 (-1)^n + c_3 (2)^n + c_4 (-2)^n\\ a_0 &= c_1 + c_2 + c_3 + c_4 = 3\\ a_1 &= c_1 - c_2 + 2c_3 - 2c_4 = 2\\ a_2 &= c_1 + c_2 + 4c_3 + 4c_4 = 6\\ a_3 &= c_1 - c_2 + 8c_3 - 8c_4 = 8\\ &\To c_1=1, c_2=1, c_3=1, c_4=0\\ a_n &= 1 + (-1)^n + 2^n \end{aligned}