Recurrence Relations — Homogeneous and Particular Solutions

⚡ Key Takeaways

A linear recurrence relation with constant coefficients is solved by combining the homogeneous solution (general solution of the equation with zero forcing term) and a particular solution (any single solution of the full equation). The general solution is $a_n = a_n^{(h)} + a_n^{(p)}$ . Applies to sequences defined recursively — algorithm analysis, combinatorics, difference equations, discrete dynamical systems. The method mirrors that for linear ODEs and dates to Euler, de Moivre, and Lagrange (18th century).

💡 The Core Insight

The solution operator is linear. If $L[a_n] = a_n + c_1 a_{n-1} + \cdots + c_k a_{n-k}$ , then $L$ is a linear map on sequences. Solving $L[a_n] = f(n)$ is therefore exactly like solving a linear system $Lx = b$ : the solution set is a coset of the kernel. The kernel is the homogeneous solution space ( $L[a_n]=0$ ), and any single solution of $L[a_n]=f(n)$ shifts the whole kernel into place. Everything else — characteristic equations, repeated-root corrections, the method of undetermined coefficients — is machinery for computing these two pieces.

DefinitionLinear Recurrence with Constant Coefficients

A $k$ -th order linear recurrence relation with constant coefficients is

1

\quad a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = f(n),\qquad n \ge k,

where:

$a_n$ is the unknown sequence (the solution);
$c_1, \dots, c_k$ are real (or complex) constants with $c_k \ne 0$ (so the order is genuinely $k$ );
$f(n)$ is a given forcing function (or nonhomogeneous term);
$k$ initial conditions $a_0, a_1, \dots, a_{k-1}$ pin down a unique solution.

If $f(n) \equiv 0$ , the recurrence is homogeneous; otherwise it is nonhomogeneous (or inhomogeneous). Derivation hint: This is the most general form invariant under the shift operator with fixed coefficients; the condition $c_k\ne 0$ guarantees that knowing $a_{n-1},\dots,a_{n-k}$ determines $a_n$ and that the past is recoverable.

DefinitionCharacteristic Equation

Substituting the trial solution $a_n = r^n$ into the homogeneous version of [1] and dividing by $r^{n-k}$ gives the characteristic equation

2

\quad r^k + c_1 r^{k-1} + c_2 r^{k-2} + \cdots + c_{k-1} r + c_k = 0.

Its roots $r_1, \dots, r_k$ (with multiplicity) generate the homogeneous solution space. Derivation hint: With $a_n=r^n$ , each term $a_{n-j}=r^{n-j}$ ; factor out the lowest power $r^{n-k}$ from $r^n+c_1 r^{n-1}+\cdots+c_k r^{n-k}=0$ .

TheoremStructure of the General Solution

Let $a_n^{(p)}$ be any particular solution of the nonhomogeneous recurrence [1], and let $a_n^{(h)}$ denote the general solution of the associated homogeneous recurrence $L[a_n]=0$ . Then every solution of [1] is

3

\quad a_n = a_n^{(h)} + a_n^{(p)},

and conversely every sequence of this form solves [1]. The free constants in $a_n^{(h)}$ are fixed uniquely by the $k$ initial conditions. Derivation hint: If $a_n$ and $\tilde a_n$ both solve $L[\cdot]=f$ , linearity gives $L[a_n-\tilde a_n]=f-f=0$ , so their difference is homogeneous.

TheoremHomogeneous Solution from Roots

Let $r_1,\dots,r_m$ be the distinct roots of [2] with multiplicities $\mu_1,\dots,\mu_m$ ( $\sum \mu_i = k$ ). Then the general homogeneous solution is

4

\quad a_n^{(h)} = \sum_{i=1}^{m}\Big( A_{i,0} + A_{i,1}\,n + \cdots + A_{i,\mu_i-1}\,n^{\,\mu_i-1}\Big) r_i^{\,n},

with $k$ arbitrary constants $A_{i,j}$ . For a simple root this reduces to $A_i r_i^n$ . Derivation hint: Distinct-root solutions $r_i^n$ are linearly independent (Vandermonde). For a root of multiplicity $\mu$ , the functions $n^j r^n$ ( $0\le j<\mu$ ) all lie in the kernel; verify by substituting $a_n=n r^n$ for a double root.

ProofGeneral Solution Structure

We prove [3] in numbered steps. 1. $L$ is linear. Define $L[a]_n = a_n + c_1 a_{n-1} + \cdots + c_k a_{n-k}$ . For scalars $\alpha,\beta$ and sequences $a,b$ :

5

