The Central Idea
Consider a constant-coefficient homogeneous linear recurrence such as
\[ a_n=5a_{n-1}-6a_{n-2}. \]We look for a solution that behaves geometrically:
\[ \boxed{a_n=r^n}. \]Substituting this trial form converts the recurrence into an algebraic equation for \(r\).
That equation is called the characteristic equation.
Why Try an Exponential Form?
Geometric sequences behave especially well under index shifts.
If
\[ a_n=r^n, \]then
\[ a_{n-1}=r^{n-1} \]and
\[ a_{n-2}=r^{n-2}. \]All shifted terms remain powers of the same base \(r\), allowing a common factor to be removed.
Build the Characteristic Equation
Start with
\[ a_n=5a_{n-1}-6a_{n-2}. \]Substitute
\[ a_n=r^n. \]Then
\[ r^n=5r^{n-1}-6r^{n-2}. \]Factor out
\[ r^{n-2}. \]This gives
\[ r^{n-2}(r^2-5r+6)=0. \]The characteristic equation is therefore
\[ \boxed{r^2-5r+6=0}. \]Characteristic Polynomial
The expression
\[ \boxed{r^2-5r+6} \]is called the characteristic polynomial.
Solving the characteristic equation means finding the roots of this polynomial.
Distinct Characteristic Roots
Factor
\[ r^2-5r+6. \]We obtain
\[ (r-2)(r-3)=0. \]Therefore, the characteristic roots are
\[ \boxed{r=2\quad\text{and}\quad r=3}. \]Each Root Produces a Geometric Solution
Since \(r=2\) is a characteristic root,
\[ 2^n \]satisfies the recurrence.
Since \(r=3\) is also a root,
\[ 3^n \]also satisfies the recurrence.
Because the recurrence is homogeneous and linear, linear combinations of these solutions are also solutions.
General Form for Two Distinct Roots
If a second-order homogeneous linear recurrence has two distinct characteristic roots
\[ r_1 \quad\text{and}\quad r_2, \]then the general solution has the form
\[ \boxed{ a_n=C_1r_1^n+C_2r_2^n }. \]The constants \(C_1\) and \(C_2\) are determined by the initial conditions.
Example: Construct the General Solution
For
\[ a_n=5a_{n-1}-6a_{n-2}, \]the characteristic roots are \(2\) and \(3\).
Therefore,
\[ \boxed{ a_n=C_1 2^n+C_2 3^n }. \]Use Initial Conditions to Find the Constants
Suppose additionally that
\[ a_0=2, \qquad a_1=7. \]Substitute \(n=0\):
\[ C_1+C_2=2. \]Substitute \(n=1\):
\[ 2C_1+3C_2=7. \]Solve the system.
Solve for the Constants
From
\[ C_1+C_2=2, \]we have
\[ C_1=2-C_2. \]Substitute into
\[ 2C_1+3C_2=7: \] \[ 2(2-C_2)+3C_2=7. \]Therefore,
\[ C_2=3 \]and
\[ C_1=-1. \]Thus,
\[ \boxed{ a_n=-2^n+3\cdot3^n }. \]Verify the Initial Conditions
At \(n=0\),
\[ a_0=-1+3=2. \]At \(n=1\),
\[ a_1=-2+9=7. \]The closed form matches both initial values.
Verify the Recurrence
Since both
\[ 2^n \]and
\[ 3^n \]individually satisfy the recurrence, any linear combination
\[ C_1 2^n+C_2 3^n \]also satisfies it.
This is the superposition principle in action.
Standard Recurrence Form
A second-order recurrence may be written as
\[ a_n=c_1a_{n-1}+c_2a_{n-2}. \]Moving all terms to one side gives
\[ a_n-c_1a_{n-1}-c_2a_{n-2}=0. \]The characteristic equation is
\[ \boxed{ r^2-c_1r-c_2=0 }. \]Example: Signs Matter
Consider
\[ a_n=4a_{n-1}+5a_{n-2}. \]Moving all terms left gives
\[ a_n-4a_{n-1}-5a_{n-2}=0. \]Therefore, the characteristic equation is
\[ \boxed{r^2-4r-5=0}. \]The sign of the \(5\) changes when the recurrence is moved to standard form.
Factor the Example
We have
\[ r^2-4r-5=(r-5)(r+1). \]Therefore, the roots are
\[ \boxed{5\quad\text{and}\quad-1}. \]The general solution is
\[ \boxed{ a_n=C_1 5^n+C_2(-1)^n }. \]Negative Characteristic Roots
A negative root produces alternating signs.
For example,
\[ (-2)^n \]alternates sign while its magnitude grows like \(2^n\).
Therefore, characteristic roots reveal qualitative sequence behavior as well as algebraic formulas.
Roots with Magnitude Less Than One
If
\[ |r|<1, \]then
\[ r^n\to0. \]A characteristic term associated with such a root decays in magnitude as \(n\) grows.
Roots with Magnitude Greater Than One
If
\[ |r|>1, \]then the magnitude of
\[ r^n \]grows exponentially.
In a linear combination, the root with the largest magnitude often controls long-run growth unless its coefficient is zero.
Dominant Root Idea
Suppose
\[ a_n=C_1 2^n+C_2 5^n \]with \(C_2\neq0\).
Since
\[ 5^n \]grows much faster than
\[ 2^n, \]the \(5^n\) term eventually dominates the size of the sequence.
This gives a first glimpse of asymptotic reasoning from characteristic roots.
Repeated Characteristic Roots
Distinct roots are not the only possibility.
Consider
\[ a_n=6a_{n-1}-9a_{n-2}. \]The characteristic equation is
\[ r^2-6r+9=0. \]Factoring,
\[ (r-3)^2=0. \]The root
\[ \boxed{r=3} \]is repeated.
Why One Exponential Is Not Enough
A second-order recurrence normally needs two independent constants in its general solution.
If the only characteristic root is \(3\), the expression
\[ C3^n \]has only one free constant.
A second independent solution is needed.
Repeated-Root Solution Form
For a repeated root \(r\) of multiplicity \(2\), the general solution is
\[ \boxed{ a_n=(C_1+C_2n)r^n }. \]Equivalently,
\[ a_n=C_1r^n+C_2nr^n. \]The extra factor \(n\) supplies the second independent solution.
Example: Repeated Root
For
\[ a_n=6a_{n-1}-9a_{n-2}, \]the repeated root is \(3\).
Therefore,
\[ \boxed{ a_n=(C_1+C_2n)3^n }. \]Fit Initial Conditions in the Repeated-Root Case
Suppose
\[ a_0=2, \qquad a_1=9. \]From \(n=0\),
\[ C_1=2. \]From \(n=1\),
\[ (2+C_2)3=9. \]Therefore,
\[ C_2=1. \]Thus,
\[ \boxed{ a_n=(2+n)3^n }. \]Higher-Order Characteristic Equations
The same idea extends to higher-order constant-coefficient homogeneous recurrences.
For example,
\[ a_n=2a_{n-1}+a_{n-2}-2a_{n-3} \]leads to
\[ \boxed{ r^3-2r^2-r+2=0 }. \]Factoring this polynomial gives the characteristic roots.
Order and Number of Constants
A \(k\)th-order recurrence normally requires \(k\) initial conditions.
Correspondingly, its general homogeneous solution normally contains \(k\) independent constants after root multiplicities are handled correctly.
The number of free constants matches the amount of initial data.
Multiplicity Beyond Two
If a characteristic root \(r\) has multiplicity \(m\), then the associated solution family contains
\[ r^n,\ nr^n,\ n^2r^n,\ldots,n^{m-1}r^n. \]Thus, a root of multiplicity \(m\) contributes \(m\) independent terms.
This general pattern is useful to recognize even when the lesson focuses mainly on second-order examples.
Example: First-Order Characteristic Method
Consider
\[ a_n=4a_{n-1}. \]Try
\[ a_n=r^n. \]Then
\[ r^n=4r^{n-1}. \]The characteristic equation is
\[ r-4=0. \]Therefore,
\[ \boxed{a_n=C4^n}. \]This recovers the familiar geometric-sequence formula.
Geometric Recurrences Are the Simplest Characteristic Case
A geometric recurrence
\[ a_n=ra_{n-1} \]already has its multiplier as the characteristic root.
The characteristic method therefore generalizes the same exponential idea to higher-order recurrences.
Fibonacci Characteristic Equation
The Fibonacci recurrence is
\[ F_n=F_{n-1}+F_{n-2}. \]Substitute
\[ F_n=r^n. \]Then
\[ r^n=r^{n-1}+r^{n-2}. \]Therefore, the characteristic equation is
\[ \boxed{r^2-r-1=0}. \]Fibonacci Characteristic Roots
Solve
\[ r^2-r-1=0. \]By the quadratic formula,
\[ r= \frac{1\pm\sqrt5}{2}. \]Therefore, the two roots are
\[ \boxed{ \phi=\frac{1+\sqrt5}{2} } \]and
\[ \boxed{ \psi=\frac{1-\sqrt5}{2} }. \]Fibonacci General Solution
Since the roots are distinct,
\[ F_n=C_1\phi^n+C_2\psi^n. \]Using
\[ F_0=0, \qquad F_1=1, \]determines the constants.
The result is the famous closed form
\[ \boxed{ F_n= \frac{\phi^n-\psi^n}{\sqrt5} }. \]Why the Fibonacci Closed Form Is Surprising
The Fibonacci numbers are integers, yet the formula contains irrational numbers involving \(\sqrt5\).
The irrational parts cancel in exactly the right way because the formula was constructed from the recurrence and its initial conditions.
This is a striking example of algebraic structure hidden inside a recursive integer sequence.
Characteristic Roots and Consecutive Ratios
For Fibonacci numbers, the root
\[ \phi=\frac{1+\sqrt5}{2} \]has larger magnitude than
\[ \psi=\frac{1-\sqrt5}{2}. \]The \(\psi^n\) term decays in magnitude, so the \(\phi^n\) term dominates for large \(n\).
This explains why
\[ \frac{F_{n+1}}{F_n} \]approaches \(\phi\).
The Method Applies to Homogeneous Recurrences
The direct characteristic-root method introduced here applies most cleanly to constant-coefficient homogeneous linear recurrences.
For example,
\[ a_n=4a_{n-1}-3a_{n-2} \]fits directly.
But
\[ a_n=4a_{n-1}-3a_{n-2}+7 \]is nonhomogeneous and needs an additional idea.
Nonhomogeneous Recurrences Need More Structure
In a nonhomogeneous recurrence,
\[ a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+g(n), \]the characteristic equation describes the associated homogeneous part.
A full solution also requires a particular solution related to the forcing term \(g(n)\).
That systematic theory is beyond this introductory lesson.
Associated Homogeneous Recurrence
Consider
\[ a_n=3a_{n-1}+2. \]The associated homogeneous recurrence is
\[ a_n=3a_{n-1}. \]Its characteristic root is
\[ r=3. \]This root describes the homogeneous part of the behavior.
Characteristic Methods and Generating Functions
Characteristic methods and generating functions often lead to the same exponential building blocks from different directions.
The characteristic method begins with the recurrence and tests
\[ r^n. \]Generating functions encode the full sequence into a power series and solve an algebraic equation for that series.
Both methods expose the algebra behind constant-coefficient recurrences.
Characteristic Polynomial and Generating-Function Denominator
Consider
\[ a_n=3a_{n-1}-2a_{n-2}. \]Its characteristic polynomial is
\[ r^2-3r+2. \]A corresponding rational generating function typically has denominator
\[ 1-3x+2x^2. \]These expressions encode the same recurrence coefficients in reversed power order.
Characteristic Methods and Closed Forms
Characteristic methods are primarily a route from recursive form to closed form.
The workflow is
\[ \boxed{ \text{recurrence} \longrightarrow \text{characteristic equation} \longrightarrow \text{roots} \longrightarrow \text{general solution} \longrightarrow \text{initial conditions} }. \]Verification after Solving
Even after finding characteristic roots and fitting constants, verify the result.
Check:
- the initial conditions;
- the recurrence relation.
This catches sign errors, indexing mistakes, and incorrectly solved constants.
Example: Full Distinct-Root Workflow
Solve
\[ a_n=4a_{n-1}-3a_{n-2} \]with
\[ a_0=2, \qquad a_1=4. \]Characteristic equation:
\[ r^2-4r+3=0. \]Factor:
\[ (r-1)(r-3)=0. \]Roots:
\[ r_1=1, \qquad r_2=3. \]Continue the Example
General form:
\[ a_n=C_1+C_2 3^n. \]Use
\[ a_0=2: \] \[ C_1+C_2=2. \]Use
\[ a_1=4: \] \[ C_1+3C_2=4. \]Subtracting gives
\[ 2C_2=2, \]so
\[ C_2=1, \qquad C_1=1. \]Therefore,
\[ \boxed{ a_n=1+3^n }. \]Check the Example Quickly
The first few terms from the formula are
\[ 2,\ 4,\ 10,\ 28,\ldots. \]Check the recurrence:
\[ 4(4)-3(2)=10, \] \[ 4(10)-3(4)=28. \]The closed form and recurrence agree.
Common Error: Building the Wrong Polynomial
From
\[ a_n=5a_{n-1}-6a_{n-2}, \]the characteristic equation is
\[ r^2-5r+6=0, \]not
\[ r^2+5r-6=0. \]Writing the recurrence in standard form before building the polynomial helps prevent sign errors.
Common Error: Forgetting the Trial Form
The characteristic equation does not appear by replacing subscripts with arbitrary powers.
It comes from the explicit trial
\[ a_n=r^n \]and substitution into the recurrence.
Understanding this step makes the method easier to reconstruct and verify.
Common Error: Using One Constant for Two Distinct Roots
If a second-order recurrence has roots \(r_1\neq r_2\), the general form is
\[ C_1r_1^n+C_2r_2^n. \]Two independent constants are needed because two initial conditions must be matched.
Common Error: Ignoring Root Multiplicity
If the characteristic polynomial is
\[ (r-2)^2, \]the general form is not merely
\[ C_1 2^n+C_2 2^n. \]Those terms are not independent.
Use
\[ \boxed{ (C_1+C_2n)2^n }. \]Common Error: Applying the Method Directly to a Nonlinear Recurrence
A recurrence such as
\[ a_n=(a_{n-1})^2+a_{n-2} \]is nonlinear.
The introductory characteristic method does not apply directly.
Common Error: Applying the Method Directly to Variable Coefficients
The recurrence
\[ a_n=na_{n-1}+a_{n-2} \]is linear but has a coefficient depending on \(n\).
The constant-coefficient characteristic method developed here does not apply in the same straightforward way.
Common Error: Forgetting Initial Conditions
Characteristic roots determine a family of solutions.
Initial conditions select the particular sequence.
Stopping after finding
\[ a_n=C_1r_1^n+C_2r_2^n \]leaves the problem incomplete when initial data is provided.
Common Error: Mixing Indexing Conventions
If the solution is written using
\[ r^n, \]substitute the actual initial indices carefully.
Initial data at
\[ a_0,a_1 \]produces a different algebraic system than data at
\[ a_1,a_2. \]A Reliable Procedure for Distinct Roots
- Write the recurrence in standard homogeneous form.
- Try \(a_n=r^n\).
- Build the characteristic polynomial.
- Solve the characteristic equation.
- For distinct roots \(r_1,\ldots,r_k\), form a linear combination of \(r_i^n\).
- Use the initial conditions to solve for the constants.
- Verify the final formula.
A Reliable Procedure for a Repeated Root
- Find the characteristic polynomial.
- Factor it and identify root multiplicities.
- For a double root \(r\), use \(r^n\) and \(nr^n\).
- For higher multiplicity, continue with \(n^2r^n,\ldots\).
- Fit all constants using the initial conditions.
- Verify the result.
A Reliable Classification Check
Before applying characteristic methods, ask:
- Is the recurrence linear?
- Are the coefficients constant?
- Is the recurrence homogeneous?
- Is enough initial data supplied?
If the first three answers are yes, the introductory characteristic method is a natural tool.
Practice 1: Build the Characteristic Equation
Find the characteristic equation for
\[ a_n=7a_{n-1}-12a_{n-2}. \]Practice 2: Find Distinct Roots
Solve
\[ r^2-7r+12=0. \]Practice 3: Write the General Solution
If the characteristic roots are
\[ 3 \quad\text{and}\quad 4, \]write the general solution.
Practice 4: Fit Initial Conditions
Suppose
\[ a_n=C_1 2^n+C_2 3^n, \]with
\[ a_0=5, \qquad a_1=13. \]Find \(C_1\) and \(C_2\).
Practice 5: Repeated Root
Find the characteristic root structure of
\[ a_n=8a_{n-1}-16a_{n-2}. \]Write the general solution form.
Practice 6: Negative Root
Find the characteristic roots of
\[ a_n=2a_{n-1}+3a_{n-2}. \]Write the general solution.
Practice 7: Fibonacci Characteristic Equation
Derive the characteristic equation for
\[ F_n=F_{n-1}+F_{n-2}. \]Practice 8: Applicability Check
Does the introductory characteristic method apply directly to
\[ a_n=na_{n-1}+a_{n-2}? \]Explain.
Practice 9: Full Solution
Solve
\[ a_n=3a_{n-1}-2a_{n-2} \]with
\[ a_0=2, \qquad a_1=3. \]Practice 10: Dominant Root
Suppose
\[ a_n=4\cdot2^n-3\cdot5^n. \]Which characteristic term controls the long-run magnitude?
Practice Answers
Practice 1
Move all terms to one side:
\[ a_n-7a_{n-1}+12a_{n-2}=0. \]Therefore,
\[ \boxed{r^2-7r+12=0}. \]Practice 2
\[ r^2-7r+12 = (r-3)(r-4). \]Therefore,
\[ \boxed{r=3,\quad r=4}. \]Practice 3
\[ \boxed{ a_n=C_1 3^n+C_2 4^n }. \]Practice 4
At \(n=0\),
\[ C_1+C_2=5. \]At \(n=1\),
\[ 2C_1+3C_2=13. \]From the first equation,
\[ C_1=5-C_2. \]Substitute:
\[ 2(5-C_2)+3C_2=13. \]Thus,
\[ C_2=3, \]and
\[ C_1=2. \]Therefore,
\[ \boxed{C_1=2,\quad C_2=3}. \]Practice 5
Characteristic equation:
\[ r^2-8r+16=0. \]Factor:
\[ (r-4)^2=0. \]The repeated root is
\[ r=4. \]Therefore,
\[ \boxed{ a_n=(C_1+C_2n)4^n }. \]Practice 6
Characteristic equation:
\[ r^2-2r-3=0. \]Factor:
\[ (r-3)(r+1)=0. \]Therefore, the roots are
\[ 3 \quad\text{and}\quad -1. \]The general solution is
\[ \boxed{ a_n=C_1 3^n+C_2(-1)^n }. \]Practice 7
Substitute
\[ F_n=r^n: \] \[ r^n=r^{n-1}+r^{n-2}. \]Divide by \(r^{n-2}\):
\[ \boxed{r^2-r-1=0}. \]Practice 8
No, not in the straightforward constant-coefficient form developed here.
The recurrence
\[ a_n=na_{n-1}+a_{n-2} \]has a coefficient \(n\) that varies with the index.
Therefore, the introductory constant-coefficient characteristic method does not apply directly.
Practice 9
Characteristic equation:
\[ r^2-3r+2=0. \]Factor:
\[ (r-1)(r-2)=0. \]General solution:
\[ a_n=C_1+C_2 2^n. \]Use \(a_0=2\):
\[ C_1+C_2=2. \]Use \(a_1=3\):
\[ C_1+2C_2=3. \]Therefore,
\[ C_2=1, \qquad C_1=1. \]Hence,
\[ \boxed{ a_n=1+2^n }. \]Practice 10
The magnitudes compare
\[ 2^n \]and
\[ 5^n. \]Since \(5^n\) grows faster,
\[ \boxed{-3\cdot5^n} \]controls the long-run magnitude.
What to Remember
The characteristic method solves many constant-coefficient homogeneous linear recurrences by testing exponential solutions.
\[ \boxed{a_n=r^n}. \]- Substitution produces a characteristic polynomial.
- Each distinct characteristic root \(r\) contributes a term proportional to \(r^n\).
- Distinct roots lead to linear combinations of exponential terms.
- A repeated root requires extra factors of \(n\).
- Initial conditions determine the free constants.
- The number of independent constants matches the recurrence order.
- Characteristic roots reveal growth, decay, and alternating behavior.
- The root with largest magnitude often controls long-run growth.
- The method applies most directly to constant-coefficient homogeneous linear recurrences.
- Nonhomogeneous and variable-coefficient recurrences require additional ideas.
- Verification should check both the recurrence and the initial conditions.
Where We Go Next
Characteristic methods convert certain recurrences into algebraic equations whose roots produce closed-form building blocks. Another powerful approach packages the entire sequence into a power series and then manipulates that series algebraically.
The next lesson, Generating Functions, introduces this sequence-encoding method and shows how coefficient extraction, shifts, products, and rational functions can reveal recurrence and counting structure.