Question

Solve the recurrence \(T(n)=r T(n-1)+s^{n}\), with \(T(0)=1\). (Assume that \(r \neq s .)\)

Short answer

The solution to the recurrence is \( T(n) = \frac{-r}{s-r} r^n + \frac{s}{s-r} s^n \).

Step-by-step solution

Understanding the Recurrence

The given recurrence relation is \( T(n) = r T(n-1) + s^n \) with an initial condition \( T(0) = 1 \). The terms involve a geometric progression more implicitly with a combination of homogeneous and non-homogeneous parts.

Identifying the Homogeneous Solution

First, solve the homogeneous part of the recurrence relation, \( T(n) = r T(n-1) \). This is a geometric sequence with the solution \( T_h(n) = C r^n \), where \( C \) is a constant determined by the initial conditions.

Finding the Particular Solution

Next, find a particular solution for the non-homogeneous recurrence relation. Since the non-homogeneous part is \( s^n \), assume a particular solution of the form \( T_p(n) = A s^n \), where \( A \) is a constant to be determined.

Solving for the Particular Solution

Substitute \( T_p(n) = A s^n \) into the recurrence: \[ T_p(n) = r T_p(n-1) + s^n \] becomes \[ A s^n = r (A s^{n-1}) + s^n \].Expanding, we get \[ A s^n = r A s^{n-1} + s^n \].Divide by \( s^n \) (assuming \( s eq 0 \)):\[ A = \frac{r A}{s} + 1 \].Solving for \( A \) gives \[ A(s - r) = s\] or \[ A = \frac{s}{s-r} \].

Combining Solutions

The general solution to the recurrence is the sum of the homogeneous and particular solutions: \[ T(n) = T_h(n) + T_p(n) = C r^n + \frac{s}{s-r} s^n \].

Applying Initial Condition

Use the initial condition \( T(0) = 1 \) to solve for the constant \( C \). \[ T(0) = C r^0 + \frac{s}{s-r} s^0 = C + \frac{s}{s-r} = 1 \].Solve for \( C \):\[ C = 1 - \frac{s}{s-r} = \frac{s-r - s}{s-r} = \frac{-r}{s-r} \].

Final Solution

Substitute \( C = \frac{-r}{s-r} \) back into the general solution to get: \[ T(n) = \frac{-r}{s-r} r^n + \frac{s}{s-r} s^n \].This is the closed form solution to the recurrence.

Key concepts

Homogeneous Solution

In the realm of recurrence relations, solving the homogeneous part is an essential first step. The homogeneous solution tackles the part of the recurrence that doesn't involve the extra non-homogeneous term. Given our recurrence relation: \[ T(n) = r T(n-1) + s^n \]The homogeneous version strips away the \( s^n \) component, simplifying to: \[ T(n) = r T(n-1) \]This simplifies our problem to finding a sequence that depends solely on its previous term, multiplied by a constant \( r \). Such a sequence is a geometric progression.For geometric progressions of the form \( a, ar, ar^2, \ldots \), each term is multiplied by the constant \( r \). The solution to our homogeneous equation is \[ T_h(n) = C r^n \] where \( C \) is a constant determined by initial conditions, in our case, \( T(0) = 1 \). You'll find that homogeneous solutions often form the base structure that particular solutions build upon.

Particular Solution

A particular solution addresses the non-homogeneous portion appearing separately in the recurrence relation. While a homogeneous solution deals with repetition through geometric progressions, a particular solution captures external influences like the \( s^n \) in our recurrence.To find a particular solution for:\[ T(n) = r T(n-1) + s^n \]Assume a form that mimics the non-homogeneous term, letting \( T_p(n) = A s^n \). This form anticipates the behavior induced by \( s^n \).Substitute this into the recurrence:- **Step 1**: Replace \( T_p(n) \) in the original equation.- **Step 2**: Solve for the constant \( A \) so our particular solution functions within the relation. Expanding and simplifying leads to \[ A s^n = r A s^{n-1} + s^n \]Once solved, \( A = \frac{s}{s-r} \), completing the particular solution. Each type of recurrence bears its unique particular solution, keeping in mind that the choice of form is pivotal in solving non-homogeneous equations.

Geometric Progression

A geometric progression describes sequences where each term after the first is found by multiplying the previous term by a fixed, non-zero number called the ratio.Formally, a geometric sequence is represented as:\[ a, ar, ar^2, ar^3, \ldots \]Here, \( a \) is the start term, and \( r \) is the common ratio. The power of geometric progressions lies in their simplicity and prevalence in recurrence relations.In our recurrence, the homogeneous equation showcases one such example:\[ T(n)= r T(n-1) \] Enhancing recognition, every problem involving a geometric progression can be quickly identified by the repetitive pattern of multiplying by \( r \). For instance, the solution for the homogeneous part \[ T_h(n) = C r^n \] perfectly aligns with the structure of a geometric progression. Understanding how they progress helps in both forming the structure of the homogeneous solution and in predicting patterns in more complex recurrence scenarios.