cs2223 Word Problem Example Solutions

[WPI] [cs2223] [cs2223 text] [News] [Notes] [Recurrence] [Word]

cs2223, D97/98 Solutions for Recurrence Word Problems

W1. A(n) - 1.18A(n-1) = 0 Where A(n) is the balance in the nth month.

W2. A(n) - 1.18A(n-1) = 5

W3. When the nth person joins, n-1 others send messages. A(n) - A(n-1) = n-1

W4. Form an n-letter word by adding a letter to an n-1 letter word. Consider two cases for words of length n-1: words containing only B-Z (to which Z can be added) and all other acceptable words containing A (to which only A-Y can be added). In the first group, the letters are all B-Z so there are 25^(n-1) words, to which Z can be added. In the second group, there are A(n-1) words, to which any of 25 letters can be added. The number of n-letter words is: A(n) - 25*A(n-1) = 25^(n-1)

W5. Subsets of Sn can be broken into two groups: those that don't include n-1 (to which n can be appended without causing consecutive integer conflict) and those that do include n-1 (to which n cannot be appended). The first set is just A(n-2) and the second set is A(n-1). The number of subsets is: A(n) - A(n-1) - A(n-2) = 0 This is the fibonacci sequence.

W6. There are two ways to arrange boxes on a shelf of size n: add a shoebox to the end of a shelf of size n-1 or add a boot box to the end of a shelf of size n-2. The number of arrangements is: Again, this is the fibonacci sequence.

W7. A(n) - A(n-1) = (-1)^n * n^2

W8. The average value on day n-1 is

A(n-1) = (1 / (n-1)) * sum(i=1 -> n-1; D(i))

and the average on day n is

A(n) = (1/n) * sum(i=1->n; D(i)) = ((n-1)/n) * ((1/(n-1)) * sum(i=1 -> n-1; D(i)) + D(n)/n

The recurrence relation is A(n) - ((n-1)/n) * A(n-1) = D(n)/n

W9. At each step, pieces 1/3 of each edge of the snowflake perimeter is removed and replaced by two pieces of the same size. Thus each piece is replaced by segments of total length 4/3 the original length. Adding together all of the pieces, the recurrence relation for the perimeter is:

P(n) - (4/3) * P(n-1) = 0

And, new triangles ( 3^n of them) each with area (sqrt(3)/4) * (L / 3^alpha)^2 , is added to the snowflake area. The resulting recurrence relation is:

A(n) = A(n-1) + (sqrt(3) * L^2 / 4) * 3 ^ (-alpha) = (1 + 3 ^ (-alpha)) * A(n-1)

W10. Products of even numbers are even; products of odd numbers are odd. Thus the recurrence relation that works for both even and odd numbers is:

A(n) - n*A(n-2) = 0