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.
The eight ways are \(BBB\), \(BBW\), \(BWB\), \(BWW\), \(WBB\), \(WBW\), \(WWB\), \(WWW\).
- In how many different ways can you put \(N\) pebbles in a row?
For \(N\) pebbles, there are two possibilities for each (black or white), giving \(2^N\) possible ways.
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.
The five ways are \(BWB\), \(BWW\), \(WBW\), \(WWB\), \(WWW\).
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.
Consider a row of \(N\) pebbles which does not contain adjacent black pebbles; there are \(r_N\) such arrangements.
If the last pebble is \(W\), then the previous pebbles form a row of length \(N-1\) with no adjacent \(B\)s; there are \(r_{N-1}\) such arrangements.
If the last pebble is \(B\), the previous pebble must be \(W\), and the rest form a row of length \(N-2\) with no adjacent \(B\)s; there are \(r_{N-2}\) such arrangements.
These are all the possible combinations that fit the rule, and so \(r_N = r_{N-1} + r_{N-2}\).
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.
Of the \(w_N\) rows of length \(N\) which follow these rules:
If the first pebble is \(W\), the rest of the pebbles form a row of length \(N-1\) with no adjacent \(B\)s; there are \(r_{N-1}\) such arrangements.
If the first pebble is \(B\), the second must be \(W\); also the last pebble must be \(W\). The remaining pebbles form a row of length \(N-3\) with no adjacent \(B\)s; there are \(r_{N-3}\) such arrangements.
These are all the possible combinations that fit the rule, and so \[w_N = r_{N-1} + r_{N-3}.\]
Alternatively, consider all the rows of length \(N\) with no adjacent black pairs. There are \(r_N\) of these.
We now wish to subtract the rows that have a black pebble at each end. These will each have a white pebble alongside.
Remove these four pebbles, and we have a row of length \(N-4\), and there are \(r_{N-4}\) possibilities for this.
So \(w_N = r_N - r_{N-4}\).
We know \(r_N = r_{N-1} + r_{N-2}\), so applying this twice, we have \(w_N = r_{N-1} + r_{N-3}.\)
