In: Advanced Math
You have a set of building-blocks which contains blocks of heights 1, 3 and 4 centimeters. (Other dimensions irrelevant.) You are constructing towers by piling blocks directly on top of one another. (A tower of height 7 cm could be obtained using seven blocks of height 1; one block of height 3 and one block of height 4; 2 blocks of height 3 and one block of height 1; etc.) Let bn be the number of ways to construct a tower of height n cm using blocks from the set. Assume that there is an unlimited supply of blocks of each size. Find a recurrence relation for bn. (You are not required to solve the recurrence relation.)
I am stuck on this question and don't really know where to start. I've seen examples done but they don't give a final result and I'm not sure how to get there.