Purchase Solution

Recurrence and counting

Not what you're looking for?

Ask Custom Question

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?

Attachments
Purchase this Solution
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:
Changping Wang, MA
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!"
Purchase this Solution
Free BrainMass Quizzes
Solving quadratic inequalities

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

View More Free Quizzes
Related BrainMass Solutions

  • Discrete structures: Sample questions

    Hint: Write n=2^m +k, where m is a nonnegative integer and k is a nonnegative integer less than 2^m. 8) Show that J(n) satisfies the recurrence relation J(2n) = 2J(n) - 1 and J(2n+1) = 2J(n) + 1, for n >= 1, and J(1) = 1. 9) Use mathematical induction

  • Solutions of Recurrence Relations

    49808 Solutions of Recurrence Relations Consider the recurrence relation . Show that the general solution is . Show that the solution with starting values and corresponds to and .

  • solving the recurrence relation

    Find a recurrence relation for the sequence A0, A1,... Find an initial condition for the sequence A0, A1,... Find A1, A2, and A3. 2.

  • Fibonacci recurrence

    plugging in a and b values) Recurrence relationship at n = 2, G(3) = G(2) + G(1) is obviously true.

  • recurrence relations

    19526 Recurrence Relations: Quicksort or Select See attached file. Here are some recurrence relations that come up in the analysis of Quicksort and or Select.

  • Using the Recurrence Relation in algebra

    State the recurrence relation and the initial conditions. Then use your recurrence relation to find the number of ways Bob can deposit $3.25.

  • Recurrence relations, compound interest, polynomials, number of combinations, & iteration

    339106 Recurrence relations, compound interest, polynomials Please help with the following discrete math involving recurrence relations, compound interest, polynomials, number of combinations and iteration. 14.

  • Recursive and Recurrence

    Find a solution to the recurrence relation: a_n = 3na_n-1, a_0 = 2 ** Please see the attached file for the complete solution ** Help 2 Recursive and Recurrence 1.

  • Fibonacci sequence in closed form

    . ~: Set Gn=[(a^n-b^n)/(a-b)] and show that Gn satisfies the recurrence formula {G(n+1) = Gn + G(n-1) for n=2,3,4...} and don't forget that a and b satisfy the equation x^2-x-1=0.

View More Related Solutions