ChapterZero

Given a positive integer , how many strings of length can you construct that satisfy the following restrictions: each character in the string is a ‘b’ or a ‘w’, no ‘b’ can be followed by a ‘b’.

One interesting thing about this problem is that it shows in a straightforward manner that the special number you get is always less than or equal to . For that reason alone, it’s an interesting problem.

Since I could solve this one in the first go, here’s my solution:

For convenience, count places in the string from right to left, with the rightmost being position 1. Let and denote the number of strings that can be constructed beginning with a ‘w’ or a ‘b’, respectively, from the -th position. What we’re trying to determine, the number of strings with length k, is therefore . Convince your self that

and
,

also, it is clear that and . Manipulating these, , so , the -th Fibonnaci number. Then . So the wanted number of strings is . This shows that , because is the total number of strings consisting of ‘b’s and ‘w’s with length .

You could probably show this inequality using the closed form expression for also, but it’s neat that it falls out so clearly here.