T(1) = 4, \quad T(n) = 2T(n-1) + 3 \text{ for } n \geq 2.

["# Solving the Recurrence: T(n) = 2T(n−1) + 3 with T(1) = 4", "Understanding recurrence relations is fundamental in computer science and mathematics, especially when analyzing the efficiency of recursive algorithms. One such recurrence that arises frequently is:", "[\nT(1) = 4, \quad T(n) = 2T(n-1) + 3 \quad \ ext{for } n \geq 2\n]", "This equation defines a sequence where each term depends exponentially on the previous one, plus a constant addition. In this article, we’ll solve the recurrence step-by-step, analyze its closed-form expression, and explore its implications for algorithm complexity.", "---", "## Understanding the Recurrence Relation", "The recurrence\n[\nT(n) = 2T(n-1) + 3\n]\nis a linear nonhomogeneous recurrence relation with constant coefficients. It describes a scenario where the problem at step ( n ) scales the previous solution by a factor of 2 and adds a constant term (3).", "Initial condition:\n[\nT(1) = 4\n]", "This recurrence models exponential growth tempered by a constant input — common in divide-and-conquer algorithms with two recursive branches, such as recursive implementations of binary trees or dynamic programming with doubling subproblems.", "---", "## Step-by-Step Solution: Finding the Closed Form", "We solve the recurrence using a combination of pattern recognition and iteration.", "### 1. Write out the first few terms", "Start with the base case:\n[\nT(1) = 4\n]", "Now compute subsequent values using the recurrence:\n[\n\begin{align}\nT(2) &= 2T(1) + 3 = 2(4) + 3 = 8 + 3 = 11 \\nT(3) &= 2T(2) + 3 = 2(11) + 3 = 22 + 3 = 25 \\nT(4) &= 2T(3) + 3 = 2(25) + 3 = 50 + 3 = 53 \\nT(5) &= 2T(4) + 3 = 2(53) + 3 = 106 + 3 = 109 \\n\end{align}\n]", "Sequence so far:\n[\nT(1)=4,\ T(2)=11,\ T(3)=25,\ T(4)=53,\ T(5)=109\n]", "### 2. Look for a pattern or solve algebraically", "Since this is a linear nonhomogeneous recurrence, we use the standard method:", "Let’s write the homogeneous part:\n[\nT_h(n) = 2T_h(n-1)\n]\nSolution: ( T_h(n) = A \cdot 2^n )", "Now find a particular solution ( T_p(n) ) for the nonhomogeneous term (( +3 )). Since the nonhomogeneous term is constant and the homogeneous solution includes ( 2^n ), we try a constant particular solution:\nLet ( T_p(n) = C )", "Substitute into recurrence:\n[\nC = 2C + 3 \quad \Rightarrow \quad C - 2C = 3 \quad \Rightarrow \quad -C = 3 \quad \Rightarrow \quad C = -3\n]", "So the general solution is:\n[\nT(n) = T_h(n) + T_p(n) = A \cdot 2^n - 3\n]", "### 3. Use initial condition to find ( A )", "Apply ( T(1) = 4 ):\n[\n4 = A \cdot 2^1 - 3 \quad \Rightarrow \quad 4 = 2A - 3 \quad \Rightarrow \quad 2A = 7 \quad \Rightarrow \quad A = \frac{7}{2}\n]", "Thus, the closed-form solution is:\n[\nT(n) = \frac{7}{2} \cdot 2^n - 3 = 7 \cdot 2^{n-1} - 3\n]", "---", "## Verification", "Check against earlier values:\n- ( n = 1 ): ( 7 \cdot 2^{0} - 3 = 7 - 3 = 4 ) ✓\n- ( n = 2 ): ( 7 \cdot 2^{1} - 3 = 14 - 3 = 11 ) ✓\n- ( n = 3 ): ( 7 \cdot 2^{2} - 3 = 28 - 3 = 25 ) ✓\n- ( n = 4 ): ( 7 \cdot 8 - 3 = 56 - 3 = 53 ) ✓", "Pattern confirmed.", "---", "## Asymptotic Complexity and Interpretation", "Since ( T(n) = 7 \cdot 2^{n-1} - 3 ), the dominant term is ( 7 \cdot 2^{n-1} ), which grows exponentially. Therefore:", "[\nT(n) = \Theta(2^n)\n]", "This means the time complexity of any algorithm tied to this recurrence is exponential in ( n ), indicating rapid growth even for moderate ( n ).", "Such behavior mirrors algorithms like recursive binary splitting (e.g., some divide-and-conquer procedures with memory duplication), where each step doubles work plus a constant overhead.", "---", "## Summary", "The recurrence ( T(1) = 4 ), ( T(n) = 2T(n-1) + 3 ) for ( n \geq 2 ) has the closed-form solution:", "[\n\boxed{T(n) = 7 \cdot 2^{n-1} - 3}\n]", "This exponential solution helps analyze algorithm performance and supports decisions in optimization, resource allocation, and computational complexity.", "---", "## Further Reading", "- Understanding recursive relations via generating functions\n- Mastering divide-and-conquer recurrences (Master Theorem)\n- Analyzing recursive algorithms with dynamic programming models", "---", "Keywords: recurrence relation, T(n) = 2T(n−1) + 3, closed-form solution, exponential growth, algorithm analysis, divide-and-conquer, recursive computation."]