Question: Now suppose that you want to solve the Restricted Trench puzzle. The setup is the same as the Trench puzzle of the previous problem, but only one direction of slant is allowed for the triangle's diagonal. Let us denote the number of ways of filling the first n inches of Restricted Trench as Rn.
(a) What are the first few Restricted Trench numbers R1, R2, R3, R4,... ?
(b) Construct a recurrence for Rn and explain why it is correct.
(c) Find a closed form for your recurrence.