Line 6: Line 6:
 
                     a(n)=a(n-1)+a(n-2)+a(n-3)+2^n-3.
 
                     a(n)=a(n-1)+a(n-2)+a(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(1)=0 a(2)=0 a(3)=1
+
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):

Revision as of 08:41, 3 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 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

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang