question 1 evaluate the following recurrence

Question

Question 1. Evaluate the following recurrence relations, but DO NOT SOLVE. Make sure to state for which values of n your relation holds, and to provide appropriate initial values. Correct relations without any explanation will not receive any marks.

(a) Find a recurrence relations for a_n, n ≥ 0, where an 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 bn 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 following 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 a_n.