Assignment:
Q1. 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.)
Q2. 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
Q3. 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.
Q4. 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??
Q5. 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
Provide complete and step by step solution for the question and show calculations and use formulas.