# How many ways are there to paint an $n$-storey block of flats if each level must be painted black or white with the given restrictions?

You are painting a block of flats, each level must be painted either black or white, but you can only paint a level white if it has a black level immediately below it. How many ways are there of painting an $$n$$-storey block of flats?

I'm struggling with the problem above. I have been introduced to permutations, but have no idea how to use/change the formula to take the restrictions into account. I know level 1 must be black, level 2 could be black or white and there will be three different ways of painting a 3-storey building. I can see that there will be five different ways of painting a 4-storey building (bbbb, bbbw, bbwb, bwbw, bwbb), but maybe I've just not learnt enough to tackle this problem! Any help would be appreciated.

• Welcome to MathSE. When you pose a question here, it is expected that you share your own thoughts on the problem. Please edit your question to show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site. – N. F. Taussig Oct 14 '18 at 21:48
• Thank you for the guidance and my apologies - I'm new to the site! – user604270 Oct 14 '18 at 22:14
• If you let $a_n$ be the number of ways you can paint an $n$-storey building, you have determined that $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, and $a_4 = 5$. Do those numbers look familiar? – N. F. Taussig Oct 14 '18 at 22:16
• After having worked out the number of ways to paint five levels, I recognised it as the Fibonacci sequence - thank you! I guess I have a long way to go when it comes to pattern spotting... – user604270 Oct 14 '18 at 22:25

## 1 Answer

Let $$a_n$$ be the number of ways of painting an $$n$$-storey building. You have correctly determined that \begin{align*} a_1 & = 1\\ a_2 & = 2\\ a_3 & = 3\\ a_4 & = 5 \end{align*} We can restate the problem by asking in how many ways can we form a sequence of $$b$$s and $$w$$s in which any $$w$$ must be immediately preceded by a $$b$$?

An admissible sequence of length $$n$$ can be formed by appending a $$b$$ to an admissible sequence of length $$n - 1$$, of which there are $$a_{n - 1}$$. Moreover, any admissible sequence of length $$n - 1$$ can be extended to an admissible sequence of length $$n$$ by appending a $$b$$. Hence, there are $$a_{n - 1}$$ sequences of length $$n$$ that end with $$b$$.

An admissible sequence of length $$n$$ that ends in $$w$$ must have a $$b$$ in the $$(n - 1)$$st position. Thus, an admissible sequence of length $$n$$ that ends in $$w$$ can be formed by appending $$bw$$ to an admissible sequence of length $$n - 2$$, of which there are $$a_{n - 2}$$. Moreover, any admissible sequence of length $$n - 2$$ can be extended to an admissible sequence of length $$n$$ only by appending $$bw$$. Hence, there are $$a_{n - 2}$$ sequences of length $$n$$ that end with $$w$$.

Thus, we have the recurrence $$a_n = a_{n - 1} + a_{n - 2}, n \geq 3$$ The first few terms of the sequence are $$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots$$. Hence, $$a_n = F_{n + 1}$$, where $$F_n$$ is the $$n$$th Fibonacci number, as you recognized in the comments.