Multiple choice

Let xn denote the number of binary strings of length n that contain no consecutive 0s.

Which of the following recurrences does xn satisfy?

  1. xn = 2xn − 1

  2. xn = x[n/2] + 1

  3. xn = x[n/2] + n

  4. xn = xn - 1 + xn - 2
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

For binary strings of length n with no consecutive 0s: strings ending in 1 can be formed from any valid (n-1)-length string, and strings ending in 01 can be formed from valid (n-2)-length strings. This gives x_n = x_{n-1} + x_{n-2}, which is the Fibonacci recurrence.

Keep practicing — related questions