Find a recurrence relation for the number of ways to form

Question

Assignment

1. Find f (1), f(2), f (3), f(4), and f(5) if f(n) is defined recursively by f(0) = 3 and for n = 0, 1, 2,.....

a) f (n + 1) =  -  2f (n).

b) f (n + 1) = 3f(n) + 7

c) f (n + 1) = f (n)² - 2f(n) - 2.

d) f (n + 1) = 3^f(n)/3

2. Find f (2), f (3), f (4), and f (5) if f is defined recursively by f(0) = f(1) = 1 and for n = 1, 2,

a) f (n + 1) = f (n) - f (n - 1).

b) f (n + 1) = f (n) f (n - 1).

c) f (n + 1) = f (n)² f(n - 1)³.

d) f (n + 1) = f (n)/f (n - 1}.

3. Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f (n) when n is a nonnegative integer and prove that your formula is valid.

a) f (0) = 1, f (n) = - f (n - 1) for n ≥ 1

b) f (0) = 1, f (1) = 0, f (2) = 2, f (n) = 2 f (n - 3) for n ≥ 3

c) f (0) = 0, f (1) = 1, f = 2f (n + 1) for n ≥ 2

d) f (0) = 0, f (1) = 1, f (n) = 2f (n - 1) for n ≥ 1

e) f (0) = 2, f (n) f (n - 1) if n is odd and n ≥ 1 and f (n) = 2 f (n - 2) if n ≥ 2

4. Give a recursive definition of the sequence fan {a_n}, n = 1, 2, 3, . . if

a) a_n = 4n - 2.             b) a_n = 1 + (-1)ⁿ .

c) a_n = n (n ± 1).         d) a_n = n².

5. Find the first six terms of the sequence defined by each of these recurrence relations and initial conditions.

a) a_n = 2a_{n - 1}, a_o = -1

b) a_n = a_n-1 - a_n-2, a₀ = 2, a₁ = 1

c) a_n = 3a²_{n - 1} a₀ = 1

d) a_n = na_n-1 + a_n-2², a_o = -1, a₁ = 0

e) a_n = a_n-1 - a_n-2 + a_n-3, a_o = 1, a₁ = 1, a₂ =2

6. For each of these sequences find a recurrence relation satisfied by this sequence. (The answers are not unique because there are infinitely many different recurrence relations satisfied by any sequence.)

a) a_n = 3               b) a_n = 2n

c) a_n = 2n + 3       d) a_n = 5ⁿ

e) a_n = n²             f) a_n = n² + n

g) a_n = n + ( -1)n  h) a_n = n!

7. A person deposits $1000 in an account that yields 9% interest compounded annually.

a) Set up a recurrence relation for the amount in the ac-count at the end of n years.

b) Find an explicit formula for the amount in the account at the end of n years.

c) How much money will the account contain after 100 years?

8. Assume that the population of the world in 2010 was 6.9 billion and is growing at the rate of 1.1% a year.

a) Set up a recurrence relation for the population of the world n years after 2010.

b) Find an explicit formula for the population of the world n years after 2010.

c) What will the population of the world be in 2030?

9. An employee joined a company in 2009 with a starting salary of 550,000. Every year this employee receives a raise of $1000 plus 5% of the salary of the previous year.

a) Set up a recurrence relation for the salary of this em-ployee n years after 2009.

b) What will the salary of this employee be in 2017?

c) Find an explicit formula for the salary of this em-ployee n years after 2009.

10. A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find a recurrence relation for the number of ways to pay a bill of n pesos if the order in which the coins and bills are paid matters.

11. Find a recurrence relation for the number of strictly increasing sequences of positive integers that have 1 as their first term and n as their last term, where n is a positive integer. That is, sequences a₁, a₂, ........., a_k, where a₁ = 1, a_k = n, and a_j < a_j+i for j = 1, 2, . . k - 1.

b) What are the initial conditions?

c) How many sequences of the type described in (a) are there when n is an integer with n ≥ 2?

12. Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are.

a) a_n = 3a_n-2            b) a_n = 3

c) a_n = an²_n-1             d) a_n = a_n-1 + 2a_n-3

e) a_n = a_n-1/n

f) a_n = a_{n - 1} + a_n-2 + n +3

g) a_n = 4a_n-2 + 5a_n-4 + 9a_n-7

13. Solve these recurrence relations together with the initial conditions given.

a) a_n = a_n-1 + 6a_n-2 for n ≥ 2, a₀ = 3, a₁ =6

b) a_n = 7a_n-1 - 10a_n-2 for n ≥ 2, a₀ = 2, a₁ = 1

c) a_n = 6an-1 - 8a_n-2 for n ≥ 2, a₀ = 4, a₁ = 10

d) a_n = 2a_n-1 - a_n-2 for n ≥ 2, a₀ = 4, a₁ =1

e) a_n = a_n-2 for n ≥ 2, a0 = 5, a₁ = -1

f) a_n = -6a_n-1 - 9a_n-2 for n ≥ 2, a₀ = 3, a₁ = -3

g) a_n+2 = -4a_n+1 + 5a_n for n ≥  0, a₀ = 2, a₁ = 8

14. A nuclear reactor has created 18 grams of a particular radioactive isotope. Every hour 1% of this radioactive isotope decays.

a) Set up a recurrence relation for the amount of this isotope left n hours after its creation.

b) What are the initial conditions for the recurrence rela-tion in part (a)?

c) Solve this recurrence relation.

15. Suppose that every hour there are two new bacteria in a colony for each bacterium that was present the previous hour, and that all bacteria 2 hours old die. The colony starts with 100 new bacteria.

a) Set up a recurrence relation for the number of bacteria present after n hours.

b) What is the solution of this recurrence relation?

c) When will the colony contain more than 1 million bac-teria?

16. A small post office has only 4-cent stamps, 6-cent stamps, and 10-cent stamps. Find a recurrence relation for the number of ways to form postage of n cents with these stamps if the order that the stamps are used matters. What are the initial conditions for this recurrence relation?