B.5.FM:5.3 - Construct classes that permit a counting inference

We need counts of binary strings at several lengths under a rule that forbids consecutive 1s. Use length four as a small case. The question supplies symbols and a restriction, but no recurrence.

Start with short valid prefixes and examine their allowed next symbols. A prefix ending in 1 may receive only 0. A prefix ending in 0 may receive either symbol; the empty prefix has the same two permissions. Group prefixes by those extension permissions.

Let r_n count valid length-n prefixes that are empty or end in 0; let b_n count those ending in 1. Every valid prefix can receive 0, while only the r_n prefixes can receive 1:

r_0 = 1, b_0 = 0
r_(n+1) = r_n + b_n
b_(n+1) = r_n

The pairs for lengths 1 through 4 are (1,1), (2,1), (3,2), (5,3). There are eight valid strings of length four.

The inference works because each extension produces a distinct string, deleting its final symbol recovers its unique predecessor, and the two resulting classes exhaust the permitted cases. The total alone does not tell how many prefixes permit appending 1; keeping the two classes makes that operation possible.

If the restriction changes to “no three consecutive 1s”, the same grouping loses a needed distinction. Separate prefixes with zero, one or two trailing 1s and reconstruct the permitted transitions. This change identifies what the state must retain; the subsequent recurrence or program is a further computational contribution.