| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | [[Category: | + | [[Category:MA375]] |
| + | [[Category:math]] | ||
| + | [[Category:discrete math]] | ||
| + | [[Category:problem solving]] | ||
| + | |||
| + | =[[MA375]]: [[MA_375_Spring_2009_Walther_Week_5| Solution to a homework problem from this week or last week's homework]]= | ||
| + | Spring 2009, Prof. Walther | ||
| + | ---- | ||
| + | |||
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 | + | 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 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)+ | + | a(n)=a(n-1)+a(n-2)+a(n-3)+2^n-3. |
| − | b.) | + | b.) The initial conditions are a(1)=0 a(2)=0 a(3)=1. |
c.)Using the recurrence relation and the initial conditions we can find a(7): | c.)Using the recurrence relation and the initial conditions we can find a(7): | ||
| − | |||
a(4)=1+2^1=3 | a(4)=1+2^1=3 | ||
a(5)=3+1+2^2=8 | a(5)=3+1+2^2=8 | ||
| − | a(6)=8+3+ | + | a(6)=8+3+1+2^3=20 |
| − | a(7)= | + | a(7)=20+8+3+2^4=47 |
| + | ---- | ||
| + | [[MA375_%28WaltherSpring2009%29|Back to MA375, Spring 2009, Prof. Walther]] | ||
Latest revision as of 08:19, 20 May 2013
MA375: Solution to a homework problem from this week or last week's homework
Spring 2009, Prof. Walther
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 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)+a(n-3)+2^n-3.
b.) The initial conditions are a(1)=0 a(2)=0 a(3)=1.
c.)Using the recurrence relation and the initial conditions we can find a(7):
a(4)=1+2^1=3
a(5)=3+1+2^2=8
a(6)=8+3+1+2^3=20
a(7)=20+8+3+2^4=47
