(New page: Category:MA375Spring2009Walther Section 7.1 #24 a.)Let a(n) be the number of bit strings of length n containing 3 consecutive 0's. The string could begin with 1 and then be followed...) |
|||
| Line 3: | Line 3: | ||
Section 7.1 #24 | Section 7.1 #24 | ||
| − | a.)Let a(n) be the number of bit strings of length n containing 3 consecutive 0's. The string could begin with 1 and then be followed by a string of length n-1 containing 3 consecutive 0's, or it could start with 01 followed by a string of length n-2 containing 3 consecutive 0's, or it could start with 001, 101, 011, or 111 followed by a string of length n-3 containing 3 consecutive 0's, or it could start with 000 followed by any string of length n- | + | a.)Let a(n) be the number of bit strings of length n containing 3 consecutive 0's. The string could begin with 1 and then be followed by a string of length n-1 containing 3 consecutive 0's, or it could start with 01 followed by a string of length n-2 containing 3 consecutive 0's, or it could start with 001, 101, 011, or 111 followed by a string of length n-3 containing 3 consecutive 0's, or it could start with 000 followed by any string of length n-3. These are all the possibilities of how the string could start. So, the recurrence relation is |
a(n)=a(n-1)+a(n-2)+4a(n-3)+2^n-3. | a(n)=a(n-1)+a(n-2)+4a(n-3)+2^n-3. | ||
Revision as of 22:42, 1 March 2009
Section 7.1 #24
a.)Let a(n) be the number of bit strings of length n containing 3 consecutive 0's. The string could begin with 1 and then be followed by a string of length n-1 containing 3 consecutive 0's, or it could start with 01 followed by a string of length n-2 containing 3 consecutive 0's, or it could start with 001, 101, 011, or 111 followed by a string of length n-3 containing 3 consecutive 0's, or it could start with 000 followed by any string of length n-3. These are all the possibilities of how the string could start. So, the recurrence relation is
a(n)=a(n-1)+a(n-2)+4a(n-3)+2^n-3.
b.)Because there are no strings of length 0,1,2 containing 3 consecutive 0's the initial conditions are a(0)=a(1)=a(2)=0.
c.)Using the recurrence relation and the initial conditions we can find a(7):
a(3)=2^0=1
a(4)=1+2^1=3
a(5)=3+1+2^2=8
a(6)=8+3+4+2^3=23
a(7)=23+8+4(3)+2^4=59
