7.5: More on Linear Recurrences

More on Linear Recurrences¹

In Section 3.4 we used diagonalization to study linear recurrences, and gave several examples. We now apply the theory of vector spaces and linear transformations to study the problem in more generality.

Consider the linear recurrence

\[x_{n+2} = 6x_n - x_{n+1} \quad \mbox{for } n \geq 0 \nonumber \]

If the initial values \(x_{0}\) and \(x_{1}\) are prescribed, this gives a sequence of numbers. For example, if \(x_{0} = 1\) and \(x_{1} = 1\) the sequence continues

\[x_2 = 5, x_3 = 1, x_4 = 29, x_5 = -23, x_6 = 197, \dots \nonumber \]

as the reader can verify. Clearly, the entire sequence is uniquely determined by the recurrence and the two initial values. In this section we define a vector space structure on the set of all sequences, and study the subspace of those sequences that satisfy a particular recurrence.

Sequences will be considered entities in their own right, so it is useful to have a special notation for them. Let

\[[x_n) \quad \mbox{denote the sequence } x_0, x_1, x_2, \dots, x_n, \dots \nonumber \]

Example \(\PageIndex{1}\)

\[\begin{aligned} &[n) & \quad\quad &\mbox{is the sequence } 0, 1, 2, 3, \dots \\ &[n + 1) & \quad\quad &\mbox{is the sequence } 1, 2, 3, 4, \dots \\ &[2^n) & \quad\quad &\mbox{is the sequence } 1, 2, 2^2, 2^3, \dots \\ &[(-1)^n) & \quad\quad &\mbox{is the sequence } 1, -1, 1, -1, \dots \\ &[5) & \quad\quad &\mbox{is the sequence } 5, 5, 5, 5, \dots\end{aligned} \nonumber \]

Sequences of the form \([c)\) for a fixed number \(c\) will be referred to as constant sequences, and those of the form \([\lambda^{n})\), \(\lambda\) some number, are power sequences.

Two sequences are regarded as equal when they are identical:

\[[x_n) = [y_n) \quad \mbox{means} \quad x_n = y_n \quad \mbox{for all } n = 0, 1, 2, \dots \nonumber \]

Addition and scalar multiplication of sequences are defined by

\[\begin{align*} [x_n) + [y_n) &= [x_n + y_n) \\[4pt] r[x_n) &= [rx_n) \end{align*} \]

These operations are analogous to the addition and scalar multiplication in \(\mathbb{R}^n\), and it is easy to check that the vector-space axioms are satisfied. The zero vector is the constant sequence \([0)\), and the negative of a sequence \([x_{n})\) is given by \(-[x_{n}) = [-x_{n})\).

Now suppose \(k\) real numbers \(r_{0}, r_{1}, \dots, r_{k-1}\) are given, and consider the linear recurrence relation determined by these numbers.

\[ x_{n+k} = r_{0}x_{n} + r_{1}x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \label{eq:linRecurrRel}\]

When \(r_{0} \neq 0\), we say this recurrence has length \(k\).² For example, the relation \(x_{n+2} = 2x_{n}+ x_{n+1}\) is of length \(2\).

Note

We shall usually assume that \(r_{0} \neq 0\); otherwise, we are essentially dealing with a recurrence of shorter length than \(k\).

A sequence \([x_{n})\) is said to satisfy the relation (\ref{eq:linRecurrRel}) if (\ref{eq:linRecurrRel}) holds for all \(n \geq 0\). Let \(V\) denote the set of all sequences that satisfy the relation. In symbols,

\[V = \{[x_n) \mid x_{n+k} = r_{0}x_{n} + r_{1}x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \mbox{ hold for all } n \geq 0\} \nonumber \]

It is easy to see that the constant sequence \([0)\) lies in \(V\) and that \(V\) is closed under addition and scalar multiplication of sequences. Hence \(V\) is vector space (being a subspace of the space of all sequences). The following important observation about \(V\) is needed (it was used implicitly earlier): If the first \(k\) terms of two sequences agree, then the sequences are identical. More formally,

Lemma \(\PageIndex{1}\)

Let \([x_n)\) and \([y_n)\) denote two sequences in \(V\). Then

\[[x_n) = [y_n) \quad \mbox{if and only if } \quad x_0 = y_0, \ x_1 = y_1, \dots, x_{k-1} = y_{k-1} \nonumber \]

Proof

