Recitation 4 3. Using strong induction, prove that the number of winning configurations on a 2 x n Mini-Tetris board(n 1)is T Solution. The proof is by strong induction on n, with the induction hypothesis Tn (2++(1))/3. The hypothesis is true for n=l and n= 2, since we determined above that T1=1=(21+1+(-1)2)/3andT2=3=(22+1+(-1))/3. Now suppose n >2 and assume that the hypothesis holds for all k< n Starting from the equation derived in the preceding problem part, we have 2"+(-1)+2.2+(-1)-2 3 We use the induction hypothesis twice in the second step, and then simplify in the third and fourth steps. This completes the inductive step. By strong induction, the hypothesis holds for all n >1Recitation 4 3 3. Using strong induction, prove that the number of winning configurations on a 2 × n Mini­Tetris board (n ≥ 1) is: n 2n+1 + (−1) Tn = 3 Solution. The proof is by strong induction on n, with the induction hypothesis Tn = (2n+1 + (−1)n)/3. The hypothesis is true for n = 1 and n = 2, since we determined above 1+1 + (−1) that T1 = 1 = (2 2+1 + (−1) 1)/3 and T2 = 3 = (2 2)/3. Now suppose n ≥ 2 and assume that the hypothesis holds for all k < n. Starting from the equation derived in the preceding problem part, we have: Tn = = Tn−1 + 2Tn−2 2n + (−1)n−1 3 + 2 · 2n−1 + (−1)n−2 3 = 2n − (−1)n + 2n + 2(−1)n 3 3 = 2n+1 + (−1)n 3 We use the induction hypothesis twice in the second step, and then simplify in the third and fourth steps. This completes the inductive step. By strong induction, the hypothesis holds for all n ≥ 1