ID: MATH 239 Assignment 10, Winter 2017, Page 1 of 4 Initials: 1. {6 marks} Fix k 1. Find the generating series for binary strings with no 01k 0 substring (where 1k means k copies of 1). Justify your decomposition and write your generating series as a ratio of polynomials. ID: MATH 239 Assignment 10, Winter 2017, Page 2 of 4 Initials: 2. {6 marks} Consider the set C of binary strings which includes the empty string and for which every nonempty element w of C, the first bit of w is 0, the last bit of w is 1, and the rest of w consists of a concatenation of zero of more elements of C. Use the recursive decomposition technique to find an equation which the generating series of C satisfies. You do not need to solve your equation for C (x). ID: MATH 239 Assignment 10, Winter 2017, Page 3 of 4 3. {5 marks} Solve the recurrence an = an1 + 2an2 for n 2 with initial conditions a0 = 2, a1 = 3. Initials: ID: MATH 239 Assignment 10, Winter 2017, Page 4 of 4 Initials: 4. {5 marks} Solve the recurrence bn = 3bn1 + 4bn3 for n 3 with initial conditions b0 = 9, b1 = 9, b2 = 18