If \([x_{n}) = [y_{n})\) then \(x_{n} = y_{n}\) for all \(n = 0, 1, 2, \dots\). Conversely, if \(x_{i} = y_{i}\) for all \(i = 0, 1, \dots, k - 1\), use the recurrence (\ref{eq:linRecurrRel}) for \(n = 0\).

\[x_{k} = r_{0}x_{0} + r_{1}x_{1} + \cdots + r_{k-1}x_{k-1} = r_{0}y_{0} + r_{1}y_{1} + \cdots + r_{k-1}y_{k-1} = y_{k} \nonumber \]

Next the recurrence for \(n = 1\) establishes \(x_{k+1} = y_{k+1}\). The process continues to show that \(x_{n+k} = y_{n+k}\) holds for all \(n \geq 0\) by induction on \(n\). Hence \([x_{n}) = [y_{n})\).

\(\square\)

This shows that a sequence in \(V\) is completely determined by its first \(k\) terms. In particular, given a \(k\)-tuple \(\mathbf{v} = (v_{0}, v_{1}, \dots, v_{k-1})\) in \(\mathbb{R}^k\), define

\[T(\mathbf{v}) \mbox{ to be the sequence in } V \mbox{ whose first } k \mbox{ terms are } v_0, v_1, \dots, v_{k-1} \nonumber \]

The rest of the sequence \(T(\mathbf{v})\) is determined by the recurrence, so \(T : \mathbb{R}^k \to V\) is a function. In fact, it is an isomorphism.

Theorem \(\PageIndex{1}\)

Given real numbers \(r_{0}, r_{1}, \dots, r_{k-1}\), let

\[V = \{[x_n) \mid x_{n+k} = r_{0}x_{n} + r_{1}x_{n+1} + \cdots + r_{k-1}x_{n+k-1}, \mbox{ for all } n \geq 0\} \nonumber \]

denote the vector space of all sequences satisfying the linear recurrence relation (\ref{eq:linRecurrRel}) determined by \(r_{0}, r_{1}, \dots, r_{k-1}\). Then the function

\[T : \mathbb{R}^k \to V \nonumber \]

defined above is an isomorphism. In particular:

1. \(dim \;V = k\).
2. If \(\{\mathbf{v}_{1}, \dots, \mathbf{v}_{k}\}\) is any basis of \(\mathbb{R}^k\), then \(\{T(\mathbf{v}_{1}), \dots, T(\mathbf{v}_{k})\}\) is a basis of \(V\).

Proof

(1) and (2) will follow from Theorem 7.3.1 and Theorem 7.3.2 as soon as we show that \(T\) is an isomorphism. Given \(\mathbf{v}\) and \(\mathbf{w}\) in \(\mathbb{R}^k\), write \(\mathbf{v} = (v_{0}, v_{1}, \dots, v_{k-1})\) and \(\mathbf{w} = (w_{0}, w_{1}, \dots, w_{k-1})\). The first \(k\) terms of \(T(\mathbf{v})\) and \(T(\mathbf{w})\) are \(v_{0}, v_{1}, \dots, v_{k-1}\) and \(w_{0}, w_{1}, \dots, w_{k-1}\), respectively, so the first \(k\) terms of \(T(\mathbf{v}) + T(\mathbf{w})\) are \(v_{0} + w_{0}, v_{1} + w_{1}, \dots, v_{k-1} + w_{k-1}\). Because these terms agree with the first \(k\) terms of \(T(\mathbf{v} + \mathbf{w})\), Lemma 7.5.1 implies that \(T(\mathbf{v} + \mathbf{w}) = T(\mathbf{v}) + T(\mathbf{w})\). The proof that \(T(r\mathbf{v}) + rT(\mathbf{v})\) is similar, so \(T\) is linear.

Now let \([x_{n})\) be any sequence in \(V\), and let \(\mathbf{v} = (x_{0}, x_{1}, \dots, x_{k-1})\). Then the first \(k\) terms of \([x_{n})\) and \(T(\mathbf{v})\) agree, so \(T(\mathbf{v}) = [x_{n})\). Hence \(T\) is onto. Finally, if \(T(\mathbf{v}) = [0)\) is the zero sequence, then the first \(k\) terms of \(T(\mathbf{v})\) are all zero (all terms of \(T(\mathbf{v})\) are zero!) so \(\mathbf{v} = \mathbf{0}\). This means that \(\text{ker }T = \{\mathbf{0}\}\), so \(T\) is one-to-one.