\quad L[\alpha a + \beta b]_n = \alpha\,L[a]_n + \beta\,L[b]_n.

Derivation hint: Each term $(\alpha a + \beta b)_{n-j} = \alpha a_{n-j}+\beta b_{n-j}$ ; sum termwise. 2. Difference of two solutions is homogeneous. Suppose $L[a]=f$ and $L[\tilde a]=f$ . By step 1, $L[a-\tilde a] = f - f = 0$ , so $h := a-\tilde a$ solves the homogeneous equation. 3. Therefore $a = \tilde a + h = a^{(p)} + a^{(h)}$ . Every solution differs from a fixed particular solution by a homogeneous solution. 4. Conversely, if $h$ is homogeneous and $a^{(p)}$ particular, then $L[a^{(p)}+h] = L[a^{(p)}] + L[h] = f + 0 = f$ , so the sum is a solution. 5. Dimension count. The map "solution $\mapsto (a_0,\dots,a_{k-1})$ " is a bijection between the homogeneous solution space and $\mathbb{R}^k$ (or $\mathbb{C}^k$ ), because initial data determine and are determined freely. Hence the kernel has dimension $k$ , matching the $k$ constants in [4]. $\blacksquare$

∎

ProofRepeated-Root Solutions

Suppose $r$ is a double root of [2], so the characteristic polynomial $P(r)$ satisfies $P(r)=P'(r)=0$ . Consider the operator-level identity: applying $L$ to $r^n$ produces $P(r) r^{n-k}$ . Differentiating $r^n$ with respect to $r$ before applying $L$ commutes appropriately, giving

6

\quad L\big[n\,r^{n-1}\big]_{} \;=\; \frac{d}{dr}\big(P(r)\,r^{n-k}\big) = P'(r)r^{n-k} + P(r)\,(n-k)r^{n-k-1}.

At a double root both $P(r)=0$ and $P'(r)=0$ , so the right side vanishes; thus $n r^n$ (a constant multiple of $n r^{n-1}$ ) is also a homogeneous solution. Iterating differentiation gives $n^j r^n$ for $j<\mu$ . $\blacksquare$ Derivation hint: Treat $r^n$ as a function of the continuous variable $r$ ; $L$ acts only on the index $n$ , so $\partial_r$ passes through it.

∎

AD

Abraham de Moivre

1667–1754

