Difference and functional equations Linear difference equations Proposition

Superposition of solutions

Builds on Homogeneous and inhomogeneous linear recurrences Sequence

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.

If $Lu = 0$ and $Lv = 0$ , then $L(\alpha u + \beta v) = 0$ for all $\alpha, \beta \in K$ .
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$ .
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 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.

Going deeper

For a student

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; 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 for difference equations.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Homogeneous and inhomogeneous linear recurrences concept
Sequence concept
Superposition of solutions statement

Tag	`7W7VV861JW`
URI	`m2://7W7VV861JW`
Kind	statement, proposition
Writing	W0 stub
MSC	39A06
Status	This copy of the site has no build data. Run `m2 status 7W7VV861JW`.
About	Homogeneous and inhomogeneous linear recurrences
Uses	Homogeneous and inhomogeneous linear recurrences, Sequence