To find the explicit formula, we first solve the homogeneous part of the recurrence relation \( a_n = 2a_{n-1} \), which gives \( a_n = C \cdot 2^n \) for some constant \( C \). Next, we find a particular solution for the non-homogeneous recurrence. Trying a constant solution \( a_n = A \):

["# Finding the Explicit Formula for a Linear Recurrence: From Homogeneous to Full Solution", "When solving linear recurrence relations, one powerful technique is to break the problem into two parts: the homogeneous solution and the particular solution to the non-homogeneous version. This approach ensures clarity and completeness in finding the explicit formula. In this article, we explore how solving the simple recurrence ( a_n = 2a_{n-1} ) leads to the homogeneous solution, then combine it with a particular solution to construct the full answer.", "---", "## Understanding the Recurrence Relation", "Consider the recurrence:", "[\na_n = 2a_{n-1}\n]", "At first glance, this appears simple. But to build confidence in solving more complex recurrences, we start by solving this foundational equation.", "---", "## Step 1: Solving the Homogeneous Part", "The relation ( a_n = 2a_{n-1} ) is a first-order linear homogeneous recurrence. To solve it, we assume a solution of the form ( a_n = C \cdot 2^n ), where ( C ) is a constant determined by initial conditions.", "Substituting into the recurrence:", "[\nC \cdot 2^n = 2 \cdot (C \cdot 2^{n-1}) = C \cdot 2^n\n]", "The equation holds for any constant ( C ), confirming that:", "[\n\boxed{a_n^{(h)} = C \cdot 2^n}\n]", "This is the general solution to the homogeneous recurrence — it captures all possible solutions without external forcing.", "---", "## Step 2: Finding a Particular Solution", "The original recurrence is homogeneous. To solve a recurrence that includes an external nonhomogeneous term (like ( f(n) )), we usually find a particular solution ( a_n^{(p)} ) that satisfies the full equation.", "Suppose we now have a nonhomogeneous version such as:", "[\na_n = 2a_{n-1} + f(n)\n]", "If ( f(n) ) is a constant, polynomial, or exponential function, we often guess a particular solution of a matching form: for example, if ( f(n) = A ), we try ( a_n^{(p)} = A ).", "---", "## Step 3: Trying a Constant Particular Solution", "Let’s test the constant solution ( a_n^{(p)} = A ). Substituting into the nonhomogeneous recurrence:", "[\nA = 2A + f(n)\n]", "But remember, for the recurrence ( a_n = 2a_{n-1} + f(n) ), the full equation becomes:", "[\nA = 2A + f(n)\n]", "Solving for ( A ):", "[\nA - 2A = f(n) \implies -A = f(n) \implies A = -f(n)\n]", "This suggests the particular solution is not constant unless ( f(n) ) is constant in ( n )—but if ( f(n) = c ) (a constant), then ( A = -c ). Thus, trying ( a_n^{(p)} = -c ) would satisfy:", "[\n-c = 2(-c) + c = -2c + c = -c \quad \ ext{✓}\n]", "But wait — this only works if the nonhomogeneous term is constant! If ( f(n) ) varies with ( n ), the guess must reflect that. For instance, if ( f(n) = 3 ), then ( A = -3 ); if ( f(n) = n ), we’d try ( a_n^{(p)} = Bn ), and substitute accordingly.", "Thus, the form of the particular solution matches the structure of ( f(n) ).", "---", "## Summary", "To solve a recurrence like ( a_n = 2a_{n-1} + f(n) ):", "1. First, solve the homogeneous part ( a_n = 2a_{n-1} ), obtaining ( a_n^{(h)} = C \cdot 2^n ).\n2. Guess a particular solution ( a_n^{(p)} ) based on ( f(n) ):\n - Constant ( f(n) = c \Rightarrow a_n^{(p)} = -c )\n - Polynomial or exponential ( f(n) \Rightarrow same form or adjusted form\n3. Combine solutions: general solution is ( a_n = a_n^{(h)} + a_n^{(p)} ).", "---", "## Real-World Application Example", "Suppose the recurrence models a doubling process disrupted by a constant daily input, like:", "[\na_n = 2a_{n-1} + 7 \quad \ ext{with } a_0 = 1\n]", "- Homogeneous solution: ( a_n^{(h)} = C \cdot 2^n )\n- Try ( a_n^{(p)} = A ). Substituting:\n [\n A = 2A + 7 \implies A = -7\n ]\n- General solution: ( a_n = C \cdot 2^n - 7 )\n- Apply initial condition: ( a_0 = C - 7 = 1 \implies C = 8 )\n- Final explicit formula: ( a_n = 8 \cdot 2^n - 7 )", "This method enables prediction and analysis in algorithmic complexity, population growth models, and financial calculations.", "---", "## Conclusion", "Understanding recurrence relations begins with isolating the homogeneous behavior. By solving ( a_n = 2a_{n-1} ), we unlock the constant solution pattern that builds the homogeneous component. Matching this structure to the nonhomogeneous term allows us to find the particular solution — completing the story of ( a_n ) in closed form. Mastering this dual approach empowers problem-solving across discrete mathematics and computer science.", "---", "Keywords: recurrence relation, homogeneous solution, particular solution, linear recurrence, explicit formula, mathematical induction, solving recurrences, doubling recurrence, explicit general solution.\nMeta Description: Learn how to find the explicit formula of a recurrence relation by solving the homogeneous part and combining it with a particular solution through substitution and pattern matching.\nRelated Topics:** recurrence relation solution, first-order recurrence, nonhomogeneous recurrences, algorithm analysis, probability theory."]