558 CHAPTER 9 Recurrence Relationsrn Exercises
- Solve T(n) = T(n- 1) +n forn > I with T(0) = 2.
- Solve T(n) = T(n - 1) + n for n > I with T(0) = 7.
- Solve T(n) = T(n - 1) + 2n + I for n > I with T(0) = 1.
- Solve T(n) = T(n - 1) + 5 for n > I with T(0) = 1.
- Solve T(n) = T(n - 1) + 2 for n > I with T(O) = 2.
- Solve 2T(n + 1) - T(n) = 3 for n > I with T(0) =3.
- Solve T(n + 1) =-- -T(n) + I for n > I with T(0)= 1.
- Solve T(n) = T(n - 1) + I forn > I with T(0) = 1.
- Solve T(n) = T(n - 1) + n for n > 2 with T(1) = 1.
- Solve T(n) = T(n - 1) + n for n > 2 with T(1) = 0.
- Solve T(n) = T(n - 1) +-n^3 forn > I with T(0) = 0.
- Solve T(n) = T(n - 1) - n + 3 for n > I with T(0) = 2.
- Solve T(n) = T(n - 1) + 2 for n > I with T(0) = 1.
- Consider n coplanar straight lines, no two of which are parallel and no three of which
pass through a common point. Find and solve the recurrence relation that describes the
number of disjoint areas into which the lines divide the plane. - Find and solve the recurrence relation for the number of ways to arrange n distinct
objects in a row. - Find and solve the recurrence relation that describes the number of regions created
by mutually overlapping circles on a piece of paper provided no three circles have a
common intersection point and each pair of circles intersects in exactly two points.
Begin by drawing a picture for such a configuration when n = 1, 2, 3, and 4. - How many strings of length n formed using the alphabet {0,1,2,3} have an even number
of zeros? - A very old puzzle book (dated 1917) contained the following problem: A man had a
basket containing n potatoes. He asked his child to place these potatoes on the ground
in a straight line. The distance between the first and second potatoes was to be one
yard, between the second and third potatoes three yards, between the third and fourth
potatoes five yards, and so on. After placing all the potatoes as required, how far would
the child walk, starting at the first potato, to pick up all n potatoes? How many potatoes
would the child pick up in the first mile of walking? - The population of a fruit fly colony doubles every day. If a colony of fruit flies has 100
members at the start of an experiment, how many fruit flies will be present after n days?
If the population triples every day, how many fruit flies will be present after n days? - The value of a dollar investment after n years of compounding at an interest rate of
i percent per year is the future value of the investment and is denoted FV(n). Find
and solve a recurrence relation that gives FV(n) in terms of FV(n - 1). Assume that
interest is calculated at the end of each year. What will be the future value of $1000
after 3, 4, 5, and 10 years? Compare this to Exercise 33 in Section 1.9. - Find the general solution for a first-order homogeneous recurrence relation with con-
stant coefficients. Is the restriction that the coefficients be constant necessary? - Two versions of the bubble sort are given below. Determine the complexity of each
procedure. For the recursive version of the code, find and solve the recurrence relation