Repeated Roots in the Characteristic Equation
You'll learn how to modify the general solution of a recurrence relation when its characteristic equation yields repeated roots.
The Core Problem
When solving linear homogeneous recurrence relations like ( a_n = c_1 a_{n-1} + c_2 a_{n-2} ), we typically find the characteristic equation's roots and write the solution as ( a_n = A r_1^n + B r_2^n ) for distinct roots ( r_1 ) and ( r_2 ).
But what happens when the characteristic equation has a repeated root—when ( r_1 = r_2 = r )?
If we naively wrote ( a_n = A r^n + B r^n ), we'd just get ( a_n = (A+B) r^n ), which has only one independent constant instead of the two we need to satisfy any pair of initial conditions. We've lost a degree of freedom!
The Solution Form
When the characteristic equation has a repeated root ( r ), the general solution becomes:
[ a_n = (A + Bn) r^n ]
Notice the extra factor of ( n ) multiplying the second term. This provides the second independent solution we need.
Analogy: Think of it like having duplicate keys—you need to "mark" the second one differently (multiply by ( n )) so they can open different locks (satisfy different initial conditions).
Example
For ( a_n = 4a_{n-1} - 4a_{n-2} ), the characteristic equation is ( r^2 - 4r + 4 = 0 ), which factors as ( (r-2)^2 = 0 ). The repeated root is ( r = 2 ).
General solution: ( a_n = (A + Bn) \cdot 2^n )
With initial conditions ( a_0 = 3 ) and ( a_1 = 10 ), you'd solve for ( A ) and ( B ).
Key Takeaway: When a characteristic equation has a repeated root ( r ), multiply the second solution term by ( n ) to obtain the general form ( a_n = (A + Bn)r^n ).