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.
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.