Use cps420

Recursively Defined Sequence #1 Define the sequence B, = Number of different n-bit binary strings that contain at least one bit, but that do not contain the substring 101. For example B3 = 7 because the following seven bit strings of length 3 do not contain 101: 000,001, 010, 011, 100, 110, 111 Give a recursive definition for Br. Your definition must include: . All the initial conditions of the sequence A recurrence relation for B, as a function of some of the elements of the sequence that precede it The values of n for which this recurrence relation applies An explanation of how this recurrence relation was derived. Recursively Defined Sequence #2 Define the sequence In = Number of different ways that an nX2 rectangle can be tiled with 1X1 and 1X2 tiles. For example T, = 7 (try out all the possible drawings) Give a recursive definition for Tr. Your definition must include: All the initial conditions of the sequence A recurrence relation for T, as a function of some of the elements of the sequence that precede it The values of n for which this recurrence relation applies An explanation with drawings of how this recurrence relation was derived