Section 3.2 Recurrence Relations
199
a. Write a recurrence relation for the number of e-mails sent at the start of the nth second.
b. Solve the recurrence relation.
c. How many e-mails are sent at the end of 20 seconds (that is, at the beginning of the 21st second)?
16. Total natural gas consumption in the state of New Jersey was 614,908 million cubic feet in 2008 and
653,459 million cubic feet in 2010.
a. Assuming a constant annual percentage growth rate r, write a recurrence relation (in terms of r) for the
total natural gas consumption in New Jersey in year n.
b. Solve the recurrence relation (in terms of r).
c. Using the given data, compute the value of r.
d. What will be the total natural gas consumption in New Jersey in the year 2020?
17. A loan of $5,000 is charged a 12% annual interest rate. An $80 payment is made each month.
a. Write a recurrence relation for the loan balance remaining at the beginning of month n.
b. Solve the recurrence relation. (See Exercise 27 of Section 2.2 for the formula for the sum of a geometric
sequence.)
c. How much is left of the loan balance at the beginning of the 19th month?
18. In an account that pays 3% annually, $1,000 is deposited. At the end of each year, an additional $100 is
deposited into the account.
a. Write a recurrence relation for the amount in the account at the beginning of year n.
b. Solve the recurrence relation. (See Exercise 27 of Section 2.2 for the formula for the sum of a geometric
sequence.)
c. What is the account worth at the beginning of the 8th year?
19. The shellfish population in a bay is estimated to have a count of about 1,000,000. Studies show that
pollution reduces this population by about 2% per year, while other hazards are judged to reduce the
population by about 10,000 per year.
a. Write a recurrence relation for the shellfish population at the beginning of year n.
b. Solve the recurrence relation. (See Exercise 27 of Section 2.2 for the formula for the sum of a geometric
sequence.)
c. What is the approximate shellfish population at the beginning of year 10?
20. A certain protected species normally doubles its population each month. The initial population is 20,
but by the beginning of the next month, 1 specimen has died of an infection. In successive months, the
infection kills 2, then 4, then 8, and so forth.
a. Write a recurrence relation for the size of the population at the beginning of month n.
b. Solve this recurrence relation.
c. What is the size of the population at the beginning of month 7?
21. A computer virus that spreads by way of e-mail messages is planted in 3 machines the first day. Each
day, each infected machine from the day before infects 5 new machines. By the end of the second day, a
software solution has been found to counteract the virus, and 1 machine is clean at that point. Each day
thereafter, 6 times as many machines are clean as were clean the day before.
a. Write a recurrence relation for the total number of infected machines on day n.
b. Solve this recurrence relation.
c. How many days will it be before the effects of the virus are completely gone?
22. This problem concerns the Towers of Hanoi puzzle (see Exercise 82 in Section 3.1).
a. Based on the recursive algorithm of Exercise 82 in Section 3.1, find a recurrence relation M(n) for the
number of disk moves required to solve the Towers of Hanoi puzzle for n disks.
199
a. Write a recurrence relation for the number of e-mails sent at the start of the nth second.
b. Solve the recurrence relation.
c. How many e-mails are sent at the end of 20 seconds (that is, at the beginning of the 21st second)?
16. Total natural gas consumption in the state of New Jersey was 614,908 million cubic feet in 2008 and
653,459 million cubic feet in 2010.
a. Assuming a constant annual percentage growth rate r, write a recurrence relation (in terms of r) for the
total natural gas consumption in New Jersey in year n.
b. Solve the recurrence relation (in terms of r).
c. Using the given data, compute the value of r.
d. What will be the total natural gas consumption in New Jersey in the year 2020?
17. A loan of $5,000 is charged a 12% annual interest rate. An $80 payment is made each month.
a. Write a recurrence relation for the loan balance remaining at the beginning of month n.
b. Solve the recurrence relation. (See Exercise 27 of Section 2.2 for the formula for the sum of a geometric
sequence.)
c. How much is left of the loan balance at the beginning of the 19th month?
18. In an account that pays 3% annually, $1,000 is deposited. At the end of each year, an additional $100 is
deposited into the account.
a. Write a recurrence relation for the amount in the account at the beginning of year n.
b. Solve the recurrence relation. (See Exercise 27 of Section 2.2 for the formula for the sum of a geometric
sequence.)
c. What is the account worth at the beginning of the 8th year?
19. The shellfish population in a bay is estimated to have a count of about 1,000,000. Studies show that
pollution reduces this population by about 2% per year, while other hazards are judged to reduce the
population by about 10,000 per year.
a. Write a recurrence relation for the shellfish population at the beginning of year n.
b. Solve the recurrence relation. (See Exercise 27 of Section 2.2 for the formula for the sum of a geometric
sequence.)
c. What is the approximate shellfish population at the beginning of year 10?
20. A certain protected species normally doubles its population each month. The initial population is 20,
but by the beginning of the next month, 1 specimen has died of an infection. In successive months, the
infection kills 2, then 4, then 8, and so forth.
a. Write a recurrence relation for the size of the population at the beginning of month n.
b. Solve this recurrence relation.
c. What is the size of the population at the beginning of month 7?
21. A computer virus that spreads by way of e-mail messages is planted in 3 machines the first day. Each
day, each infected machine from the day before infects 5 new machines. By the end of the second day, a
software solution has been found to counteract the virus, and 1 machine is clean at that point. Each day
thereafter, 6 times as many machines are clean as were clean the day before.
a. Write a recurrence relation for the total number of infected machines on day n.
b. Solve this recurrence relation.
c. How many days will it be before the effects of the virus are completely gone?
22. This problem concerns the Towers of Hanoi puzzle (see Exercise 82 in Section 3.1).
a. Based on the recursive algorithm of Exercise 82 in Section 3.1, find a recurrence relation M(n) for the
number of disk moves required to solve the Towers of Hanoi puzzle for n disks.