problem 1: Find the following recurrence relations, but DO NOT SOLVE. Make sure to state for which values of n your relation holds, and to give appropriate initial values. Correct relations without any explanation will not receive any marks.
(a) Find a recurrence relations for a_{n}, n ≥ 0, where a_{n} is the number of n-character upper-case "words" that contain exactly one A.
(b) Find a recurrence relation for b_{n}, n ≥ 0 where b_{n} is the number of ways to partition S = {1, 2, 3, .... , n} into exactly 2 subsets.
(c) Consider the set T = {A, B, C, 1, 2, 3, 4}. For n ≥ 0, let c_{n} be the number of n-character sequences of elements of T that contain no consecutive letters (identical or distinct). For ex, 12A113A and A1B1C1A are such 7-character sequences, but AA1234B and AB12341 are not.
problem 2: Solve the given recurrence relations. For recurrence relations with complex characteristic roots, you do not need to simplify using DeMoivre's Theorem.
(a) a_{n} - 6a_{n-1} + 9a_{n -2} = 0, n ≥ 2, a_{0} = 5, a_{1} = 12.
(b) a_{n} + a_{n-2} = 0, n ≥ 2, a_{0} = 0; a_{1} = 3.
(c) a_{n+1}- 2a_{n }= 2^{n}, n ≥ 0, a_{0} = 1.
problem 3: Let an number of n-digit quaternary (0,1,2,3) sequences in which there is never a 0 anywhere to the right of a 3. Solve for an. (Hint: You will need to dene a second relation: z_{n}, the number of n-digit sequences ternary (0,1,2) sequences, and then relate z_{n} to a_{n}).