4. Applications of Recurrence Relations (4 points) (1) (0.5 points) Count the nu

Question

4. Applications of Recurrence Relations (4 points) (1) (0.5 points) Count the number of length 2 bit strings that start and end (2) (0.5 points) Count the number of length 3 bit strings that start and end (3) (1.5 points) Find a recurrence relation for the number length n bit strings 4) (1.5 points) Use this recurrence relation to find the number of permuta- Reminder: We used expansion method in class to generate a guess ini. in 1 that start and end in 1 (where n2 2). for the number of moves in the Towers of Hanoi problem

Explanation / Answer

4

a. For a 2 bit string ,for the strings that start with a 1 ,we would have 2-1=1 bit to choose.

Similary for the 2 bit strings that ends with a 1,we should have 2-1=1 bit to choose.

The sum 2^1+2^1=4 (ouput)double-counts the bit strings that start and ends with 1

b. Similarly for a 3 bit string for the string that starts with 1, we would have 3-1=2 bit to choose.

For the 3bit strings that ends with a 1,we should have 3-1=2 bit to choose.

Combinedly we have the sum 2^2+2^2=4+4=8(output) double-counts the bit strings that start and ends with 1

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.