Solving a Tower Building Recurrence Relationship

In summary, the conversation discusses a recurrence relationship problem involving constructing towers using blocks of different heights. The recurrence relation is t_n = t_{n-1} + t_{n-2} + t_{n-4}, with the base cases t_1 = 1, t_2 = 2, t_3 = 3 and t_4 = 4.
  • #1
mr_coffee
1,629
1
Hello everyone.

I"m having troubles figuring out this recurrance relationship. The problem is the following:

A set of bloks contains blocks of heights 1, 2, and 4 inches. Imaigne constructing towers by piling blocks of dferent heights directly on top of one another. (A tower of height 6 inches could be obtained using six 1 inch blocks, 3 2 inch blocks, one 2 inch block with one 4 inch block on top, one 4 inch block with one 2 inch block on top, and so oforth.)

Let t_n be the number of ways to construct a tower of height n inches using blocks from the set. (assume an inifinte supply of block of each size.) Find a recurrence relation for t_1, t_2, t_3...


Okay so i had no idea where to start so i started at
t_1...
well to form a tower of height 1, u only have 1 way, which is to place a 1 inch block, so
t_1 = 1
t_2 = 2
you can either stack 2, 1 inch blocks, or one 2 inch block, so 2 ways
t_3 = 3
you can stack 3, 1 inch blocks or one 2 inch block with a 1 inch block or stack a 1 inch block then stack a 2 inch block, so I'm getting 3
t_4 = 4
you can stack, four 1 inch blocks = 1 or two 2 inch blocks = 2 or two 2 inch blocks and two 1 inch blocks = 3, or the oppposite which would be 4, or one 4 inch block = 4.
which would be 4 total ways.


It looks like [tex]t_n = t_{n-1} + t_{n-2} + t_{n-4}[/tex]
but now i need the base cases, so would
t_1 = 1
t_2 = 2
t_3 = 3
and
t_4 = 4
then i can find t_5 by:
t_5 = T_4 + t_3 + t_1 = 4 + 3 + 1 = 7
 
Physics news on Phys.org
  • #2
Therefore, the recurrence relation for t_n is t_n = t_{n-1} + t_{n-2} + t_{n-4}, with the base cases t_1 = 1, t_2 = 2, t_3 = 3 and t_4 = 4.
 

Related to Solving a Tower Building Recurrence Relationship

1. What is a tower building recurrence relationship?

A tower building recurrence relationship is a mathematical formula used to represent the number of ways to build a tower with a certain number of levels, given a set of building blocks and specific rules for stacking them. It involves finding a pattern in the number of possible tower configurations as the number of levels increases.

2. How do you solve a tower building recurrence relationship?

To solve a tower building recurrence relationship, you need to first identify the base case, or the simplest case of the problem. Then, you can use a recursive formula to build up to the desired number of levels. This involves breaking down the problem into smaller subproblems and using the results to build up to the larger problem. You may also need to use combinatorial techniques, such as permutations and combinations, to find the total number of possible configurations.

3. What are some strategies for approaching a tower building recurrence relationship?

One strategy is to start by listing out all the possible tower configurations for a small number of levels and then look for patterns or relationships between them. Another strategy is to use a table or chart to organize the different configurations and their corresponding number of levels. You can also try to break down the problem into smaller subproblems and look for a recursive formula to solve them.

4. What are some real-life applications of tower building recurrence relationships?

Tower building recurrence relationships can be applied to various fields, such as computer science, physics, and biology. In computer science, they can be used to analyze the time complexity of algorithms or the number of possible outcomes in a game. In physics, they can represent the energy levels of atoms or the possible arrangements of particles in a system. In biology, they can be used to model the growth of populations or the formation of molecular structures.

5. Are there any common mistakes to avoid when solving a tower building recurrence relationship?

One common mistake is forgetting to consider all possible cases or configurations in the recursive formula. It is important to carefully analyze the problem and make sure all possible scenarios are accounted for. Another mistake is using an incorrect base case or recursive formula, which can lead to incorrect results. It is also important to double-check your calculations and make sure they are accurate. Finally, it is helpful to use a systematic approach and avoid relying on guesswork when solving a tower building recurrence relationship.

Similar threads

  • Introductory Physics Homework Help
Replies
1
Views
790
  • Mechanical Engineering
Replies
15
Views
1K
  • Introductory Physics Homework Help
Replies
3
Views
262
  • Introductory Physics Homework Help
2
Replies
38
Views
1K
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
768
  • Introductory Physics Homework Help
Replies
9
Views
1K
  • Introductory Physics Homework Help
Replies
1
Views
827
Back
Top