| Due: | 4/22 |
A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, 10 pesos, 20 pesos, 50 pesos and 100 pesos. Give a recurrence relation and initial conditions for the number of ways to pay a bill of n pesos if the order in which the coins are paid matters.
Find a recurrence relation and initial conditions for the number of bit strings of length n that contain three consecutive 0s.
How many bit strings of length seven contain three consecutive 0s?
Find a recurrence and initial conditions for the number of ways to climb n stairs if the person climbing the stairs can take one,two or three stairs at a time. (For example, to climb a flight of 3 stairs, this person might take steps of (3), (2, 1), (1, 2) or (1, 1, 1). So you are counting sequences that contain 1, 2 and 3 that sum to n)
In how many ways can this person climb a flight of eight stairs?
A ternary string is a string of 0s, 1s and 2s.
Find a recurrence relation and initial conditions for the number of ternary strings of length n that contain two consecutive 0s.
How many ternary strings of length six contain two consecutive 0s?
A bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into the mechanical toll collector. (Yes, that sounds tedious.)
Find a recurrence relation and initial conditions for the number of different ways the bus driver can pay a toll of n cents, where the order in which the coins are used matters.
In how many different ways can the driver pay a toll of 45 cents?
Find a recurrence relation and initial conditions for the number of bit strings of length n with an even number of 0s.
Write out all of the ways the product x0 ⋅ x1 ⋅ x2 ⋅ x3 ⋅ x4 can be parenthesized to determine the order of multiplication.
Using the recurrence relation developed in the textbook for the Catalan number Cn, the number of ways to parenthesize a multiplication of n + 1 numbers, compute C4. Does your result agree with the number of ways that you found in part (a)?
Compute C4 using the closed-form developed in the textbook for Cn. Does your result agree with your answers from parts (a) and (b)?
Which of the following are linear homogeneous recurrence relations with constant coefficients? Give the degree of those that are.
| a. | an = 3an−2 | linear homogeous? | degree: |
| b. | an = 3 | linear homogeous? | degree: |
| c. | an = a2n−1 | linear homogeous? | degree: |
| d. | an = an−1 + 2an−3 | linear homogeous? | degree: |
| e. | an = an−1/n | linear homogeous? | degree: |
| f. | an = an−1 + an−3 + n + 3 | linear homogeous? | degree: |
| f. | an = 4an−2 + 4an−4 + 9an−7 | linear homogeous? | degree: |
Solve each of the following recurrence relations with the given initial conditions. That is, find a closed-form solution for an.
an = an−1 + 6an−2 for n ≥ 2, a0 = 3, a1 = 6.
an = 7an−1 − 10an−2 for n ≥ 2, a0 = 2, a1 = 1.
an = 6an−1 − 8an−2 for n ≥ 2, a0 = 4, a1 = 10.
an = 2an−1 − an−2 for n ≥ 2, a0 = 4, a1 = 1.
an = an−2 for n ≥ 2, a0 = 5, a1 = −1.
an = −6an−1 − 9an−2 for n ≥ 2, a0 = 3, a1 = −3.
an+2 = −4an+1 + 5an for n ≥ 0, a0 = 2, a1 = 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 previous two years.
Find a recurrence relation for sequence {Ln}. where Ln is the number of lobsters caught in year n, under the assumption of this model.
Find a closed-form for Ln if 100,000 lobsters were caught in year 1 and 300,000 were caught in year 2.
Find a closed-form solution to an = 5an−2 − 4an−4 with a0 = 3, a1 = 2, a2 = 6 and a3 = 8.
Consider the nonhomogenous linear recurrence relation an = 2an−1 + 2n.
Show that an = n2n is a solution of this recurrence relation by substituting it into the recurrence.
Give a general form that describes all solutions of this recurrence relation.
Find the solution with a0 = 2.
Find a general form that describes all solutions of recurrence relation an = 2an−1 + 2n2
Find the solution to the recurrence of part (a) with initial condition a1 = 4.
Find a general form that describes all solutions of recurrence relation an = 2an−1 + 3 ⋅ 2n.
Suppose f (n) = 2 f (n/2) + 3 when n is an even positive integer, and f (1) = 4. Find
If m and n are positive integers and x is an integer, then xn mod m can be computed using the following recursive algorithm.
| x1 | = | x |
| x2n | = | (x2 mod m)n mod m |
| xn+1 | = | x ⋅ (xn mod m) mod m |
A modular multiplication consists of a multiplication of two integers followed by taking the result mod a given modulus. Give a divide-and-conquer recurrence relation, including initial conditions, for the number of modular multiplications used by the above algorithm to compute xn mod m.
Give a big-O solution for your recurrence from part (a).