Discrete Mathematics

Let T(n) be the set of all strings of 1's and 2's that add up to n. For example: 21221 elementof T(8) because it is a string of 1's and 2's that add up to 8. (a) Show that | T(0) | and | T(1) | and by using a combinatorial argument, show that | T(n) | = | T(n - 1) | + | T(n - 2) |. (This shows that | T(n) | is the nth Fibonacci number!) (b) List all 13 elements of T(6) in lexicographic ordering, labeling them from 0 to 12. (Notice that all strings that start with 1 occur before all strings that start with 2.) (c) If we list all elements of T(n) in lexicographic ordering, then all the strings that start with 1 will be in positions before | T(n - 1) | and all strings that start with 2 will be in positions at or after | T(n - 1) |. Consider the following encoding algorithm that uses this fact: procedure LexEncode(s_1 s_2.... s_k, n) (s_1 s_2 ... s_k is a sequence of 1's and 2's that add up to n.) if n == 0: return 0 if s_1 == 1: return LexEncode (s_2, ..., s_k, n - 1) if s_1 == 2: return F_n - 1 + Lex Encode (s_2, ..., s_k, n - 2) Where F_n is the nth Fibonacci number: F_0 = 1, F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, F_5 = 8, F_6 = 13, F_7 = 21, F_8 = 34, F_9 = 55, F_10 = 89, ... Use this encoding algorithm to compute LexEncode(1221212, 11)