Consider the Set$S$ Of All Strings Of$a$ 'S And$b$ 'S for Each Integer

Question

Examlex · Accepted Answer

The Answer is First note that there is one string of length zero that does not contain the pattern bb, namely
ϵ, the null string; there are two strings of length one that do not contain the pattern bb, namely
a and b; and there are three strings of length three that do not contain the pattern bb, namely
aa, ab, and ba. Thus the initial conditions for the recurrence relation are

a _ { 0 } = 1 , a _ { 1 } = 2 , ext { and } a _ { 2 } = 3

Let

k

be any integer with

k \geq 2

. Any string of length

k

that does not contain the pattern

b b

starts either with an

a

or with a

b

. If it starts with an

a

, this can be followed by any string of

k - 1 b

's that does not contain the pattern

b b

. There are

a _ { k - 1 }

of these. If the string starts with a

b

, then it must be followed by an

a

and that can be followed by any string of length

k - 2

that does not contain the pattern

b b

. There are

a _ { k - 2 }

of these. Therefore, for all integers

k \geq 2

,

a _ { k } = a _ { k - 1 } + a _ { k - 2 }

Consider the Set $S$ Of All Strings Of $a$ 'S And $b$ 'S for Each Integer

Definitions:

Consider the Set SSS Of All Strings Of aaa 'S And bbb 'S for Each Integer

Definitions:

Consider the Set $S$ Of All Strings Of $a$ 'S And $b$ 'S for Each Integer