Solving Linear Recurrences

We proceed by three steps: (a) show $S$ is a $k$-dimensional vector space by exhibiting an explicit isomorphism with $\mathbb{C}^k$; (b) verify each proposed basis element actually lies in $S$; (c) verify the $k$ proposed basis elements are linearly independent, which combined with (a) shows they form a basis, giving statement 3.

Step (a): $S$ is a $k$-dimensional vector space. If $(a_n), (b_n) \in S$ and $\lambda, \mu$ are scalars, then for $n \ge k$,

using linearity of the recurrence; hence $\lambda a + \mu b \in S$. So $S$ is a vector space. Define $\Phi: S \to \mathbb{C}^k$ by $\Phi((a_n)) = (a_0, a_1, \dots, a_{k-1})$. This is linear. It is injective: if $(a_n)$ and $(a_n')$ agree on their first $k$ terms and both satisfy (H), then by strong induction on $n$, for $n \ge k$,

where the middle equality uses the inductive hypothesis that $a_{n-i} = a_{n-i}'$ for all $1 \le i \le k$ (each index $n - i < n$). So $(a_n) = (a_n')$. It is surjective: given any $(x_0, \dots, x_{k-1}) \in \mathbb{C}^k$, define $a_0 = x_0, \dots, a_{k-1} = x_{k-1}$ and extend by the recurrence $a_n = \sum_{i=1}^k c_i a_{n-i}$ for $n \ge k$; this is a well-defined sequence in $S$ mapping to $(x_0,\dots,x_{k-1})$ under $\Phi$. Hence $\Phi$ is a linear isomorphism, so $\dim S = k$.

Step (b): each $n^j r_i^n$ satisfies (H). Fix a root $r$ of $p$ with multiplicity $m$, and fix $0 \le j \le m - 1$; we show $a_n := n^j r^n \in S$. It suffices to prove the polynomial identity: for all $n$,

Case $r = 0$: then since $p(x) = x^k - c_1 x^{k-1} - \cdots - c_k$ has $c_k \ne 0$ (given), $x = 0$ is a root of $p$ iff $c_k = 0$, contradiction — so $r \ne 0$ always. Good, this simplifies matters: we may always divide by powers of $r$. Divide $(\ast)$ by $r^{n-k}$ (nonzero since $r \ne 0$); it becomes, writing $x = r$ symbolically for the moment via a generating identity in $x$: consider the polynomial in $x$,

We must show $Q_n(r) = 0$ whenever $r$ is a root of $p(x)$ of multiplicity $\ge j+1$ (since $j \le m-1$ means multiplicity $m \ge j + 1$). This is most cleanly done using the standard "differentiate the generating identity" trick. Consider the two-variable identity in $x$:

We instead argue directly by the operator method, which is rigorous and avoids clumsy algebra. Define the shift operator $E$ on sequences by $(Ea)_n = a_{n+1}$, and consider the operator

acting on sequences indexed by $n \ge 0$; then $(a_n) \in S$ exactly means $(La)_n = 0$ for all $n \ge 0$ (this is a re-indexing of (H): applying $L$ to $(a_n)$ and evaluating at index $n$ reads $a_{n+k} - c_1 a_{n+k-1} - \cdots - c_k a_n = 0$, i.e. (H) at index $n + k$). Operators built from $E$ commute and factor exactly as polynomials in $E$ do, since $E$ commutes with itself; concretely $L = q(E)$ where $q(x) = p(x)$ up to the correspondence $E^k \leftrightarrow x^k$. Since $p(x) = \prod_i (x - r_i)^{m_i}$, we get the operator factorization

where $I$ is the identity operator and the factors commute (polynomials in the same operator $E$ always commute). Now we use the elementary fact, provable by direct computation: for any constant $r$ and any polynomial $q$ of degree $< m$ in $n$,

Indeed $(E - rI)(q(n)r^n) = q(n+1) r^{n+1} - r\cdot q(n) r^n = (q(n+1) - q(n)) r^{n+1}$. If $\deg q \le d$ then $q(n+1) - q(n)$ is a polynomial in $n$ of degree $\le d - 1$ (the leading terms cancel — this is the standard finite-difference degree drop). Hence applying $(E - rI)$ repeatedly $m$ times to $n^j r^n$ (with $j \le m-1 < m$) drives the polynomial factor's degree down by one each time, past degree $0$, to the zero polynomial after at most $m$ applications; formally, by induction on $j$: $(E-rI)^{j+1}(n^j r^n) = 0$, and since $j + 1 \le m_i$, also $(E - r_iI)^{m_i}(n^j r_i^n) = 0$. Therefore $(E - r_i I)^{m_i} (n^j r_i^n) = 0$, and since the other factors $(E - r_\ell I)^{m_\ell}$ for $\ell \ne i$ commute with this one, applying all of $L = \prod_\ell (E-r_\ell I)^{m_\ell}$ to $n^j r_i^n$ gives $0$ as well (apply the vanishing factor last, using commutativity). Hence $L(n^j r_i^n) = 0$, i.e. $n^j r_i^n \in S$. This proves step (b) for every basis candidate.

