Purchase Solution

Recurrence and counting

Not what you're looking for?

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 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.

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 provided by:
Education
• BSc , Wuhan Univ. China
• MA, Shandong Univ.
Recent Feedback
• "Your solution, looks excellent. I recognize things from previous chapters. I have seen the standard deviation formula you used to get 5.154. I do understand the Central Limit Theorem needs the sample size (n) to be greater than 30, we have 100. I do understand the sample mean(s) of the population will follow a normal distribution, and that CLT states the sample mean of population is the population (mean), we have 143.74. But when and WHY do we use the standard deviation formula where you got 5.154. WHEN & Why use standard deviation of the sample mean. I don't understand, why don't we simply use the "100" I understand that standard deviation is the square root of variance. I do understand that the variance is the square of the differences of each sample data value minus the mean. But somehow, why not use 100, why use standard deviation of sample mean? Please help explain."
• "excellent work"
• "Thank you so much for all of your help!!! I will be posting another assignment. Please let me know (once posted), if the credits I'm offering is enough or you ! Thanks again!"
• "Thank you"
• "Thank you very much for your valuable time and assistance!"

Free BrainMass Quizzes

This quiz test you on how well you are familiar with solving quadratic inequalities.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts