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
Mathematics Homework Solutions
#5608
Discrete Structures
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?
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.
What is this?
By OTA - Overall OTA Rating
Changping Wang, MA - 4.9/5
Purchase Cost Now
$2.19 CAD (was ~$11.97)
Included in Download
- Plain text response
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Probability - A bagel shop offers 14 varieties of bagels, 11 flavors of cream cheese, and 15 flavors of coffee. How many different orders for a bagel, cream cheese, and a coffee can a customer place?
- Prove that Binomial[2n, n] = Sum from k=0 to n of Binomial[n,k]^2 - Prove that (2n choose n) = the sum from k=0 to n of (n choose k) squared.
- In how many ways can the numbers 1,2,3,4,5,6 be written in a row if - In how many ways can the numbers 1,2,3,4,5,6 be written in a row if (a) There are no restrictions on the order of the numbers? (b) 1 dn 2 are next to each other? ... (SEE ATTACHMENT FOR REST)
- Probability and Combinations - The nation of Griddonesia consists of eighty-one equally-spaced islands represented by intersections of the lines in the following grid, where north is up and east is right as on a standard map. Each ...
- Probability and counting - There are 4 performers who will present their comedy this weekend at a comedy club. How many different ways are there to schedule their appearances ?
