A block in a bitstring s is a maximal sequence of consecutive 1's. For example, the bitstring s = 11011101000 contains the three blocks 11 0 111 0 1 000 A bitstring is called awesome, if each of its blocks has an even length. Thus, the bit-string above is not awesome, whereas both bitstrings 00011011110 and 0000000 are awesome. For any integer n greaterthanorequalto 1. Let An denote the number of awesome bitstrings of length n. Determine A_1, A_2. A_3, and A_4. Determine the value of A_n i.e.. express A_n in terms of numbers that we have seen in class. The Fibonacci numbers are defined as follows: f_0 = 0. f_1 = 1, and f_n = f_n + 1 + f_ greaterthanorequalto 2 In class, we have seen that for any m greaterthanorequalto 1. Let n greaterthanorequalto 2 be an integer. What is the number of 00-free bit-strings of length 2n - 1 for which the bit in the middle position is equal to 1 ? Let n greaterthanorequalto 3 be an integer. What is the number of 00-free bitstrings of length 2n - 1 for which the bit in the middle position is equal to 0? Use the previous results to prove that for any integer n greaterthanorequalto 3, f_2n + 1 = f_n^2 + f_n + 1^2 A block in a bitstring s is a maximal sequence of consecutive 1's. For example, the bitstring s = 11011101000 contains the three blocks 11 0 111 0 1 000 A bitstring is called awesome, if each of its blocks has an even length. Thus, the bit-string above is not awesome, whereas both bitstrings 00011011110 and 0000000 are awesome. For any integer n greaterthanorequalto 1. Let An denote the number of awesome bitstrings of length n. Determine A_1, A_2. A_3, and A_4. Determine the value of A_n i.e.. express A_n in terms of numbers that we have seen in class. The Fibonacci numbers are defined as follows: f_0 = 0. f_1 = 1, and f_n = f_n + 1 + f_ greaterthanorequalto 2 In class, we have seen that for any m greaterthanorequalto 1. Let n greaterthanorequalto 2 be an integer. What is the number of 00-free bit-strings of length 2n - 1 for which the bit in the middle position is equal to 1 ? Let n greaterthanorequalto 3 be an integer. What is the number of 00-free bitstrings of length 2n - 1 for which the bit in the middle position is equal to 0? Use the previous results to prove that for any integer n greaterthanorequalto 3, f_2n + 1 = f_n^2 + f_n + 1^2