Suggestion

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

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

Using the hint: if the last pebble is white, what do we know about the rest of the row?

  1. For \(N \ge 5\), write down a formula for \(w_N\) in terms of the numbers \(r_i\), and explain why it is correct.

What do we know if the first pebble is white? If it’s black?