Calculate the different apartment combinations

An apartment building is being divided up and converted into apartments. A large apartment takes up two stories of the building and a small apartment takes up one story of the building. Now I have given the number of stories in the building, how do I calculate the different apartment combinations?

Do I simply use the combination formula?

• I would proceed recursively. Let $T_n$ be the answer if the building has $n$ stories. Compute the first few, then sort out how to compute $T_n$ given $T_i$ for $i<n$. – lulu May 24 at 17:17

Let $$a_n$$ be the number of ways to do this with $$n$$ stories. For $$n$$ stories, if the highest apartment has size $$1$$, then there are $$a_{n-1}$$ ways to do everything below, and if it has size $$2$$ there are $$a_{n-2}$$ ways. So we obtain $$a_n = a_{n-1} + a_{n-2}$$. Noting that $$a_1=1, a_2=2,$$ we see that $$a_n$$ is in fact the $$(n+1)$$th Fibonacci number.