Problem 43 - Discrete Mathematics with Applications

Question

Let \(\alpha\) be a characteristic root of the LHRRWCC \(a_{n}=a a_{n-1}+b a_{n-2}+\) \(c a_{n-3}\) with degree of multiplicity three. Show that \(\alpha^{n}, n \alpha^{n}, n^{2} \alpha^{n}\) are solutions of LHRRWCC.

Step-by-Step Solution

Answer

After substituting \(α^n\), \(nα^n\), and \(n^2α^n\) into given LHRRWCC, we obtained the equations \(α^n = α^{n-1}(a + bα + cα^2)\), \(nα^n = α^{n-1}[(n-1)a + (n-2)bα + (n-3)cα^2]\), and \(n^2α^n = α^{n-1}[(n-1)^2a + (n-2)^2bα + (n-3)^2cα^2]\) respectively. Since α is a root with multiplicity 3, these equations are satisfied, proving that \(α^n\), \(nα^n\), and \(n^2α^n\) are solutions to the given LHRRWCC.

Step 1: Substituting \(α^n\) into the LHRRWCC

Let's first consider the function \(a_n = α^n\). We can find \(a_{n-1}\), \(a_{n-2}\), and \(a_{n-3}\) by replacing n with n-1, n-2, and n-3, respectively. \[a_{n-1} = α^{n-1}\] \[a_{n-2} = α^{n-2}\] \[a_{n-3} = α^{n-3}\] Now, we'll substitute these expressions into the LHRRWCC: \[α^n = a(α^{n-1}) + b(α^{n-2}) + c(α^{n-3})\]

Step 2: Simplify and verify the first solution

Let's simplify the equation: \[α^n = α^{n-1}(a + bα + cα^2)\] Since \(α\) is a root with multiplicity 3, the above equation is satisfied, and we can conclude that \(α^n\) is a solution to the LHRRWCC.

Step 3: Substituting \(nα^n\) into the LHRRWCC

Now, let's consider the function \(a_n = nα^n\). We can find the related expressions: \[a_{n-1} = (n-1)α^{n-1}\] \[a_{n-2} = (n-2)α^{n-2}\] \[a_{n-3} = (n-3)α^{n-3}\] Now, we'll substitute these expressions into the LHRRWCC: \[nα^n = a(n-1)α^{n-1} + b(n-2)α^{n-2} + c(n-3)α^{n-3}\]

Step 4: Simplify and verify the second solution

Let's simplify the equation: \[nα^n = α^{n-1}[(n-1)a + (n-2)bα + (n-3)cα^2]\] Since \(α\) is a root with multiplicity 3, the above equation is satisfied, and we can conclude that \(nα^n\) is a solution to the LHRRWCC.

Step 5: Substituting \(n^2α^n\) into the LHRRWCC

Finally, let's consider the function \(a_n = n^2α^n\). We can find the related expressions: \[a_{n-1} = (n-1)^2α^{n-1}\] \[a_{n-2} = (n-2)^2α^{n-2}\] \[a_{n-3} = (n-3)^2α^{n-3}\] Now, we'll substitute these expressions into the LHRRWCC: \[n^2α^n = a(n-1)^2α^{n-1} + b(n-2)^2α^{n-2} + c(n-3)^2α^{n-3}\]

Step 6: Simplify and verify the third solution

Let's simplify the equation: \[n^2α^n = α^{n-1}[(n-1)^2a + (n-2)^2bα + (n-3)^2cα^2]\] Since \(α\) is a root with multiplicity 3, the above equation is satisfied, and we can conclude that \(n^2α^n\) is a solution to the LHRRWCC. In conclusion, we have shown that \(α^n\), \(nα^n\), and \(n^2α^n\) are solutions of the given LHRRWCC.

Key Concepts

Characteristic Roots

Characteristic roots, often referred to as eigenvalues in other contexts, play a vital role in solving homogeneous linear recurrence relations with constant coefficients (LHRRWCC). These characteristic roots are the solutions to the characteristic equation, which is derived from the recurrence relation by assuming a solution of the form \( a_n = r^n \) and substituting it back into the original recurrence. The roots determine the behavior of the sequence defined by the recurrence relation.

In the context of discrete mathematics, especially when dealing with LHRRWCC, a characteristic root with multiplicity indicates that not only is \( r \) itself a solution, but also \( nr \) and \( n^2r \) when the multiplicity is three, as shown in the given exercise. In each step of the provided solution, we substitute these forms back into the original relation to prove that they indeed satisfy the recurrence, confirming their validity as solutions.

Discrete Mathematics

Discrete mathematics is a branch of mathematics dealing with discrete elements that use algebra and arithmetic. It is foundational for topics in computer science, cryptography, and combinatorics, among others. In the realm of discrete mathematics, recurrence relations are a crucial concept because they define sequences recursively and appear frequently in algorithms and counting problems.

The exercise presented falls under discrete mathematics, specifically in the study of sequences and how they evolve based on previous terms. The significance of understanding such relations is not merely for academic purposes, but also for practical applications such as computer programming, where understanding algorithm complexity often involves recurrence relations.

Recurrence Relations

Recurrence relations are equations that recursively define a sequence, where each term is a function of its preceding terms. The LHRRWCC in the exercise is a third-order linear recurrence relation because the next term in the sequence depends linearly on the previous three terms. Solving such equations typically involves finding the general form of the sequence's nth term.

To verify the solutions to these recurrence relations, we substitute potential solutions back into the original relation and show that they satisfy it. As seen in the steps of the given solution, proving that expressions like \( \alpha^n \) and *polynomials times* \( \alpha^n \) are indeed solutions entails deriving related expressions for the previous sequence terms, substituting them into the LHRRWCC, and simplifying the resultant equation.