B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

Example: Find recurrence relation and initial condition for the number of bit strings of length n that do not have two consecutive 0s.

Solution: Let a_n denote the number of bit strings of length n that do not contain two consecutive 0s. Number of bit strings of length one that follow the necessary rule are: string 0 and string 1. Thus, a₁

= 2. The number of bit strings of length 2 is: string 01, 10 and 11. Thus, a₂ = 3. Now we shall consider the case n  3. The bit strings of length n that do not have two consecutive 0s are precisely those strings length n–1 with no consecutive 0s along with a 1 added 1 at the end of it (which is a_n–1 in number) and bit strings of length n–2 with no consecutive 0s with a 10 added at the end of it (which is a_n–2 in number). Thus, the recurrence relation is:

a_n = a_n–1 + a_n–2 for n  3 with a₁ = 2 and a₂ = 3.