Explore BrainMass

Recurrence and counting

1. Consider the sequence of triangles Ti, i >= 2: T2 is simply a triangle sitting upright, on its base. T3 is T2, except that an additional straight line is drawn from the upper vertex, down to somewhere on the base. For each Ti+1, one more line is added to triangle Ti (such that each line meets the base at a different point).

For each Ti we define ai to be the number of triangles ?contained? in Ti, each comprising 1 or more areas of Ti. So, e.g., a2 = 1, but a3 = 3: the triangle on the left, the triangle on the right, and the whole triangle.

a. Find a recurrence relation for the sequence ai.
b. Find a close-form solution for the sequence ai. (It may be easier to do this part first.)

2. Give formulas for the number of ways to buy k bagels from n types if
a. .order matters and each bagel different ("poppy, sesame " differs from "sesame, poppy, ")
b. order doesn't matter and each bagel different
c. order matters but repeated bagel purchases allowed ("poppy, sesame, sesame, " differs from "sesame, poppy, sesame, ")
d. order doesn't matter but repeated bagel purchases are allowed?

3. Find and solve a recurrence relation for the number of matches played in a tennis tournament, assuming the number of players is a power of 2.

4. If n balls, labeled 1 to n, are successively removed from an urn, a rencontre occurs if the ith ball is ball number i. Show that the probability that k rencontres occur (when drawing the balls in random order) is approximately (i.e., in the limit) 1/(k!*e).

Notice, by the way, that, for the case of n rencontres out of n balls, this formula gives 1/(n!e), whereas we would probably want to say the correct answer is simply 1/n!. Does this mean the formula is wrong?

5. Assume that the population of the world in 2002 is 6.2 billion and is growing at the rate of 1.3% a year.
a) set up a recurrence relation for the population of the world n years after 2002
b) find an explicit formula for the population of the world n years after 2002
c) what will the population of the world be in 2022?


Solution Preview

b) We can get ai in an easy way. Let us analyse it as follows. You know T2 just a triangle which has 2 edges except a base edge. T3 is T2 but an additional edge added, so there are 3 edges except the base edge. By the inductive way we know Tn will have n edges except the base edge. Now we want to know the number of the triangles in Tn. Any two edges and the base edge can form a triangle, so a(n) should equal to choosing 2 from n, ie, n(n-1)/2.
So a(n)=n(n-1)/2. For example, a(2)=1,a(3)=3, a(4)=6,a(5)=10,...
>a) By the analysis above, if the number of triangles in Ti is a(i), then the number of triangles in Ti+1 is a(i)+i since this additional edge can form a new triangle with each edge in Ti and the base edge, and Ti has i edges except the ...

Solution Summary

There are three examples of recurrence relation problems: one with triangles, one with population, and one with the number of matches in a tournament. There is also one problem about rencontres and one counting problem.