Problem 15 - Discrete Mathematics with Applications

Question

Solve each LHRRWCC. $$a_{n}=a_{n-1}+a_{n-2}, a_{0}=2, a_{1}=3$$

Step-by-Step Solution

Answer

The general formula for the given LHRRWCC is: \[a_n = \frac{1 + \sqrt{5}}{2} \left(\frac{1 + \sqrt{5}}{2}\right)^n + \frac{1 - \sqrt{5}}{2} \left(\frac{1 - \sqrt{5}}{2}\right)^n\]

Step 1: Identify the characteristic equation from the given recurrence relation

Transform the given recurrence relation, $$a_{n} = a_{n-1} + a_{n-2}$$, into a characteristic equation by replacing \(a_n\) with \(r^n\), \(a_{n-1}\) with \(r^{n-1}\), and \(a_{n-2}\) with \(r^{n-2}\). The characteristic equation becomes: \(r^n = r^{n-1} + r^{n-2}\).

Step 2: Simplify the characteristic equation

Factor out the term with the least exponent, which is \(r^{n-2}\), from the characteristic equation: \[r^{n-2}(r^2 - r - 1) = 0\]

Step 3: Solve for r in the simplified characteristic equation

The roots of the equation will be the solutions for r. As the quadratic equation \(r^2 - r - 1 = 0\) doesn't have rational roots, we can use the quadratic formula to solve for r: \[r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\] So, \[r = \frac{1 \pm \sqrt{1^2 - 4(1)(-1)}}{2(1)} = \frac{1 \pm \sqrt{5}}{2}\] Therefore, roots r1 and r2 are: $$r_1 = \frac{1 + \sqrt{5}}{2}$$ and $$r_2 = \frac{1 - \sqrt{5}}{2}$$

Step 4: Use the general formula for LHRRWCC

The closed-form expression for the given LHRRWCC is: \[a_n = A(r_1)^n + B(r_2)^n\]

Step 5: Use initial values to find A and B

Use provided initial values $$a_{0} = 2$$ and $$a_{1} = 3$$, and our expressions concerning roots $$r_1$$ and $$r_2$$ to create a system of equations: $$a_0 = A(r_1)^0 + B(r_2)^0 = 2$$ $$a_1 = A(r_1)^1 + B(r_2)^1 = 3$$ The system of equations becomes: \[A + B = 2\] \[A\frac{1 + \sqrt{5}}{2} + B\frac{1 - \sqrt{5}}{2} = 3\]

Step 6: Solve the system of equations

Solve the system of equations for A and B using substitution or elimination method. After solving the system of equations, we get: $$A = \frac{1 + \sqrt{5}}{2}$$ and $$B = \frac{1 - \sqrt{5}}{2}$$

Step 7: Write the final closed-form expression

Using the values of A and B, the general formula for the given LHRRWCC is: \[a_n = \frac{1 + \sqrt{5}}{2} \left(\frac{1 + \sqrt{5}}{2}\right)^n + \frac{1 - \sqrt{5}}{2} \left(\frac{1 - \sqrt{5}}{2}\right)^n\]