Q$2-$pg$2(9$ points$)$

Building blocks $-$ Page $2$: Recurrence relation

c$)$ Describe a recursive algorithm to construct all the possible towers of $n$ centimeters by adding blocks to smaller towers. Explain this

algorithm, supporting your explanation with drawings.

d$)$ Based on the algorithm in c$)$ give a recurrence relation for the sequence $t_n$ as a function of some of the elements of the sequence

that precede $t_n.$

Hint: the algorithm in c$)$ is used in d$)$ to count the different ways to construct a tower of a specific size. Be sure that the same tower

configuration is not constructed more than once by your algorithm.

e$)$ Specify the values of $n$ for which this recurrence relation applies.

f$)$ Could you have started this sequence at $t_0$ instead of $t_1?$ if so$,$ explain what would be the meaning and value of $t_0,$ and rewrite your

entire recursive definition accordingly.