MATH239 Study Guide - Final Guide: Substring, Partial Fraction Decomposition, Mathematical Induction

• School: University of Waterloo
• Department: Mathematics
• Course: MATH239
• Professor: Katz Eric

Document Summary

Math 239 fall 2016 assignment 5 solutions: {5 marks} let s be the set of all binary strings where the number of 0"s is congruent to 1 modulo 3 (there can be any number of 1"s). Give a recursive de nition of s, and justify your de nition. Use your recursive de nition to determine the generating series of s with respect to the lengths of the strings. (hint: partition the string after the third occurrence of 0. ) A string in s has at least one 0. If it has exactly one 0, then it is a string in {1} {0}{1} . We look for the third 0 from the left, and split the string just after that. The rst part consists of strings with exactly three 0"s, ending with a 0, so it can be expressed as {1} {0}{1} {0}{1} {0}.