Suppose you have an unlimited supply of black and white pebbles. There are four ways in which you can put two of them in a row: \(BB\), \(BW\), \(WB\) and \(WW\).
Write down the eight different ways in which you can put three pebbles in a row.
In how many different ways can you put \(N\) pebbles in a row?
Suppose now that you are not allowed to put black pebbles next to each other. There are now only three ways of putting two pebbles in a row, because \(BB\) is forbidden.
- Write down the five 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 restriction that black pebbles may not be next to each other, so \(r_2 = 3\) and \(r_3 = 5\).
- Show that for \(N \ge 4\) we have \(r_N = r_{N-1} + r_{N-2}\). Hint: consider separately the case where the last pebble is white, and the case where it is black.
Finally, suppose that we impose the further restriction that the first pebble and the last pebble cannot both be black. Let \(w_N\) be the number of such arrangements for \(N\) pebbles; for example, \(w_3 = 4\), since the configuration \(BWB\) is now forbidden.
- For \(N \ge 5\), write down a formula for \(w_N\) in terms of the numbers \(r_i\), and explain why it is correct.
