Note that the explanation is the most important part of this question. The way to approach this question is very much like we approached the Tower of Hanoi: we figured out a recursive algorithm to move the discs, then derived the recurrence relation for the cost, based on the algorithm. Here, you need to figure out recursive algorithms to build longer valid strings from shorter valid strings. Once you have each algorithm, then you can derive the entire recursive definition of its associated sequence quite easily.

Q2 (10 points) Recursively Defined Sequence #2: Integer Strings 1. Define the sequence Tn = Number of different n-digit (without leading Os) positive integers that do not contain the string "99" in their decimal representation. For example, 929 would be included in the count for Tz but 299, 992, and 029 would not be the first two because they contain the string "99" and the third because 29 is considered to be a 2-digit positive integer. Give a recursive definition for Tr. Your definition must include: o All the initial conditions of the sequence. A recurrence relation for Tn as a function of some of the elements of the sequence that precede it. o The values of n for which this recurrence relation applies. o An explanation of how this recurrence relation was derived based on an algorithm to build strings of length n from shorter strings. 2. We will now generalize this sequence for any base m, including base ten. For any base m, call the largest digit in that base k. For example, in base ten, k=9, in base two k=1, in base sixteen (hex) k=F. As you can see, k is simply the character representing m-1. Define the sequence Bm,n = Number of different n-digit (without leading Os) positive integers that do not contain the string kk in their representation in base m. For example, F3F would be included in the count for B16,3 but 3FF, FF3, and 03F would not be the first two because they contain the string "FF" and the third because 3F is considered to be a 2-digit positive hex integer. Give a recursive definition for Bm,n. Your definition must include: All the initial conditions of the sequence. A recurrence relation for Bm,n as a function of some of the elements of the sequence that precede it. The recurrence is on n, not on m that is assumed to be fixed. o The values of n for which this recurrence relation applies. An explanation of how this recurrence relation was derived based on an algorithm to build strings of length n from shorter strings