- #1

Miike012

- 1,009

- 0

I am having difficulty knowing which "cases" include in the recurrence equation.

My solution to problem in paint document.

Cases 1 - 6:

All cases contain strings of length n

Let a

a

0_ _ ... _

1_ _ ... _

a

1 0 _ ... _

1 1 _ ... _

0 1 _ ... _

a

0 0 _ ... _

Therefore

A

2(a

Cases that "overlap"

1 and 5: if second term of case 1 is 1

1 and 6: if second term of case 1 is 0

2 and 3: if second term of case 2 is 0

2 and 4: if second term of case 2 is 1

Therefore

a

My solution to problem in paint document.

Cases 1 - 6:

All cases contain strings of length n

Let a

_{k}represent number of bit string of length k with a pair of consecutive 0s.__For cases 1 and 2.__a

_{n-1}, k = n-1.**1.**Start with 00_ _ ... _

**2.**Start with 11_ _ ... _

__For cases 3 - 5__a

_{n-2}, k = n-2.**3.**Start with 1 01 0 _ ... _

**4.**Start with 1 11 1 _ ... _

**5.**Start with 0 10 1 _ ... _

__Case 6__a

_{n-2}= 2^{n-2}**6.**Start with 0 00 0 _ ... _

Therefore

A

_{n}= (sum of a_{k}from case 1 and 2) + (sum of a_{k}from case 3,4, and 5) + (a_{k}from case 6) =2(a

_{n-1}) + 3(a_{n-2}) + 2^{n-2}Cases that "overlap"

1 and 5: if second term of case 1 is 1

1 and 6: if second term of case 1 is 0

2 and 3: if second term of case 2 is 0

2 and 4: if second term of case 2 is 1

Therefore

a

_{n}= 2(a_{n-1}) - (a_{n-2}) + 2^{n-2}= A_{n}- 4(a_{n-2})#### Attachments

Last edited: