5. With an unlimited supply of black pebbles and white pebbles, there are 4 ways in which you can put two of them in a row: $B B , B W , W B$ and $W W$.
(a) Write down the 8 different ways in which you can put three of the pebbles in a row. In how many different ways can you put $N$ of the pebbles in a row?
Suppose now that you are not allowed to put black pebbles next to each other: with two pebbles there are now only 3 ways of putting them in a row, because $B B$ is forbidden.
(b) Write down the 5 different ways that are still allowed for three pebbles.
Now let $r _ { N }$ be the number of possible arrangements for $N$ pebbles in a row, still under the no-two-black-together restriction, so that $r _ { 2 } = 3$ and $r _ { 3 } = 5$.
(c) Show that for $N \geqslant 4$ we have $r _ { N } = r _ { N - 1 } + r _ { N - 2 }$. [Hint: Consider separately the two possible cases for the colour of the last pebble.]
Finally, suppose that we impose the further restriction that the first pebble and the last pebble cannot both be black. For $N$ pebbles call the number of such arrangements $w _ { N }$, so that for example $w _ { 3 } = 4$ (although $r _ { 3 } = 5$, the arrangement $B W B$ is now forbidden).
(d) When $N \geqslant 5$, write down a formula for $w _ { N }$ in terms of the numbers $r _ { i }$, and explain why it is correct.