# 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

1.

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.