De Moivre, a French Huguenot émigré in London, was the first to systematically extract closed forms from recurrences. Studying the Fibonacci-like sequences arising in probability (gambler's ruin, runs in coin tossing), he introduced the generating-function idea and the trick of solving $a_n = a_{n-1}+a_{n-2}$ via roots of $x^2 = x + 1$ . The resulting expression $a_n = \frac{\phi^n - \psi^n}{\sqrt5}$ — later named Binet's formula after the 19th-century mathematician who popularized it — was effectively known to de Moivre and to Euler. De Moivre's Doctrine of Chances (1718, 1738, 1756) treats "recurring series" as a named topic, establishing the partial-fraction method for their summation.

🧠 Intuition

Think of a recurrence as a discrete machine that, given enough past states, computes the next. The homogeneous part captures the machine's internal dynamics — how it would evolve if left alone (geometric growth/decay, oscillation), governed entirely by the roots $r_i$ . The roots are the machine's natural modes: $|r|>1$ means a mode blows up, $|r|<1$ means it dies, $|r|=1$ means it persists, and complex roots mean it oscillates. The particular solution is the machine's forced response — the way it tracks the external input $f(n)$ . After transients (the decaying homogeneous modes) wash out, the particular solution dominates, just as a driven oscillator eventually moves at the driving frequency. The two pieces are independent because the system is linear: superposition lets you solve "natural behavior" and "forced behavior" separately and simply add them.

Figure

Root locations in the complex plane and their dynamical meaning for

a_n^{(h)}=A r^n

ExampleFibonacci — Homogeneous, Distinct Roots

Given: $a_n = a_{n-1} + a_{n-2}$ , with $a_0 = 0$ , $a_1 = 1$ . (Forcing $f(n)=0$ , so it is purely homogeneous.)

Step 1 — Characteristic equation. Rewrite as $a_n - a_{n-1} - a_{n-2}=0$ . Trial $a_n = r^n$ :

7

\quad r^2 - r - 1 = 0.

Derivation hint: divide $r^n - r^{n-1} - r^{n-2}=0$ by $r^{n-2}$ .

Step 2 — Roots.

8

\quad r = \frac{1 \pm \sqrt5}{2},\qquad \phi = \frac{1+\sqrt5}{2}\approx 1.618,\quad \psi = \frac{1-\sqrt5}{2}\approx -0.618.

Derivation hint: quadratic formula on [7].

Step 3 — General homogeneous solution. Distinct roots, so $a_n = A\phi^n + B\psi^n$ .

Step 4 — Apply initial conditions.

9

\quad \begin{cases} A + B = 0\\ A\phi + B\psi = 1\end{cases}\Rightarrow A = \tfrac{1}{\sqrt5},\; B = -\tfrac1{\sqrt5}.

Derivation hint: $n=0$ gives the first; $n=1$ the second; subtract using $\phi-\psi=\sqrt5$ .

Answer:

\boxed{\,a_n = \dfrac{\phi^n - \psi^n}{\sqrt5}\,}\qquad\text{(Binet's formula; dimensionless count)}

Check: $a_5 = \frac{11.09 - (-0.09)}{2.236}=5$ . ✓

ExampleNonhomogeneous — Repeated Root + Polynomial Forcing

Given: $a_n - 4a_{n-1} + 4a_{n-2} = 3n$ , with $a_0 = 1,\ a_1 = 2$ .

Step 1 — Homogeneous part. Characteristic equation $r^2 - 4r + 4 = (r-2)^2 = 0$ , a double root $r=2$ . By [4]:

10

\quad a_n^{(h)} = (A + Bn)\,2^n.

Derivation hint: multiplicity 2 introduces the factor $n$ .

Step 2 — Particular solution (undetermined coefficients). Forcing $f(n)=3n$ is linear and $r=1$ is not a root, so try $a_n^{(p)} = \alpha n + \beta$ . Substitute:

11

\quad (\alpha n + \beta) - 4(\alpha(n-1)+\beta) + 4(\alpha(n-2)+\beta) = 3n.

Derivation hint: shift the index in each occurrence and collect. Expanding: $\alpha n + \beta - 4\alpha n + 4\alpha - 4\beta + 4\alpha n - 8\alpha + 4\beta = \alpha n + (-4\alpha + \beta)$ . Matching:

12

\quad \alpha = 3,\qquad -4\alpha + \beta = 0 \Rightarrow \beta = 12.

So $a_n^{(p)} = 3n + 12$ . Derivation hint: coefficient of $n$ gives $\alpha=3$ ; constant term gives $\beta=4\alpha$ .

Step 3 — General solution. $a_n = (A+Bn)2^n + 3n + 12$ .

Step 4 — Initial conditions.

13

\quad \begin{cases} n=0:\ A + 12 = 1 \Rightarrow A = -11\\ n=1:\ 2(A+B) + 15 = 2 \Rightarrow A + B = -\tfrac{13}{2}\Rightarrow B = \tfrac{9}{2}\end{cases}

Derivation hint: plug $n=0,1$ into the full general solution and solve the $2\times2$ system.

Answer:

\boxed{\,a_n = \left(-11 + \tfrac{9}{2}n\right)2^n + 3n + 12\,}\quad\text{(dimensionless)}

Check $a_2$ : $(-11+9)\cdot4 + 6 + 12 = -8 + 18 = 10$ ; directly $a_2 = 4a_1 - 4a_0 + 6 = 8 - 4 + 6 = 10$ . ✓

⚠️ Common mistake

Resonance: the forcing matches a homogeneous mode. When the trial particular solution duplicates a term already in $a_n^{(h)}$ , the naive guess fails (it gets annihilated by $L$ ). You must multiply by $n^s$ , where $s$ is the multiplicity of the offending root. Concretely, for forcing $f(n) = b\,\rho^n$ :

14

\quad a_n^{(p)} = \begin{cases} C\,\rho^n & \rho\text{ is not a characteristic root}\\ C\,n^s\,\rho^n & \rho\text{ is a root of multiplicity }s.\end{cases}

Derivation hint: $L[\rho^n]=P(\rho)\rho^{n-k}$ vanishes when $\rho$ is a root; the factor $n^s$ pushes you past the kernel just as in repeated-root homogeneous solutions. Other frequent errors: (1) forgetting the $n$ -factors for repeated roots (you'll be one constant short and unable to satisfy all initial conditions); (2) applying initial conditions to $a_n^{(h)}$ before adding $a_n^{(p)}$ — always assemble the full $a_n$ first; (3) using $a_n=r^n$ on a recurrence whose coefficients are not constant (e.g. $a_n = n\,a_{n-1}$ ) — the characteristic method does not apply there.

Counterexample

Solve $a_n - 3a_{n-1} = 2\cdot 3^n$ . The homogeneous root is $r=3$ , so $a_n^{(h)} = A\,3^n$ . A student guesses $a_n^{(p)} = C\,3^n$ . Substituting:

C\,3^n - 3\cdot C\,3^{n-1} = C\,3^n - C\,3^n = 0 \ne 2\cdot 3^n.

The guess is annihilated — it lives in the kernel. Because $\rho=3$ is a root of multiplicity $1$ , the correct ansatz is $a_n^{(p)} = C\,n\,3^n$ :

C n 3^n - 3 C(n-1)3^{n-1} = C n 3^n - C(n-1)3^{n} = C\,3^n = 2\cdot 3^n \Rightarrow C=2.

Hence $a_n^{(p)} = 2n\,3^n$ . The "obvious" guess gave a contradiction precisely because of resonance.

connection

Linear recurrences are the discrete shadow of Linear Differential Equations with Constant Coefficients: the shift operator $E$ (where $Ea_n = a_{n+1}$ ) plays the role of $\frac{d}{dt}$ , and the characteristic polynomial is identical in spirit. The homogeneous/particular split is the same affine-coset structure seen in any Linear Systems of Equations ( $Lx=b$ ). Generating Functions give an alternative, often more powerful, solution route — encoding a sequence as $\sum a_n x^n$ converts the recurrence into an algebraic equation whose partial-fraction expansion re-derives the root-based closed form. Higher-order recurrences also reduce to first-order vector recurrences $\mathbf{v}_n = M\mathbf{v}_{n-1}$ , linking the topic to Eigenvalues and Eigenvectors: the characteristic roots $r_i$ are exactly the eigenvalues of the companion matrix $M$ , and repeated roots correspond to nontrivial Jordan Normal Form blocks.

🔬 Where this appears

⏳ History

- 1202 — Leonardo of Pisa (Fibonacci), in Liber Abaci, poses the rabbit problem giving

F_n = F_{n-1}+F_{n-2}

, the archetypal recurrence (though without a closed form).

- 1718 — Abraham de Moivre, Doctrine of Chances, introduces "recurring series" and the technique of summing them via roots of an auxiliary equation.

- 1748 — Leonhard Euler, Introductio in analysin infinitorum, systematizes generating functions and partial-fraction extraction of recurrence solutions.

- 1759 — Joseph-Louis Lagrange develops the general theory of linear difference and differential equations in parallel, clarifying the role of repeated roots.

- 1782 — Pierre-Simon Laplace advances the operational/symbolic treatment of difference equations in probability theory (Théorie analytique des probabilités, 1812).

- 1843 — Jacques Binet publishes the closed-form

\frac{\phi^n-\psi^n}{\sqrt5}

, which thereafter bears his name despite earlier knowledge.

- 1860s — George Boole, A Treatise on the Calculus of Finite Differences, gives the definitive 19th-century exposition of difference equations, including the operator

E

and undetermined coefficients.

- 1939 — Paul Samuelson applies second-order recurrences to macroeconomic business cycles, popularizing the dynamical interpretation of complex roots.

- 20th c. — The companion-matrix/eigenvalue viewpoint and connections to control theory and numerical stability (Dahlquist's analysis of multistep methods, 1956) place recurrences firmly within linear algebra and dynamical systems.

open-problem

The clean closed-form theory is fragile outside the linear-constant-coefficient world.

Variable coefficients. For $a_n = p(n)a_{n-1} + q(n)a_{n-2}$ with polynomial $p,q$ , no characteristic-polynomial method exists in general. Whether such a recurrence admits a closed-form (hypergeometric or "Liouvillian") solution is decidable by Petkovšek's algorithm (1992) and the Gosper/Zeilberger machinery, but a general elementary solution need not exist.
Nonlinear recurrences. Even the innocent-looking logistic map $a_{n+1}=\lambda a_n(1-a_n)$ has no closed form for general $\lambda$ and exhibits chaos; superposition fails entirely.
Skolem's Problem. For a linear recurrence over the integers, deciding whether some term equals zero (the Skolem–Mahler–Lech zero set is known to be eventually periodic) is not known to be decidable — a long-standing open problem at the boundary of number theory and computability, despite the apparent simplicity of the underlying recurrence.
Repeated-root forcing combinations. When $f(n)$ is itself a sum of resonant and non-resonant terms, the correct particular ansatz requires treating each piece with its own resonance multiplier; bookkeeping errors here are the most common source of incorrect final answers.

Recurrence Relations — Homogeneous and Particular Solutions

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also