\(\square\)

Example \(\PageIndex{2}\)

Show that the sequences \([1)\), \([n)\), and \([(-1)^{n})\) are a basis of the space \(V\) of all solutions of the recurrence

\[x_{n+3} = -x_{n} + x_{n+1} + x_{n+2} \nonumber \]

Then find the solution satisfying \(x_{0} = 1\), \(x_{1} = 2\), \(x_{2} = 5\).

Solution

The verifications that these sequences satisfy the recurrence (and hence lie in \(V\)) are left to the reader. They are a basis because \([1) = T(1, 1, 1)\), \([n) = T(0, 1, 2)\), and \([(-1)^{n}) = T(1, -1, 1)\); and \(\{(1, 1, 1), (0, 1, 2), (1, -1, 1)\}\) is a basis of \(\mathbb{R}^3\). Hence the sequence \([x_{n})\) in \(V\) satisfying \(x_{0} = 1\), \(x_{1} = 2\), \(x_{2} = 5\) is a linear combination of this basis:

\[[x_n) = t_1[1) + t_2[n) + t_3[(-1)^n) \nonumber \]

The \(n\)th term is \(x_{n} = t_{1} + nt_{2} + (-1)^{n}t_{3}\), so taking \(n = 0, 1, 2\) gives

\[ \begin{array}{ccccccccc} 1 & = & x_0 & = & t_1 & + & 0 & + & t_3 \\ 2 & = & x_1 & = &t_1 & + & t_2 & - & t_3 \\ 5 & = & x_2 & = & t_1 & + & 2t_2 & + & t_3 \end{array} \nonumber \]

This has the solution \(t_1 = t_3 = \frac{1}{2}\), \(t_2 = 2\), so \(x_n = \frac{1}{2} + 2n + \frac{1}{2}(-1)^n\).

This technique clearly works for any linear recurrence of length \(k\): Simply take your favorite basis \(\{\mathbf{v}_{1}, \dots, \mathbf{v}_{k}\}\) of \(\mathbb{R}^k\)—perhaps the standard basis—and compute \(T(\mathbf{v}_{1}), \dots, T(\mathbf{v}_{k})\). This is a basis of \(V\) all right, but the \(n\)th term of \(T(\mathbf{v}_{i})\) is not usually given as an explicit function of \(n\). (The basis in Example 7.5.2 was carefully chosen so that the \(n\)th terms of the three sequences were \(1\), \(n\), and \((-1)^{n}\), respectively, each a simple function of \(n\).)

However, it turns out that an explicit basis of \(V\) can be given in the general situation. Given the recurrence (\ref{eq:linRecurrRel}) again:

\[x_{n+k} = r_{0}x_{n} + r_{1}x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \nonumber \]

the idea is to look for numbers \(\lambda\) such that the power sequence \([\lambda^{n})\) satisfies (\ref{eq:linRecurrRel}). This happens if and only if

\[\lambda^{n+k} = r_{0}\lambda^{n} + r_{1}\lambda^{n+1} + \cdots + r_{k-1}\lambda^{n+k-1} \nonumber \]

holds for all \(n \geq 0\). This is true just when the case \(n = 0\) holds; that is,

\[\lambda^k = r_0 + r_1\lambda + \cdots + r_{k-1}\lambda^{k-1} \nonumber \]

The polynomial

\[p(x) = x^k - r_{k-1}x^{k-1} - \cdots - r_1x - r_0 \nonumber \]

is called the polynomial associated with the linear recurrence (\ref{eq:linRecurrRel}). Thus every root \(\lambda\) of \(p(x)\) provides a sequence \([\lambda^{n})\) satisfying (\ref{eq:linRecurrRel}). If there are \(k\) distinct roots, the power sequences provide a basis. Incidentally, if \(\lambda = 0\), the sequence \([\lambda^{n})\) is \(1, 0, 0, \dots\); that is, we accept the convention that \(0^{0} = 1\).

Theorem \(\PageIndex{2}\)

Let \(r_{0}, r_{1}, \dots, r_{k-1}\) be real numbers; let

\[V = \{[x_n) \mid x_{n+k} = r_0x_n + r_1x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \mbox{ for all } n \geq 0\} \nonumber \]

denote the vector space of all sequences satisfying the linear recurrence relation determined by \(r_{0}, r_{1}, \dots, r_{k-1}\); and let