Step (c): the $k$ sequences $\{n^j r_i^n\}$ are linearly independent. Since $\dim S = k$ (Step a) and we have exhibited $k$ elements of $S$ (Step b, and $\sum_i m_i = k$ so there are exactly $k$ of them), it suffices to show they are linearly independent; then they automatically form a basis. Suppose

where $P_i(n) = \sum_{j=0}^{m_i - 1} \beta_{i,j} n^j$. We must show all $\beta_{i,j} = 0$. Suppose not all are zero; among the $i$ with $P_i \not\equiv 0$, this is a nontrivial linear relation among "generalized exponentials" with distinct bases $r_i$. We prove no such nontrivial relation can hold, by induction on $t$ (the number of distinct roots appearing with $P_i \not\equiv 0$). If $t = 1$: $(\dagger)$ reads $P_1(n) r_1^n = 0$ for all $n$, and since $r_1 \ne 0$, $P_1(n) = 0$ for all $n \ge 0$, forcing $P_1$ to be the zero polynomial (a nonzero polynomial has finitely many roots, but $P_1$ vanishes at all $n \ge 0$, infinitely many points), so all its coefficients vanish. Inductive step: suppose the claim holds for fewer than $t$ terms, $t \ge 2$, and suppose $(\dagger)$ holds with all $t$ polynomials $P_i \not\equiv 0$ and roots $r_1,\dots,r_t$ distinct and nonzero. Divide $(\dagger)$ by $r_t^n$:

Apply the finite-difference operator $\Delta$, $(\Delta f)(n) = f(n+1) - f(n)$, exactly $\deg P_t + 1$ times to both sides, as a function of $n$. Applying $\Delta$ to $P_t(n)$ (a polynomial of degree $\deg P_t$) reduces its degree by $1$ each time (standard fact: leading terms cancel), so after $\deg P_t + 1$ applications $P_t$ is annihilated. Applying $\Delta$ to a term $P_i(n) \rho^n$ with $\rho := r_i/r_t \ne 1$ (since $r_i \ne r_t$) gives $\rho^n\big(P_i(n+1)\rho - P_i(n)\big)$, which is again of the form $\widetilde P_i(n)\rho^n$ with $\widetilde P_i$ of the same degree as $P_i$ (its leading coefficient is $(\rho - 1)$ times the leading coefficient of $P_i$, nonzero since $\rho \ne 1$). So after all these applications of $\Delta$, we obtain a relation

with each $\widetilde P_i \not\equiv 0$ and $t - 1$ distinct nonzero bases $r_i/r_t$. This contradicts the inductive hypothesis (fewer than $t$ terms, all coefficients forced to vanish, yet we just showed the leading coefficients are nonzero multiples of the original ones). This contradiction shows no such nontrivial relation exists, completing the induction. Hence the $k$ sequences $n^j r_i^n$ are linearly independent, and since $\dim S = k$, they form a basis of $S$. This proves statements 1 and 2.

Conclusion (statement 3). Since $\{n^j r_i^n\}$ is a basis of $S$, every $(a_n) \in S$ is a unique linear combination of these basis vectors, i.e.

for unique constants $\beta_{i,j}$. Because $\Phi$ (from Step a) is an isomorphism, these constants are determined uniquely once $a_0, \dots, a_{k-1}$ are fixed, by solving the resulting linear system — which has a unique solution precisely because $\Phi$ is injective. $\blacksquare$

This is a direct application of linear algebra to the affine structure of (N); we give a self-contained argument (a standard technique, sometimes called the superposition principle). ($\Leftarrow$) Suppose $a_n = a_n^{(h)} + a_n^{(p)}$ where $(a_n^{(h)}) \in S$ (the homogeneous solution space) and $(a_n^{(p)})$ satisfies (N). Then for $n \ge k$,

The first bracket equals $a_n^{(h)}$ since $(a_n^{(h)})$ satisfies (H); the second equals $a_n^{(p)}$ since $(a_n^{(p)})$ satisfies (N). Summing, the right side is $a_n^{(h)} + a_n^{(p)} = a_n$, which is exactly the claim that $(a_n)$ satisfies (N). ($\Rightarrow$) Suppose $(a_n)$ satisfies (N). Define $b_n := a_n - a_n^{(p)}$ for all $n \ge 0$. For $n \ge k$,

So $(b_n)$ satisfies the homogeneous recurrence (H), i.e. $(b_n) \in S$, hence by the homogeneous solution theorem $b_n = a_n^{(h)}$ for some choice of the free parameters $\beta_{i,j}$. Then $a_n = b_n + a_n^{(p)} = a_n^{(h)} + a_n^{(p)}$, as required.

Uniqueness of parameters. Given initial conditions $a_0,\dots,a_{k-1}$, the values $b_0,\dots,b_{k-1} = a_0 - a_0^{(p)}, \dots, a_{k-1} - a_{k-1}^{(p)}$ are determined. By the isomorphism $\Phi$ from the homogeneous theorem's proof, these determine the parameters $\beta_{i,j}$ of $(b_n) = (a_n^{(h)})$ uniquely. Hence the decomposition $a_n = a_n^{(h)} + a_n^{(p)}$ with prescribed initial data has a unique choice of parameters. $\blacksquare$