Problem 1 - Applied Discrete Structures

Question

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-10 S(k-1)+9 S(k-2)=0, S(0)=3, S(1)=11 $$

Step-by-Step Solution

Answer

The solution is \( S(k) = 9^k + 2 \).

Step 1: Characteristic Equation

The given recurrence relation is a linear homogeneous equation with constant coefficients. Start by assuming a solution of the form \( S(k) = r^k \). Substitute this into the recurrence relation: \[ r^k - 10r^{k-1} + 9r^{k-2} = 0 \] Divide the entire equation by \( r^{k-2} \): \[ r^2 - 10r + 9 = 0 \] This is our characteristic equation.

Step 2: Solve the Characteristic Equation

Solve the quadratic equation \( r^2 - 10r + 9 = 0 \) using the quadratic formula: \[ r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \] where \( a = 1, b = -10, c = 9 \). Simplifying, we find: \[ r = \frac{10 \pm \sqrt{100 - 36}}{2} = \frac{10 \pm 8}{2} \] Thus, the roots are \( r = 9 \) and \( r = 1 \). These are distinct roots.

Step 3: General Solution

Since the characteristic equation has distinct roots, the general solution of the recurrence relation is: \[ S(k) = C_1 \cdot 9^k + C_2 \cdot 1^k \] which simplifies to \( S(k) = C_1 \cdot 9^k + C_2 \).

Step 4: Apply Initial Conditions

Use the initial conditions \( S(0) = 3 \) and \( S(1) = 11 \) to solve for \( C_1 \) and \( C_2 \). Substitute \( k = 0 \) into the general solution: \[ S(0) = C_1 \cdot 9^0 + C_2 = 3 \] Thus, \( C_1 + C_2 = 3 \). Now, substitute \( k = 1 \): \[ S(1) = C_1 \cdot 9^1 + C_2 = 11 \] Thus, \( 9C_1 + C_2 = 11 \).

Step 5: Solve for Constants

Solve the system of equations: 1. \( C_1 + C_2 = 3 \) 2. \( 9C_1 + C_2 = 11 \) Subtract equation 1 from equation 2 to eliminate \( C_2 \): \[ (9C_1 + C_2) - (C_1 + C_2) = 11 - 3 \] This simplifies to \( 8C_1 = 8 \), so \( C_1 = 1 \). Substitute \( C_1 = 1 \) back into \( C_1 + C_2 = 3 \): \[ 1 + C_2 = 3 \] Thus, \( C_2 = 2 \).

Step 6: Final Solution

Substitute \( C_1 = 1 \) and \( C_2 = 2 \) back into the general solution: \[ S(k) = 1 \cdot 9^k + 2 \] This is the solution to the recurrence relation with the given initial conditions.

Key Concepts

Characteristic Equation

When working with recurrence relations, a powerful technique involves finding the characteristic equation. The characteristic equation is obtained from a linear homogeneous recurrence relation. In simple terms, it helps to determine the structure of the solutions to the recursion. Consider a recurrence relation of the form \( S(k) - 10 S(k-1) + 9 S(k-2) = 0 \). The goal is to find a polynomial that encapsulates the behaviors of this equation.
To do this, assume a solution of the form \( S(k) = r^k \). By substituting this into the given equation and factoring out common terms, we derive a characteristic equation. In our case, dividing by the lowest power term, we get a quadratic equation:

• \( r^2 - 10r + 9 = 0 \)

The roots of this equation, which we solve next, hold essential insights into the recurrence relation's solution pattern.

Linear Homogeneous Equations

Recurrence relations classify into various types, with linear homogeneous equations being one of the common and systematic ones. These are equations where all terms are functions of a single variable, and they equate to zero without any external or additional terms. In simpler terms, they have no extra constant or non-homogeneous part.
In our example, \( S(k) - 10S(k-1) + 9S(k-2) = 0 \), each term involves either \( S \) or its previous forms like \( S(k-1) \) and \( S(k-2) \). Linear homogeneous equations have a characteristic equation which helps to simplify by solving for the solution roots.
Because the equation is homogeneous, its general solution takes the form of a linear combination of these roots raised to powers reflecting position—meaning the solution is built entirely from the actions of its previous elements without adding anything externally.

Initial Conditions

Initial conditions are key to determining a specific solution to a recurrence relation. Once the general solution is obtained using the characteristic equation, these conditions specify the unique constants in the solution. Essentially, initial conditions give us specific values at starting points to solve for these constants, tailoring the general solution to fit the problem.
For instance, with initial conditions \( S(0) = 3 \) and \( S(1) = 11 \), you substitute these into your general solution. Initially, you express the general formula as \( S(k) = C_1 \cdot 9^k + C_2 \). By inputting \( k = 0 \) and \( k = 1 \) into this solution, you get two equations with the constants \( C_1 \) and \( C_2 \). Solving the resulting system of equations reveals the specific values for these constants.
This tailored approach ensures your final solution accurately reflects the characteristics of the system described by the initial problem.