Recurrence relations with complex characteristic roots

Question

Question 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 example, 12A113A and A1B1C1A are such 7-character sequences, but AA1234B and AB12341 are not.

Question 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₀ = 5, a₁ = 12.

(b) a_n + a_n-2 = 0, n ≥ 2, a₀ = 0; a₁ = 3.

(c) a_n+1- 2a_n = 2ⁿ, n ≥ 0, a₀ = 1.

Question 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 dene a second relation: z_n, the number of n-digit sequences ternary (0,1,2) sequences, and then relate z_n to a_n).