Problem 26 - Discrete Mathematics with Applications

Question

Using generating functions, solve each LHRRWCC. $$a_{n}=3 a_{n-1}+4 a_{n-2}-12 a_{n-3}, a_{0}=3, a_{1}=-7, a_{2}=7$$

Step-by-Step Solution

Answer

The explicit form of the given sequence is: $$ a_n = 1 + 3^n + (-2)^n $$

Step 1: Write down the characteristic equation

The characteristic equation for the given recurrence relation is: \[ r^{3}-3r^{2}-4r+12=0 \]

Step 2: Find roots of the characteristic equation

We need to find the roots of the equation \(r^3 - 3r^2 - 4r + 12 = 0\). The roots can be found by factoring the equation or using a numerical method. In this case, we can quickly find that \(r=1\) is a root: \[ (1)^3 - 3(1)^2 - 4(1) + 12 = 1 - 3 - 4 + 12 = 0 \] Now, using synthetic division, we find the other quadratic factor: \[ (r - 1)(r^2 - 2r - 6) = 0 \] So, the roots of the characteristic equation are \(r = 1\) and the roots of \(r^2 - 2r - 6\). Factoring further, we get: \[ (r - 1)(r - 3)(r + 2) = 0 \] The roots are \(r_1 = 1\), \(r_2 = 3\), and \(r_3 = -2\).

Step 3: Write the general solution using the roots

From the roots of the characteristic equation, we write down the general solution in the form: \[ a_n = c_1 r_1^n + c_2 r_2^n + c_3 r_3^n \] or \[ a_n = c_1 (1)^n + c_2 (3)^n + c_3 (-2)^n \]

Step 4: Find the coefficients using the given values of the sequence

We use the given values of the sequence to find the coefficients: For \(n=0\), \(a_0 = 3\): \[ 3 = c_1 (1)^0 + c_2 (3)^0 + c_3 (-2)^0 = c_1 + c_2 + c_3 \] For \(n=1\), \(a_1 = -7\): \[ -7 = c_1 (1)^1 + c_2 (3)^1 + c_3 (-2)^1 = c_1 + 3c_2 -2c_3 \] For \(n=2\), \(a_2 = 7\): \[ 7 = c_1 (1)^2 + c_2 (3)^2 + c_3 (-2)^2 = c_1 + 9c_2 + 4c_3 \]

Step 5: Solve the system of equations for the coefficients

Now we have the following system of equations: \[ \begin{cases} c_1+c_2+c_3=3 \\ c_1+3c_2-2c_3=-7 \\ c_1+9c_2+4c_3=7 \end{cases} \] Solving this system, we find \(c_1 = 1\), \(c_2 = 1\), and \(c_3 = 1\).

Step 6: Write the explicit form of the sequence

Now that we have all the coefficients, we can write the explicit form of the sequence: \[ a_n = 1 \cdot 1^n + 1\cdot 3^n + 1 \cdot (-2)^n = 1 + 3^n + (-2)^n \] Thus, the explicit form of the given sequence is: $$ a_n = 1 + 3^n + (-2)^n $$