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- in 1 in 1 that start and end in 1 (where n 2 2). tions of a set with n elements using the expansion method Reminder: We used expansion method in class to generate a guess for the number of moves in the Towers of Hanoi problem.

Explanation / Answer

Solution for 1:

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

Solution for 2:

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.