Problem 4 - Applied Discrete Structures

Question

Solve the following sets of recurrence relations and initial conditions: $$ S(k)-20 S(k-1)+100 S(k-2)=0, S(0)=2, S(1)=50 $$

Step-by-Step Solution

Answer

The explicit formula is \( S(k) = (2 + 3k) \cdot 10^k \).

Step 1: Identify the Recurrence Relation

The given recurrence relation is \( S(k) - 20 S(k-1) + 100 S(k-2) = 0 \). Our task is to find the explicit form of \( S(k) \) based on this recurrence relation and the initial conditions \( S(0) = 2 \) and \( S(1) = 50 \).

Step 2: Define the Characteristic Equation

To solve the recurrence relation, we first need to find the characteristic equation, which is given by transforming the recurrence into \( r^2 - 20r + 100 = 0 \). This equation will be used to find the roots that will help express the general form of the sequence.

Step 3: Solve the Characteristic Equation

Now, we solve the characteristic equation \( r^2 - 20r + 100 = 0 \). This can be factored as \( (r - 10)^2 = 0 \), which gives a repeated root \( r = 10 \). Since the root is repeated, the general solution will include a linear term associated with it.

Step 4: Write the General Solution

For a repeated root \( r = 10 \) of multiplicity 2, the general solution of the recurrence relation takes the form: \[ S(k) = A \cdot 10^k + B \cdot k \cdot 10^k \] where \( A \) and \( B \) are constants to be determined using the initial conditions.

Step 5: Apply Initial Conditions

Using the initial condition \( S(0) = 2 \), substitute \( k = 0 \) into the general solution: \[ A \cdot 10^0 + B \cdot 0 \cdot 10^0 = 2 \] which simplifies to \( A = 2 \). Next, use \( S(1) = 50 \) with the sequence formula: \[ 2 \cdot 10^1 + B \cdot 1 \cdot 10^1 = 50 \] This simplifies to \( 20 + 10B = 50 \) which yields \( B = 3 \).

Step 6: Write the Explicit Formula

Substituting \( A = 2 \) and \( B = 3 \) back into the general solution, we arrive at the explicit formula for the sequence: \[ S(k) = 2 \cdot 10^k + 3k \cdot 10^k \] Simplifying further, we get: \[ S(k) = (2 + 3k) \cdot 10^k \]

Step 7: Verify the Solution

Verify the solution by substituting \( k = 0 \) and \( k = 1 \) back into the explicit formula. For \( k = 0 \), \( S(0) = (2 + 3 \times 0) \cdot 10^0 = 2 \) matches the initial condition. For \( k = 1 \), \( S(1) = (2 + 3 \times 1) \cdot 10^1 = 50 \), which also matches. Hence, our solution is verified.

Key Concepts

Characteristic Equation

Solving recurrence relations often involves creating a characteristic equation. This equation is a transformed version of the recurrence relation, designed to identify a pattern or trend in the sequence's behavior.
The recurrence relation in this exercise is given by \( S(k) - 20S(k-1) + 100S(k-2) = 0 \). To create the characteristic equation, you replace each term with a power of \( r \). So, the sequence transforms into \[ r^2 - 20r + 100 = 0 \].
This equation represents the possible values (or roots) that describe the long-term behavior of the sequence. Thus, solving it is crucial for finding the general solution to the recurrence relation.

General Solution

Once we have the characteristic equation, the next step is to solve it to find the roots. For this problem, solving \( r^2 - 20r + 100 = 0 \) results in finding the root \( r = 10 \) with a multiplicity of 2.
When a root is repeated, the general solution of the recurrence is not a simple exponential form. Instead, we use a special formula that accounts for this repetition: \[ S(k) = A \cdot r^k + B \cdot k \cdot r^k \].
Substituting the repeated root \( r = 10 \) into this formula, we obtain: \[ S(k) = A \cdot 10^k + B \cdot k \cdot 10^k \].
This form allows us to incorporate the root’s repetition through the linear term \( k \), providing a richer expression that captures the sequence's behavior.

Initial Conditions

Initial conditions are specific values given for certain positions in the sequence, necessary for determining the constants within the general solution. In this exercise, the initial conditions are \( S(0) = 2 \) and \( S(1) = 50 \).
These initial conditions help resolve the constants \( A \) and \( B \) within the general solution. For \( S(0) = 2 \), substituting \( k = 0 \) into \( S(k) = A \cdot 10^k + B \cdot k \cdot 10^k \) simplifies to \( A = 2 \).
Next, using \( S(1) = 50 \) gives another equation: \( 2 \cdot 10^1 + B \cdot 1 \cdot 10^1 = 50 \). Solving this yields \( B = 3 \).
Thus, the constants \( A \) and \( B \), determined by the initial conditions, finalize the precise expression for the sequence, rendered as \( S(k) = (2 + 3k) \cdot 10^k \).