\[p(x) = x^k -r_{k-1}x^{k-1} - \cdots - r_1x - r_0 \nonumber \]

denote the polynomial associated with the recurrence relation. Then

1. \([\lambda^{n})\) lies in \(V\) if and only if \(\lambda\) is a root of \(p(x)\).
2. If \(\lambda_1, \lambda_2, \dots, \lambda_k\) are distinct real roots of \(p(x)\), then \(\{[\lambda_{1}^{n}), [\lambda_2^{n}), \dots, [\lambda_k^{n})\}\) is a basis of \(V\).

Proof

It remains to prove (2). But \([\lambda_{i}^{n}) = T(\mathbf{v}_{i})\) where \(\mathbf{v}_{i} = (1, \lambda_{i}, \lambda_{i}^{2}, \dots, \lambda_{i}^{k-1})\), so (2) follows by Theorem 7.5.1, provided that \((\mathbf{v}_{1}, \mathbf{v}_{2}, \dots, \mathbf{v}_{n})\) is a basis of \(\mathbb{R}^k\). This is true provided that the matrix with the \(\mathbf{v}_{i}\) as its rows

\[\left[ \begin{array}{ccccc} 1 & \lambda_1 & \lambda_1^2 & \cdots & \lambda_1^{k-1} \\ 1 & \lambda_2 & \lambda_2^2 & \cdots & \lambda_2^{k-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \lambda_k & \lambda_k^2 & \cdots & \lambda_k^{k-1} \end{array} \right] \nonumber \]

is invertible. But this is a Vandermonde matrix and so is invertible if the \(\lambda_{i}\) are distinct (Theorem 3.2.7). This proves (2).

\(\square\)

Example \(\PageIndex{3}\)

Find the solution of \(x_{n+2} = 2x_{n} + x_{n+1}\) that satisfies \(x_{0} = a\), \(x_{1} = b\).

Solution

The associated polynomial is \(p(x) = x^{2} - x - 2 = (x - 2)(x + 1)\). The roots are \(\lambda_{1} = 2\) and \(\lambda_{2} = -1\), so the sequences \([2^n)\) and \([(-1)^n)\) are a basis for the space of solutions by Theorem 7.5.2. Hence every solution \([x_{n})\) is a linear combination

\[[x_n) = t_1[2^n) + t_2[(-1)^n) \nonumber \]

This means that \(x_{n} = t_{1}2^{n} + t_{2}(-1)^{n}\) holds for \(n = 0, 1, 2, \dots\), so (taking \(n = 0, 1\)) \(x_{0} = a\) and \(x_{1} = b\) give

\[\begin{aligned} t_1 + t_2 &= a \\ 2t_1 - t_2 &= b\end{aligned} \nonumber \]

These are easily solved: \(t_1 = \frac{1}{3}(a + b)\) and \(t_2 = \frac{1}{3}(2a - b)\), so

\[t_n = \frac{1}{3}\left[(a + b)2^n + (2a - b)(-1)^n\right] \nonumber \]

The Shift Operator

If \(p(x)\) is the polynomial associated with a linear recurrence relation of length \(k\), and if \(p(x)\) has \(k\) distinct roots \(\lambda_{1}, \lambda_{2}, \dots, \lambda_{k}\), then \(p(x)\) factors completely:

\[p(x) = (x - \lambda_1)(x - \lambda_2)\cdots(x - \lambda_k) \nonumber \]

Each root \(\lambda_{i}\) provides a sequence \([\lambda_{i}^{n})\) satisfying the recurrence, and they are a basis of \(V\) by Theorem 7.5.2. In this case, each \(\lambda_{i}\) has multiplicity \(1\) as a root of \(p(x)\). In general, a root \(\lambda\) has multiplicity \(m\) if \(p(x) = (x - \lambda)^{m}q(x)\), where \(q(\lambda) \neq 0\). In this case, there are fewer than \(k\) distinct roots and so fewer than \(k\) sequences \([\lambda^{n})\) satisfying the recurrence. However, we can still obtain a basis because, if \(\lambda\) has multiplicity \(m\) (and \(\lambda \neq 0\)), it provides \(m\) linearly independent sequences that satisfy the recurrence. To prove this, it is convenient to give another way to describe the space \(V\) of all sequences satisfying a given linear recurrence relation.

Let \(\mathbf{S}\) denote the vector space of all sequences and define a function

\[S : \mathbf{S} \to \mathbf{S} \quad \mbox{by} \quad S[x_n) = [x_{n+1}) = [x_1, \ x_2, \ x_3, \ \dots) \nonumber \]

\(S\) is clearly a linear transformation and is called the shift operator on \(\mathbf{S}\). Note that powers of \(S\) shift the sequence further: \(S^{2}[x_{n}) = S[x_{n+1}) = [x_{n+2})\). In general,

\[S^k[x_n) = [x_{n+k}) = [x_k, \ x_{k+1}, \ \dots) \quad \mbox{for all } k = 0, 1, 2, \dots \nonumber \]

But then a linear recurrence relation

\[x_{n+k} = r_0x_n + r_1x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \quad \mbox{for all } n = 0, 1, \dots \nonumber \]

can be written

\[\label{eq:shiftOperator} S^k[x_n) = r_0[x_n) + r_1S[x_n) + \cdots + r_{k-1}S^{k-1}[x_n) \]

Now let \(p(x) = x^{k} - r_{k-1}x^{k-1} - \cdots - r_{1}x - r_{0}\) denote the polynomial associated with the recurrence relation. The set \(\mathbf{L}[\mathbf{S}, \mathbf{S}]\) of all linear transformations from \(\mathbf{S}\) to itself is a vector space (verify³) that is closed under composition. In particular,

\[p(S) = S^k - r_{k-1}S^{k-1} - \cdots - r_1S - r_0 \nonumber \]

is a linear transformation called the evaluation of \(p\) at \(S\). The point is that condition (\ref{eq:shiftOperator}) can be written as

\[p(S)\{[x_n)\} = 0 \nonumber \]

In other words, the space \(V\) of all sequences satisfying the recurrence relation is just \(\text{ker}[p(S)]\). This is the first assertion in the following theorem.

Theorem \(\PageIndex{3}\)

Let \(r_{0}, r_{1}, \dots, r_{k-1}\) be real numbers, and let

\[V = \{[x_n) \mid x_{n+k} = r_{0}x_n + r_{1}x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \quad \mbox{for all } n \geq 0\} \nonumber \]

denote the space of all sequences satisfying the linear recurrence relation determined by \(r_{0}, r_{1}, \dots, r_{k-1}\). Let

\[p(x) = x^k - r_{k-1}x^{k-1} - \cdots - r_{1}x - r_0 \nonumber \]

denote the corresponding polynomial. Then:

1. \(V = \text{ker}[p(S)]\), where \(S\) is the shift operator.
2. If \(p(x)=(x-\lambda)^m q(x)\), where \(\lambda \neq 0\) and \(m>1\), then the sequences \[\{[\lambda^n), [n\lambda^n), [n^2\lambda^n), \dots, [n^{m-1}\lambda^n)\} \nonumber \] all lie in V and are linearly independent.

Proof (Sketch)

It remains to prove (2). If \(\binom{n}{k} = \frac{n(n - 1) \cdots (n - k + 1)}{k!}\) denotes the binomial coefficient, the idea is to use (1) to show that the sequence \(s_k = \left[\binom{n}{k} \lambda^n \right)\) is a solution for each \(k = 0, 1, \dots, m - 1\). Then (2) of Theorem 7.5.1 can be applied to show that \(\left\{s_0, s_1, \ldots, s_{m-1}\right\}\) is linearly independent. Finally, the sequences \(t_k=\left[n^k \lambda^n\right), k=0,1, \ldots, m-1\), in the present theorem can be given by \(t_k=\sum_{j=0}^{m-1} a_{k j} s_j\), where \(A=\left[a_{i j}\right]\) is an invertible matrix. Then (2) follows. We omit the details.

\(\square\)

This theorem combines with Theorem 7.5.2 to give a basis for \(V\) when \(p(x)\) has \(k\) real roots (not necessarily distinct) none of which is zero. This last requirement means \(r_{0} \neq 0\), a condition that is unimportant in practice (see Remark 1 below).

Theorem \(\PageIndex{4}\)

Let \(r_{0}, r_{1}, \dots, r_{k-1}\) be real numbers with \(r_{0} \neq 0\); let

\[V = \{[x_n) \mid x_{n+k} = r_{0}x_n + r_{1}x_{n+1} + \cdots + r_{k-1}x_{n+k-1} \mbox{ for all } n \geq 0 \} \nonumber \]

denote the space of all sequences satisfying the linear recurrence relation of length \(k\) determined by \(r_{0}, \dots, r_{k-1}\); and assume that the polynomial

\[p(x) = x^k - r_{k-1}x^{k-1} - \cdots - r_{1}x - r_{0} \nonumber \]

factors completely as

\[p(x) = (x - \lambda_1)^{m_1}(x-\lambda_2)^{m_2} \cdots (x - \lambda_p)^{m_p} \nonumber \]

where \(\lambda_{1}, \lambda_{2}, \dots, \lambda_{p}\) are distinct real numbers and each \(m_{i} \geq 1\). Then \(\lambda_{i} \neq 0\) for each \(i\), and

\[\def\arraystretch{1.5} \begin{array}{c} \left[\lambda_{1}^{n}\right), \left[n\lambda_{1}^{n}\right), \dots, \left[n^{m_{1}-1}\lambda_{1}^{n}\right) \\ \left[\lambda_{2}^{n}\right), \left[n\lambda_{2}^{n}\right), \dots, \left[n^{m_{2}-1}\lambda_{2}^{n}\right) \\ \vdots \\ \left[\lambda_{p}^{n}\right), \left[n\lambda_{p}^{n}\right), \dots, \left[n^{m_{p}-1}\lambda_{p}^{n}\right) \end{array} \nonumber \]

is a basis of \(V\).

Proof

There are \(m_{1} + m_{2} + \cdots + m_{p} = k\) sequences in all so, because \(dim \;V = k\), it suffices to show that they are linearly independent. The assumption that \(r_{0} \neq 0\), implies that \(0\) is not a root of \(p(x)\). Hence each \(\lambda_{i} \neq 0\), so \(\{[\lambda_i^n), [n\lambda_i^n), \dots, [n^{m_i-1}\lambda_i^n)\}\) is linearly independent by Theorem 7.5.3. The proof that the whole set of sequences is linearly independent is omitted.

\(\square\)

Example \(\PageIndex{4}\)

Find a basis for the space \(V\) of all sequences \([x_{n})\) satisfying

\[x_{n+3} = -9x_n - 3x_{n+1} + 5x_{n+2} \nonumber \]

Solution

The associated polynomial is

\[p(x) = x^3 - 5x^2 + 3x + 9 = (x - 3)^2(x + 1) \nonumber \]

Hence \(3\) is a double root, so \([3_{n})\) and \([n3^{n})\) both lie in \(V\) by Theorem \(\PageIndex{4}\)

Remark 1

If \(r_{0} = 0\) [so \(p(x)\) has \(0\) as a root], the recurrence reduces to one of shorter length. For example, consider

\[\label{eq:7_5remark1Eq} x_{n+4} = 0x_n + 0x_{n+1} + 3x_{n+2} + 2x_{n+3} \]

If we set \(y_{n} = x_{n+2}\), this recurrence becomes \(y_{n+2} = 3y_{n} + 2y_{n+1}\), which has solutions \([3^{n})\) and \([(-1)^{n})\). These give the following solution to (\ref{eq:linRecurrRel}):

\[\def\arraystretch{1.5} \begin{array}{l} \left[0, 0, 1, 3, 3^2, \dots\right) \\ \left[0, 0, 1, -1, (-1)^2, \dots\right) \end{array} \nonumber \]

In addition, it is easy to verify that

\[\def\arraystretch{1.5} \begin{array}{l} \left[1, 0, 0, 0, 0, \dots\right) \\ \left[0, 1, 0, 0, 0, \dots\right) \end{array} \nonumber \]

are also solutions to (\ref{eq:7_5remark1Eq}). The space of all solutions of (\ref{eq:linRecurrRel}) has dimension \(4\) (Theorem 7.5.1), so these sequences are a basis. This technique works whenever \(r_{0} = 0\).

Remark 2

Theorem 7.5.4 completely describes the space \(V\) of sequences that satisfy a linear recurrence relation for which the associated polynomial \(p(x)\) has all real roots. However, in many cases of interest, \(p(x)\) has complex roots that are not real. If \(p(\mu) = 0\), \(\mu\) complex, then \(p(\overline{\mu}) = 0\) too (\(\overline{\mu}\) the conjugate), and the main observation is that \([\mu^n + \overline{\mu}^n)\) and \([i(\mu^n + \overline{\mu}^n))\) are real solutions. Analogs of the preceding theorems can then be proved.