Problem 1. [15 points] Consider the following sequence of predicates Q1(x1)=x1 Q2(x1,x2)=x1→m2 Q Q4(x1,x2,x3,x4)=(x1→x2)→x3)→4 Q5(x1,x2,x3,x4,x5)=(x1→x2)→x3)→x4)→5 Let Tn be the number of different true/false settings of the variables T1, 2,.. In for which Qn(a1, T2,..., n)is true. For example, T2= 3 since Q2(1, T2) is true for 3 different settings of the variables f1 and 2: TT TFF FTF TFTT FF T (a) Express Tn+1 in terms of Tn, assuming n> 1 Solution We have n+1(T1,x 1)=Qn( If an+1 is true, then Qn+1 is true for all 2n settings of the variables 1, 2, .. In. If n+i is false, then Qn+i is true for all settings of c1, 12, .. n except for the Tn settings that make Qn true. Thus, altogether we have 21+21-Tn=2 n (b)Use induction to prove that Tn=3(2n++(1)m) for n> 1. You may assume your answer to the previous part without proof Solution. The proof is by induction. Let P(n) be the proposition that Tn=(2n++ Base case: There is a single setting of 1 that makes Q1(a1)=1 true, and Ti 1))/3=1. Therefore, P(O)is true Inductive step: For n>0, we assume P(n)and reason as follows Tn+1=2+1-Tn 2n+2+(-1)x+1 3 The first step uses the result from the previous problem part, the second uses the induction hypothesis P(n), and the third is simplification. This implies that P(n+1 is true. By the principle of induction, P(n) is true for alln> 1� � Final Exam 2 Problem 1. [15 points] Consider the following sequence of predicates: Q1(x1) = x1 Q2(x1, x2) = x1 ⇒ x2 Q3(x1, x2, x3) = (x1 ⇒ x2) ⇒ x3 Q4(x1, x2, x3, x4) = ((x1 ⇒ x2) ⇒ x3) ⇒ x4 Q5(x1, x2, x3, x4, x5) = (((x1 ⇒ x2) ⇒ x3) ⇒ x4) ⇒ x5 . . . . . . Let Tn be the number of different true/false settings of the variables x1, x2, . . . , xn for which Qn(x1, x2, . . . , xn) is true. For example, T2 = 3 since Q2(x1, x2) is true for 3 different settings of the variables x1 and x2: Q2(x1, x2) T T T F F T F F x1 x2 T F T T (a) Express Tn+1 in terms of Tn, assuming n ≥ 1. Solution. We have: Qn+1(x1, x2, . . . , xn+1) = Qn(x1, x2, . . . , xn) ⇒ xn+1 If xn+1 is true, then Qn+1 is true for all 2n settings of the variables x1, x2, . . . , xn. If xn+1 is false, then Qn+1 is true for all settings of x1, x2, . . . , xn except for the Tn settings that make Qn true. Thus, altogether we have: n Tn+1 = 2n + 2 − Tn = 2n+1 − Tn 1 (b) Use induction to prove that Tn = 3 (2n+1 + (−1)n) for n ≥ 1. You may assume your answer to the previous part without proof. Solution. The proof is by induction. Let P(n) be the proposition that Tn = (2n+1 + (−1)n)/3. Base case: There is a single setting of x1 that makes Q1(x1) = x1 true, and T1 = (21+1 + (−1)1)/3 = 1. Therefore, P(0) is true. Inductive step: For n ≥ 0, we assume P(n) and reason as follows: Tn+1 = 2n+1 − Tn n 2n+1 + (−1) = 2n+1 − 3 n+1 2n+2 + (−1) = 3 The first step uses the result from the previous problem part, the second uses the induction hypothesis P(n), and the third is simplification. This implies that P(n+1) is true. By the principle of induction, P(n) is true for all n ≥ 1