Some of the following questions ask for a closed-form formula. This is a formula that is non- recursive and doesn's use the summation () or product (IT) notation. These formulas can use any of the special functions we've seen in class, including the factorial function and binomial coefficients. 4. Consider the set An of strings over the 4-character alphabet {a,b,c,d} whose length is n and for which cc does not appear as a consecutive substring. For example: A] = {f} Az = {a,b,c,d} A2 = {aa, ab, ac, ad, ba, bb, bc, bd, ca,cb, x, cd, da, db, dc, dd) Write a recurrence for An). Then, using induction, show that this recurrence solves to Anl= (1/2+5.21/42). " ++(1/2-5./21/42) - BM , where a =(3+ 21)/2 and 3 = (3-21)/2. 5. Consider the set Sn of binary strings whose length is n and for which 010 does not appear as a consecutive substring. For example, So = {{}, Si = {0,1}, S2 = {00,01, 10, 11}, S3 = {000,001, OY,011, 100, 101, 110, 111} S4 = {0000, 0001, 0010, 0011, 0100, 011, 0110,0111, 1000, 1001, 100, 1011, 1100, 1101, 1110, 1111} a. Argue that for n > 3, Sn] = \Sn-1]+) Sn-k] +2. ke-3 Some of the following questions ask for a closed-form formula. This is a formula that is non- recursive and doesn's use the summation () or product (IT) notation. These formulas can use any of the special functions we've seen in class, including the factorial function and binomial coefficients. 4. Consider the set An of strings over the 4-character alphabet {a,b,c,d} whose length is n and for which cc does not appear as a consecutive substring. For example: A] = {f} Az = {a,b,c,d} A2 = {aa, ab, ac, ad, ba, bb, bc, bd, ca,cb, x, cd, da, db, dc, dd) Write a recurrence for An). Then, using induction, show that this recurrence solves to Anl= (1/2+5.21/42). " ++(1/2-5./21/42) - BM , where a =(3+ 21)/2 and 3 = (3-21)/2. 5. Consider the set Sn of binary strings whose length is n and for which 010 does not appear as a consecutive substring. For example, So = {{}, Si = {0,1}, S2 = {00,01, 10, 11}, S3 = {000,001, OY,011, 100, 101, 110, 111} S4 = {0000, 0001, 0010, 0011, 0100, 011, 0110,0111, 1000, 1001, 100, 1011, 1100, 1101, 1110, 1111} a. Argue that for n > 3, Sn] = \Sn-1]+) Sn-k] +2. ke-3