- #1

mr_coffee

- 1,629

- 1

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