---
tag: 7W7VV861JW
kind: statement
role: proposition
name: Superposition of solutions
msc: [39A06]
uses: [8Y28JQB0Q5, 0G9EKM0E15]
about: [8Y28JQB0Q5]
sources:
  - url: https://en.wikipedia.org/wiki/Superposition_principle
---

## Statement

Let $K$ be a field, let $d \ge 1$, and let $a_0, \dots, a_{d-1} \colon \N \to K$ be sequences.
For a sequence $u \colon \N \to K$, let $Lu$ be the sequence
$$(Lu)(n) = u_{n+d} + a_{d-1}(n)\, u_{n+d-1} + \cdots + a_0(n)\, u_n .$$
Then the following hold.

1. If $Lu = 0$ and $Lv = 0$, then $L(\alpha u + \beta v) = 0$ for all $\alpha, \beta \in K$.
2. If $Lu = g_1$ and $Lv = g_2$, then $L(\alpha u + \beta v) = \alpha g_1 + \beta g_2$ for all $\alpha, \beta \in K$.
3. If $Lp = g$, then a sequence $u$ satisfies $Lu = g$ if and only if $u = p + h$ for a sequence $h$ with $Lh = 0$.

## Remarks

All three parts follow from the linearity of $L$: $L(\alpha u + \beta v) = \alpha Lu + \beta Lv$, which one checks term by term.
For part 3, if $Lu = g$ then $L(u - p) = g - g = 0$, and conversely $L(p + h) = g + 0 = g$.
Example: for $u_{n+1} - 2 u_n = 1$, the constant $p_n = -1$ is a particular solution, and the [[homogeneous|8Y28JQB0Q5]] solutions are $c\, 2^n$, so all solutions are $c\, 2^n - 1$.
Linearity is necessary: for $u_{n+1} = u_n^2$, the sequence $u_n = 1$ is a solution, but $2u$ is not, since $2 \ne 4$.
The same principle holds for linear differential equations; see the [[superposition principle|0F2VBPXNP9]].

## Explanations

### L1 human

For a linear recurrence, you can add solutions and scale them, and the result is again a solution of the matching equation.
So to solve an inhomogeneous recurrence, find one solution of it by any trick, then add all solutions of the homogeneous recurrence.

### L2 human

Part 1 says that the solutions of a homogeneous linear recurrence form a vector space over $K$.
Since the leading coefficient is $1$, the first $d$ terms determine a solution, by the same induction as in [[uniqueness given initial values|WREYNFJHH2]]; so this space has dimension $d$.
Part 3 says that the solutions of the inhomogeneous recurrence form an affine space, a translate of that vector space.
This is the base of the method of undetermined coefficients and of [[variation of parameters|QQFYC988SJ]] for difference equations.