Question

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

Short answer

The solution is \( T(n) = r^{2n}. \)

Step-by-step solution

Analyze the Homogeneous Solution

The homogeneous part of the recurrence is \[ T(n) = r T(n-1). \]Assuming a solution of the form \( T_h(n) = A r^n \), we plug this into the homogeneous equation:\[ A r^n = r A r^{n-1}. \]This satisfies the equation, confirming that \( T_h(n) = A r^n \) is a solution to the homogeneous part.

Find the Particular Solution

For the non-homogeneous part, the recursion is \[ T(n) = r T(n-1) + r^{2n}. \]Try a particular solution of the form \( T_p(n) = B r^{2n} \) and plug into the equation:\[ B r^{2n} = r (B r^{2(n-1)}) + r^{2n}. \]Simplifying gives:\[ B r^{2n} = B r^{2n} + r^{2n}. \]This implies \( B = 1 \), so the particular solution is: \[ T_p(n) = r^{2n}. \]

Form the General Solution

Combine both the homogeneous and particular solutions:\[ T(n) = T_h(n) + T_p(n) = A r^n + r^{2n}. \]

Use Initial Condition

Use the initial condition \( T(0) = 1 \) to find \( A \):\[ T(0) = A r^0 + r^{2\times0} = A + 1 = 1. \]Solving gives \( A = 0 \).

Write the Final Solution

Substitute \( A = 0 \) back into the general solution:\[ T(n) = 0 \cdot r^n + r^{2n} = r^{2n}. \]Thus, the solution to the recurrence is \[ T(n) = r^{2n}. \]

Key concepts

Homogeneous Solution

When solving recurrence relations, we start with the homogeneous solution. For a relation like \( T(n) = r T(n-1) \), we focus on finding the part of the solution that accounts for this recursive pattern without the addition of any extra terms. In this case, we assume the homogeneous solution is of the form \( T_h(n) = A r^n \).
This assumption stems from trying out solutions that naturally align with the recursive structure.
Plugging \( T_h(n) = A r^n \) back into the homogeneous part verifies its validity, since both sides of the equation align when simplified.

• We substitute \( A r^n \) for \( T(n) \).
• This leads to the equality \( A r^n = r A r^{n-1} \), which holds true.

Thus, we confirm \( T_h(n) = A r^n \) is indeed a solution to the homogeneous part. This step sets the stage for solving the entire recurrence by providing a structured approach to handle the equation's core repetitive behavior.

Particular Solution

A particular solution identifies additional components in the recurrence relation caused by non-homogeneous factors, such as added constants or terms. Here, the non-homogeneous part is the term \( r^{2n} \) in \( T(n) = r T(n-1) + r^{2n} \).
To find the particular solution, we hypothesize a form similar to the non-homogeneous term, such as \( T_p(n) = B r^{2n} \). Checking if this form works involves substituting \( T_p(n) \) into the equation.

• Substitute \( B r^{2n} \) into \( T(n) = r T(n-1) + r^{2n} \).
• After simplification, \( B r^{2n} = B r^{2n} + r^{2n} \) implies \( B = 1 \).

The particular solution is thus \( T_p(n) = r^{2n} \). This solution accounts for the specific external terms added to the recurrence, allowing us to fully model the problem with both homogeneous and particular solutions.

Initial Conditions

Initial conditions play a crucial role in determining the specific instance of a general solution that accurately represents the problem scenario. Once we extract the general solution, composed of both the homogeneous and particular parts \( T(n) = A r^n + r^{2n} \), the initial conditions allow us to solve for constants like \( A \).
Given the initial condition \( T(0) = 1 \), we substitute into the general solution:

• \( T(0) = A \cdot r^0 + r^{2 \cdot 0} \).
• Solving \( A + 1 = 1 \) yields \( A = 0 \).

This constraint results from the specific scenario defined by the initial condition.
Finally, substituting \( A = 0 \) back into the equation simplifies the general solution to \( T(n) = r^{2n} \). Thus, initial conditions effectively personalize the solution to fit the original problem's requirements by fixing the constants involved in the general solution.