Let xn denote the number of binary strings of length n that contain…

Recurrence: x_n = x_{n-1} + x_{n-2}

Reason (case split):

• If a valid string of length n starts with 1, the remaining n-1 bits can be any valid string of length n-1: x_{n-1} choices

• If it starts with 0, the next bit cannot be 0, so the first two bits must be '01'. The remaining n-2 bits can be any valid string of length n-2: x_{n-2} choices

• Combining the two disjoint cases gives x_n = x_{n-1} + x_{n-2}.

Base cases:

• For n = 1, the valid strings are 0 and 1, so x1 = 2.

• For n = 2, the valid strings are 01, 10, 11, so x2 = 3.

Thus for n ≥ 3 the recurrence x_n = x_{n-1} + x_{n-2} with x1 = 2 and x2 = 3 holds, producing the sequence 2, 3, 5, 8, ...