A set of blocks contains blocks of heights 1, 2, and 4 centimeters. Imagine cons
ID: 1720755 • Letter: A
Question
A set of blocks contains blocks of heights 1, 2, and 4 centimeters. Imagine constructing towers by piling blocks of different heights directly on top of one another. (A tower of height 6 cm could be obtained using six 1-cm blocks, three 2-cm blocks one 2-cm block with one 4-cm block on top, one 4-cm block with one 2-cm block on top, and so forth.) Let t_n be the number of ways to construct a tower of height n cm using blocks from the set. (Assume an unlimited supply of blocks of each size.) Find a recurrence relation for t_1,t_2,t_3,....Explanation / Answer
The last block of a tower of height n can be a 1, 2, or 4.
so it was added to a tower of height n-1, n-2, or n-4 respectively.
Let's try: tn = t[n-1] + t[n-2] + t[n-4] . . .
1 = 1 from 1
2 = 2 from (2) or (1,1)
3 = 3 from (1,1,1) or (2,1) or (1,2)
4 = 6 from (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2) (4)
5 = 10 from
1 x (1,1,1,1,1)
4 x (1,1,1,2)
3 x (1,2,2)
2 x (1,4)
6 = 18 from
2 x (4,2) ....
3 x (4,1,1) ...
1 x (2,2,2) .....
6 x (2,2,1,1) ....
5 x (2,1,1,1,1) ...
1 x (1,1,1,1,1,1) ..
Prediction for 7 is t6 + t5 + t3 = 18 + 10 + 3 = 31
6 x (4,2,1)
4 x (4,1,1,1)
4 x (2,2,2,1)
10 x (2,2,1,1,1)
6 x (2,1,1,1,1,1)
1 x (1,1,1,1,1,1,1)
Total 31 ... works for us!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.