12. Solving linear recurrences with constant coefficients#
In the previous note, we saw that many counting problems lead naturally to recurrence relations. For example, the number of tilings of a board with dominoes satisfies with initial conditions and . The recurrence allows us to compute subsequent values step by step: This step-by-step calculation works well for small values of , but it becomes impractical if we need or . Moreover, generating terms one at a time obscures the qualitative behavior of the sequence: how fast does grow as becomes large? Is its growth polynomial, exponential, or something else?
We seek a closed formula: an explicit expression for as a function of that can be evaluated directly without computing intermediate terms. For linear recurrences with constant coefficients, the algebraic structure of the recurrence makes this possible. Substituting a geometric sequence converts the recurrence into an algebraic equation called the characteristic equation. The roots of this equation determine the building blocks of all solutions, and the initial conditions select the unique sequence that solves the original problem.
After studying these notes, you will be able to do the following.
Classify a recurrence by order, linearity, coefficient type, and homogeneity.
Form the characteristic polynomial of a linear homogeneous recurrence with constant coefficients.
Solve homogeneous recurrences whose characteristic roots are real, including repeated roots.
Explain why a root of multiplicity contributes the terms .
Find a particular solution for a driving term , accounting for whether is a characteristic root.
Combine a particular solution with the general homogeneous solution before applying initial conditions.
Express solutions arising from complex roots in terms of a radius, an argument, sines, and cosines.
12.1 Review: classifying recurrence relations#
A recurrence relation expresses the general term in terms of earlier terms of the sequence . We classify recurrences according to four structural features.
The order is the difference between the highest and lowest indices that appear in the equation. For example, the recurrence has order because the index difference is , even though the intermediate terms and do not appear.
The recurrence is linear if it can be written in the form where and . In words, every sequence term appears only to the first power, no sequence terms are multiplied together, and no sequence term appears inside nonlinear functions such as square roots or exponents.
A linear recurrence has constant coefficients if the coefficients are constants that do not depend on . If any coefficient depends on , the recurrence has variable coefficients.
A linear recurrence is homogeneous if the driving term is zero for all , so that every nonzero term involves the sequence. It is nonhomogeneous if for at least one .
The terms homogeneous and nonhomogeneous describe linear recurrences in this note. A nonlinear recurrence requires different techniques and is not assigned either label here.
Example 1 (Classifying before choosing a method)#
Consider the following recurrences.
The recurrence has order . It is linear, has constant coefficients, and is homogeneous. The characteristic-root method applies directly.
The recurrence also has order and constant coefficients, but it is nonhomogeneous. Its driving term is . We find one particular solution to account for this driving term, and then add the solutions of the corresponding homogeneous recurrence.
The recurrence is linear, homogeneous, and of order , but it has variable coefficients because the coefficient changes with the index. The constant-coefficient method in this note does not apply.
The recurrence has order and is nonlinear because two earlier sequence terms are multiplied together. It does not possess a characteristic polynomial.
The recurrence has order , not order : the coefficient of is zero, but the equation still reaches back to . It is linear, has constant coefficients, and is nonhomogeneous with constant driving term .
We consider finite-order linear recurrences with constant coefficients, beginning with the homogeneous case where every term involves the sequence and the driving term is zero.
12.2 Homogeneous recurrences with real characteristic roots#
We consider a linear homogeneous recurrence of order with constant coefficients, written in standard form as
where are real constants and . Moving all terms to the left-hand side gives
A first-order recurrence has geometric sequences as solutions: . Geometric sequences have the property that shifting the index multiplies the term by a constant power: . Let us test whether a geometric sequence can solve the higher-order recurrence (1).
Substituting into the recurrence gives Because we seek a nonzero solution, we require . Factoring out yields Since , the sequence satisfies the recurrence if and only if is a root of the polynomial in parentheses.
Definition 2 (Characteristic polynomial)#
The characteristic polynomial of the recurrence (1) is The equation is the characteristic equation, and its roots are the characteristic roots of the recurrence.
Notice the signs in : each coefficient from the right-hand side of (1) enters with a minus sign, . Moving all sequence terms to one side of the recurrence before writing down the polynomial prevents sign errors.
12.2.1 Distinct real roots and the opening problem#
Suppose the characteristic polynomial has distinct real roots . Then each of the sequences satisfies the recurrence.
Because the recurrence is linear and homogeneous, the principle of superposition applies: any linear combination of solutions is also a solution. If and both satisfy the recurrence, then for any constants and , the sequence satisfies it as well:
Therefore,
is a solution for every choice of constants .
We must also confirm that (2) accounts for all solutions to the recurrence. An order- recurrence determines a unique sequence once initial values are specified. Setting in (2) produces a system of linear equations in the variables :
Because the roots are distinct, this linear system always has a unique solution. (Writing this system as a matrix-vector equation yields a coefficient matrix known as a Vandermonde matrix. Its determinant is the product of all differences for , which is nonzero precisely when the roots are distinct. Finding the initial data this way is indeed solving a matrix-vector equation, but the details of this matrix determinant are beyond the scope of this course.) Since every sequence satisfying the recurrence is uniquely determined by its initial values, the family (2) contains all solutions.
Example 3 (Resolving the opening problem: closed formula for domino tilings)#
Find a closed-form formula for the number of tilings of a board with dominoes, which satisfies with initial conditions and .
Solution: Moving all terms to the left gives . The characteristic equation is By the quadratic formula, the characteristic roots are These roots are real and distinct. The general solution is therefore We use the initial conditions and to determine and :
Multiplying the second equation by gives Substituting yields , so Adding and subtracting the equations and gives Substituting and back into the general solution gives the closed formula
This formula is known as Binet’s formula (shifted by one index because ). Two observations clarify how it behaves:
Although appears in both terms, every value is an integer. For instance, at , which matches .
Because , the second term decays exponentially to zero as increases. For large , is the nearest integer to , showing that the number of tilings grows exponentially at the golden ratio rate .
Example 4 (Three distinct real roots)#
Solve with initial conditions
Solution: Moving all terms to the left gives so the characteristic polynomial is The three roots are distinct. The general solution therefore has one unknown coefficient for each root:
We now fit the three initial values:
Subtracting the first equation from the second eliminates : Subtracting the second equation from the third also eliminates : Subtracting from gives . Then , and finally . Thus As an arithmetic check, the formula predicts , while the recurrence gives
12.2.2 Repeated real roots and the shift operator#
When the characteristic polynomial has repeated roots, a single characteristic root does not provide enough independent solutions. Consider the recurrence Its characteristic polynomial is which has only one root, , with multiplicity . If we used only pure powers of roots, we would write The two constants collapse into a single constant . But an order- recurrence requires two independent initial values and to specify a sequence. For instance, if and , the single constant gives from , which forces . One degree of freedom is missing.
We multiply the geometric sequence by to generate a second linearly independent solution. Substituting into the left-hand side of gives
The sequence is indeed a second linearly independent solution. The general solution for this recurrence is therefore .
The shift operator explains why polynomial factors appear systematically whenever a root is repeated.
Definition 5 (Shift operator)#
For a sequence , the shift operator is defined by Thus is the sequence whose th term is .
Let be a polynomial in . Applying the operator to the sequence gives
The difference is the forward difference of . If has degree , then has degree because the leading terms cancel: If is constant, then .
Consequently, each application of reduces the degree of the polynomial factor multiplying by one. Applying repeatedly gives If is a root of of multiplicity , then for some polynomial . Because polynomials in the shift operator commute, the recurrence operator factors as Therefore, annihilates every sequence of the form with . Choosing yields the linearly independent solutions
Theorem 6 (General homogeneous solution for real roots)#
Let the distinct real roots of the characteristic polynomial be with respective multiplicities , where . Every solution of (1) has the form where the numbers are constants determined by the initial conditions.
In particular, a root of multiplicity contributes
Example 7 (A repeated real root)#
Solve with initial conditions
Solution: Moving all terms to the left gives . The characteristic polynomial factors as The root is simple and contributes . The root has multiplicity and contributes . The general solution is
Substituting the initial conditions produces the linear system:
Subtracting the first equation from the second gives , so . Subtracting the second equation from the third gives . Substituting into this second relation yields Then , and . The unique solution is Checking at , the formula gives . The recurrence confirms:
Example 8 (A triple root and successive differences)#
The recurrence has characteristic polynomial Its general solution is The operator identity shows why is annihilated:
Thus annihilates . It also annihilates after two applications and after one. This explains why a root of multiplicity accommodates polynomials of degree up to , but not a higher power such as .
12.2.3 Summary of the homogeneous solution procedure#
For a homogeneous linear recurrence with constant coefficients and specified initial values, the calculation follows four steps:
Form the characteristic polynomial. Move all sequence terms to one side, replace each term by , and set .
Find all roots and their multiplicities. Factor completely and record the multiplicity of each root.
Write the general solution with unknown coefficients. Each distinct real root of multiplicity contributes a polynomial in of degree multiplied by .
Fit the initial data. Substitute the given initial values into the general solution and solve the resulting system of linear equations for the unknown constants.
Initial conditions must always be applied to the complete general solution in Step 4, never to an incomplete form before all roots and their multiplicities are accounted for.
12.3 Nonhomogeneous polynomial–exponential driving terms#
We now consider recurrences with an external driving term:
where denotes the linear recurrence operator, is a polynomial in , and is a constant. The associated homogeneous recurrence is
Theorem 9 (Particular plus homogeneous)#
If is any particular solution of , then every solution of (3) can be written in the form where is a solution of the associated homogeneous recurrence .
Proof#
Because is a linear operator, substituting gives Thus every sequence of this form is a solution.
Conversely, suppose is an arbitrary solution of . Define the difference sequence . By linearity, Thus is indeed a solution to the homogeneous equation, so .
Theorem 2 establishes the solution procedure for nonhomogeneous recurrences:
Find one particular solution satisfying the nonhomogeneous equation, ignoring the initial conditions.
Write down the general solution of the associated homogeneous recurrence with unknown constants.
Form the complete sum , and only then substitute the initial conditions to determine the constants.
Initial conditions must never be fitted to alone before adding . The initial values belong to the total sequence , so the particular solution shifts the values that the homogeneous part must match.
12.3.1 Choosing the trial form: undetermined coefficients#
To find a particular solution for a driving term , where is a polynomial of degree , we use the method of undetermined coefficients. Let be the multiplicity of as a root of the characteristic polynomial . If is not a root, we set . We select the trial form
The polynomial has the same degree as , with coefficients to be determined by substitution.
Two cases arise based on whether is a characteristic root:
Nonresonance (): If is not a characteristic root, the trial form is simply .
Resonance (): If is a characteristic root of multiplicity , the trial form must be multiplied by .
The factor is required when is a characteristic root because the homogeneous operator annihilates . If we tried an unmodified form , the terms belonging to lower powers of would produce zero rather than the driving term. Multiplying by lifts every term in the trial sequence out of the homogeneous solution space.
Warning (The trial polynomial must include all lower-degree terms)#
If the driving polynomial has degree , the trial polynomial must include every power from down to the constant term , even if some intermediate powers are missing in . For example, if the driving term is , we must try Omitting the linear term prevents matching coefficients because shifting the index from to expands , generating linear terms during substitution.
12.3.2 Case 1: the exponential base is not a characteristic root#
When the base is not a root of , no term of the trial form solves the homogeneous equation. This is the nonresonant case.
Example 10 (A nonresonant polynomial–exponential driving term)#
Solve with initial conditions
Solution: First, solve the homogeneous equation . Its characteristic polynomial is which has roots and . The homogeneous solution is
Next, find a particular solution. The driving term is , so the base is and the polynomial has degree . Because is not a root of , we set and try Substituting into the left-hand side of the recurrence gives We factor out using and :
Setting this equal to and matching coefficients of and the constant term yields Thus , and gives . A particular solution is
The full solution is the sum of the particular and homogeneous solutions: We now use the initial conditions and :
Thus and . Subtracting the first equation from the second gives , and so . The required solution is Checking at , the recurrence gives The formula produces
12.3.3 Case 2: the exponential base is a characteristic root#
When the base is a characteristic root, the unmodified form overlaps with the homogeneous solution family. This is called resonance. Multiplying by , where is the multiplicity of , restores independence.
Example 11 (Resonance at a simple root)#
Solve with initial conditions
Solution: The characteristic polynomial is again , with roots and . The homogeneous solution is .
The driving term is . The base is a characteristic root of multiplicity . The unmodified trial would fail: the term is already a homogeneous solution and would vanish under substitution. We therefore multiply by : Let . Substituting into the recurrence operator gives Now compute each term inside the bracket:
Summing these expressions, the coefficient of vanishes: This cancellation is expected: the term cancels precisely because is a characteristic root. The remaining terms are Equating with yields Thus , and gives , so . A particular solution is
The full solution is We fit the initial conditions and :
Thus and . Subtracting yields , which gives . The solution is Checking at , the recurrence gives The formula produces
Example 12 (Resonance at a double root)#
Solve with initial conditions and .
Solution: The characteristic polynomial is . The root has multiplicity , so the homogeneous solution is
The driving term is , where the polynomial has degree (a constant) and the base has multiplicity . Both and are homogeneous solutions, so we must multiply by : Substituting into the recurrence operator gives
Both the and terms cancel, leaving . Hence , so . The particular solution is
The general solution is Fitting the initial conditions and :
The solution is Checking at , the recurrence gives , and the formula gives . At , the recurrence gives , and the formula gives .
12.4 Complex characteristic roots#
A polynomial with real coefficients need not factor completely into real linear factors. For example, the equation has roots and , where satisfies . When a linear recurrence with real coefficients has nonreal characteristic roots, every sequence value generated from real initial conditions is a real number. We use the polar form of complex numbers to convert powers of complex roots into sines and cosines, yielding a real-valued formula.
12.4.1 Complex numbers, radius, and argument#
A complex number is written in Cartesian form as where . The real number is the real part , is the imaginary part , and is the complex conjugate of .
For , the radius (or modulus) of is its distance from the origin in the complex plane: An argument of is an angle measured counterclockwise from the positive real axis satisfying Euler’s formula states that Therefore, can be written in polar form as
Taking powers in polar form is governed by De Moivre’s formula:
Raising to the th power scales its distance from the origin by and multiplies its angle by .
Example 13 (Computing a complex power in polar form)#
Compute for .
Solution: The radius of is The point lies in the second quadrant of the complex plane, with We choose the argument . The polar form of is By De Moivre’s formula (5),
Polar form allows us to compute without expanding the product term by term.
12.4.2 Conjugate roots produce real sine and cosine terms#
Because the coefficients of the characteristic polynomial are real, any nonreal root must be accompanied by its complex conjugate with the same multiplicity. In polar form, De Moivre’s formula gives expressions for the powers of both roots:
Both and are solutions to the recurrence. Because the recurrence is linear and homogeneous, any linear combination of solutions is again a solution. Adding and subtracting these two equations produces two purely real solutions: Both sequences are real-valued. Forming an arbitrary real linear combination of them gives where and are real constants.
This expression reveals the geometric role of the polar coordinates:
The radius factor controls the amplitude growth or decay: if , the terms grow exponentially; if , they decay to zero; if , the amplitude remains constant.
The trigonometric factors and cause the terms to oscillate in sign and value, with a period determined by the angle .
Theorem 14 (Full real form of the homogeneous solution)#
Let the characteristic polynomial of an order- linear recurrence have real roots with multiplicities , and nonreal conjugate pairs with multiplicities , where Then every real-valued solution of the recurrence has the form
where all coefficients are real constants.
Each real root of multiplicity contributes arbitrary constants. Each conjugate pair of multiplicity contributes arbitrary constants: constants for the cosine terms and constants for the sine terms. The total number of constants equals the degree of the characteristic polynomial, matching the initial conditions needed to specify a unique sequence.
Example 15 (Solving a recurrence with complex roots)#
Solve with initial conditions
Solution: Moving all terms to the left gives . The characteristic equation is By the quadratic formula, We convert to polar form: Because and , we choose .
The two roots form a single simple conjugate pair, so the real general solution is We use the initial conditions and to find and :
Thus and . The solution is
We check the first few terms against the recurrence:
From the recurrence:
From the formula:
The formula matches the recurrence values exactly. The sequence values exhibit oscillatory changes in sign and value driven by the trigonometric factors, enclosed within an exponential envelope growing by a factor of per step.
12.5 A complete solution checklist#
To solve any linear constant-coefficient recurrence with specified initial conditions, follow these steps in order:
Classify the recurrence. Confirm that the recurrence is linear with constant coefficients, and determine its order .
Form the characteristic polynomial. Move all homogeneous sequence terms to one side, replace each term by , and write .
Find all roots and multiplicities. Factor completely. Identify real roots and their multiplicities, and express any nonreal roots as conjugate pairs in polar form .
Write the general homogeneous solution.
Each real root of multiplicity contributes .
Each complex conjugate pair of multiplicity contributes , where and are polynomials of degree .
Find a particular solution if nonhomogeneous. For a driving term with , use the trial form , where and is the multiplicity of as a characteristic root ( if is not a root). Substitute into the recurrence and solve for the unknown coefficients of .
Add the solutions. Form the full solution .
Fit the initial data. Substitute the initial values into and solve the resulting linear system for the unknown constants in .
Verify the solution. Test the resulting formula against the initial values and at least one subsequent term computed directly from the recurrence.