Solving a Tower Building Recurrence Relationship

[mr_coffee]

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

 

[lippyka]

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.