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

GATE · 2008 · CSModified — slightly modified from the official paper; see the solution

Let xn denote the number of binary strings of length n that contain no two consecutive 0s. This sequence satisfies the recurrence xn = xn-1 + xn-2.

The value of x5 is:

  1. A.

    5

  2. B.

    7

  3. C.

    8

  4. D.

    13

Show answer

Correct answer: D

The worked solution is available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…