1. Consider the function defined by: (i)f(0) = 1, f(1) = 2: (ii)f(n) = f (n-2) + 2 f(n-1). a) Prove, by induction, thatf(n) >= 2^nfor alln>= 0. The property being proven is P(n): f(n) >= 2^n Base cases: f(0) = 1 >= 1 = 2^0; f(1) = 2 >= 2 = 2^1. Induction step: Assume that for all i <=k, f(i) >= 2^i. Consider: f(k+1) = f (k-1) + 2 f(k-2) >= 2^(k-1) + 2 (2^k) >= 2 (2^k) = 2^(k+1). Therefore, by induction f(n) >= 2^n for all n>=0. NOTE: You must use the second principle of induction, as the inductive step uses two smaller cases, not just one. In the same sense, you do need two base cases. b) Isf(n) <= 3^nfor alln>= 0? [No proof is required here.]YES. This IS also provable by induction. The base cases are obvious: 1 <= 1, 2<= 3. The inductive step comes down to: f(k+1) = f (k-1) + 2 f(k-2) <= 3^(k-1) + 2 (3^k) = 3^(k-1)[1+ 6] <= 3^(k-1)[9] = 3^(k+1) 2. Consider the subsetSof strings of0s and1s generated by the recursive definition: (i)1 in Sand0 in S; (ii) if\alpha in Sthen1\alpha 1 in Sand0\alpha 0 in S. a) Prove that if \beta in S , then the reversal of \beta, obtained by reversing the order of the symbols in the string, written r(\beta), is equal to \beta . [That is \beta is a palindrome.] By induction on the steps of the recusive construction: Base case: If \beta has length=1, then r(\beta) = \beta. Induction step. Assume r(\alpha) = \alpha for all strings in S of length <= k . Let \beta be a string in S of length k+1 Therefore \beta= 1\alpha1 or \beta= 0\alpha0. Now r(1\alpha1) = 1 (r(\alpha)) 1 = 1\alpha1, by the induction assumption. Similarly: r(0\alpha0) = 0 (r(\alpha)) 0 = 0\alpha0, In either case, \beta is a palindrome, as required. By induction, all strings \beta in S are palindromes. b) List all strings in S of length 0, 1, 2, 3. Strings of length 0: NONE The only such string is the empty string, but it is not in S. Strings of length 1: 1, 0 Strings of length 2: NONE The recursive step adds two symbols to a smaller string, and there were no strings of length 0. Strings of length 3. 111, 101, 010, 000. A string which is a palindrome but is not in S: \lambda (the empty string) OR 11, 00. c) How would you change the definition of S so that the new set contains all palindromes of 0 s and 1 s. [No proof is required, just a revised definition.]Add to step (i) the empty string\lambda in S. This will generate all the even palindromes. Almost a right answer: Add 11, 00 in S. This just misses the empty string, which is indeed a palindrome.