The selection of a linear recurrent sequence over the field is LRS too

A Linear recurrent sequence is $u_{i+m} = a_{m-1}u_{i+m-1} + a_{m-2}u_{i+m-2} + ... + a_1u_{i+1} + a_0u_i$, where m is the order of sequence and $a_i$ is integer.

The selection of a linear recurrent sequence is the sequence $v_i=u_{l+di}, i \ge 0$, where $d$ is $u$-sequence step and $l$ is $u$-sequence starting point. So, it is $(l, d)$-selection.

Prove that if $u$ is a linear recurrent sequence (or LRS) over the field P, $v$ is a LRS over the field P too.

Please write in detail!

• There is a really nice proof using the Cayley-Hamilton theorem. Idea: Let $A$ be the $m\times m$-matrix $\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ a_0 & a_1 & a_2 & \cdots & a_{m-1} \end{pmatrix}$. (This is the $m\times m$-matrix whose last row is $\left(a_0,a_1,\ldots,a_{m-1}\right)$, while its first $m-1$ columns have $1$'s in all cells $\left(i,i+1\right)$ and $0$'s in all other cells.) Now, argue (by induction on $j$) that ... – darij grinberg May 13 '18 at 19:18
• ... each $j\geq 0$ satisfies $A^j \begin{pmatrix} u_0 \\ u_1 \\ \vdots \\ u_{m-1} \end{pmatrix} = \begin{pmatrix} u_j \\ u_{j+1} \\ \vdots \\ u_{j+m-1} \end{pmatrix}$. Hence, each $v_i$ is the $1$-st coordinate of the vector $A^{l+di} \begin{pmatrix} u_0 \\ u_1 \\ \vdots \\ u_{m-1} \end{pmatrix}$. Thus, it suffices to prove that the sequence $\left(A^{l+d0}, A^{l+d1}, A^{l+d2}, \ldots\right)$ is an LRS (this is well-defined, even though it is a sequence of matrices, not of numbers). But this follows from the Cayley-Hamilton theorem applied to the matrix $A^d$. Anyone has time to flesh it out? – darij grinberg May 13 '18 at 19:21
• @darijgrinberg Your ideas are very good! But could you give links to the sites (or books), where I can read complete proofs of my approval and the Cayley-Hamilton theorem? Or I would be very grateful if you could write down the proof of my statement here in detail. – alexhak May 13 '18 at 19:45
• For Cayley-Hamilton itself, see the many references given in my note The trace Cayley-Hamilton theorem (currently in the paragraph under Theorem 2.6), and the note itself. You only need the (famous) Cayley-Hamilton theorem, not the (less well-known) trace Cayley-Hamilton theorem. As for its use... I hope to have more time in the next few days. – darij grinberg May 13 '18 at 19:50
• This has previously been discussed at math.stackexchange.com/questions/1777724/… too. – darij grinberg Jun 26 '18 at 11:38

Here is the proof I alluded to in the comments. I will work in a much more general setting.

Fix a commutative ring $$\mathbb{K}$$. As usual, $$\mathbb{N}$$ shall denote the set $$\left\{ 0,1,2,\ldots\right\}$$.

Theorem 1. Let $$d\in\mathbb{N}$$. Let $$m\in\mathbb{N}$$. Let $$a_{1} ,a_{2},\ldots,a_{m}$$ be $$m$$ elements of $$\mathbb{K}$$. Then, there exist $$m$$ elements $$b_{1},b_{2},\ldots,b_{m}$$ of $$\mathbb{K}$$ with the following property: If $$\left( u_{0},u_{1},u_{2},\ldots\right)$$ is any sequence of elements of $$\mathbb{K}$$ such that $$\begin{equation} \left( u_{i}=a_{1}u_{i-1}+a_{2}u_{i-2}+\cdots+a_{m}u_{i-m}\text{ for all }i\geq m\right) , \end{equation}$$ then this sequence also satisfies $$\begin{equation} \left( u_{i}=b_{1}u_{i-1d}+b_{2}u_{i-2d}+\cdots+b_{m}u_{i-md}\text{ for all }i\geq dm\right) . \end{equation}$$

Note that my $$a_{1},a_{2},\ldots,a_{m}$$ correspond to your $$a_{m-1} ,a_{m-2},\ldots,a_{0}$$. Note also that I'm not talking about a single $$\left( l,d\right)$$-selection but rather claiming a general linear recurrence that expresses each $$u_{i}$$ in terms of $$u_{i-1d},u_{i-2d},\ldots,u_{i-md}$$ (no matter what remainder $$i$$ leaves when divided by $$d$$); so, in your language, I'm saying that the $$\left( l,d\right)$$-selections for all $$l\in\mathbb{Z}$$ satisfy one and the same linear recurrence (for fixed $$d$$). Finally, the $$b_{1},b_{2},\ldots,b_{m}$$ in Theorem 1 depend only on $$\mathbb{K}$$, $$d$$ and $$a_{1},a_{2},\ldots,a_{m}$$, but not on the sequence $$\left( u_{0},u_{1} ,u_{2},\ldots\right)$$.

The proof of Theorem 1 will rely on the Cayley-Hamilton theorem for matrices. Let me recall what it says; but first I will need some notations. For any $$n\in\mathbb{N}$$, we let $$I_{n}$$ denote the $$n\times n$$ identity matrix in $$\mathbb{K}^{n\times n}$$, and we let $$0_{n\times n}$$ denote the zero matrix in $$\mathbb{K}^{n\times n}$$. The ring $$\mathbb{K}$$ is canonically embedded into the polynomial ring $$\mathbb{K}\left[ t\right]$$; thus, any matrix over $$\mathbb{K}$$ can be regarded as a matrix over $$\mathbb{K}\left[ t\right]$$. If $$A\in\mathbb{K}^{n\times n}$$ is any $$n\times n$$-matrix, then the characteristic polynomial $$\chi_{A}$$ of $$A$$ is defined to be the polynomial $$\det\left( tI_{n}-A\right) \in\mathbb{K}\left[ t\right]$$; here, $$tI_{n}-A$$ is a matrix in $$\left( \mathbb{K}\left[ t\right] \right) ^{n\times n}$$ (that is, a matrix whose entries are polynomials in $$\mathbb{K}\left[ t\right]$$). We shall use the following facts:

Theorem 2. Let $$A\in\mathbb{K}^{n\times n}$$ be any $$n\times n$$-matrix.

(a) The polynomial $$\chi_{A}\in\mathbb{K}\left[ t\right]$$ is monic of degree $$n$$.

(b) We have $$\chi_{A}\left( A\right) =0_{n\times n}$$.

Here, $$\chi_{A}\left( A\right)$$ denotes the result of substituting $$A$$ for $$t$$ in $$\chi_{A}$$.

Theorem 2 can be found in any good textbook on linear algebra. In my note The trace Cayley-Hamilton theorem, Theorem 2 (a) appears as Corollary 2.4, and Theorem 2 (b) as Theorem 2.5. Theorem 2 (b) is known as the Cayley-Hamilton theorem.

Now, let us prepare for the proof of Theorem 1. Let $$m\in\mathbb{N}$$. Let $$a_{1},a_{2},\ldots,a_{m}$$ be $$m$$ elements of $$\mathbb{K}$$. Let $$A$$ be the $$m\times m$$-matrix $$\begin{equation} \begin{pmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 1\\ a_{m} & a_{m-1} & a_{m-2} & \cdots & a_{1} \end{pmatrix} . \end{equation}$$ Rigorously speaking, this is the $$m\times m$$-matrix whose $$\left( i,j\right)$$-th entry is $$\begin{equation} \begin{cases} a_{m+1-j}, & \text{if }i=m;\\ 1, & \text{if }j=i+1;\\ 0, & \text{otherwise} \end{cases} \end{equation}$$ for all $$i\in\left\{ 1,2,\ldots,m\right\}$$ and $$j\in\left\{ 1,2,\ldots ,m\right\}$$.

Now, consider the characteristic polynomial $$\chi_{A^{d}}$$ of the $$m\times m$$-matrix $$A^{d}$$. Theorem 2 (a) (applied to $$m$$ and $$A^{d}$$ instead of $$n$$ and $$A$$) shows that the polynomial $$\chi_{A^{d}}\in\mathbb{K}\left[ t\right]$$ is monic of degree $$m$$. Thus, we can write $$\chi_{A^{d}}$$ in the form $$\begin{equation} \chi_{A^{d}}=t^{m}+c_{m-1}t^{m-1}+c_{m-2}t^{m-2}+\cdots+c_{0}t^{0} \end{equation}$$ for some $$c_{0},c_{1},\ldots,c_{m-1}\in\mathbb{K}$$. Consider these $$c_{0},c_{1},\ldots,c_{m-1}$$. Define $$m$$ further elements $$b_{1},b_{2} ,\ldots,b_{m}$$ of $$\mathbb{K}$$ by setting $$\begin{equation} \left( b_{i}=-c_{m-i}\text{ for each }i\in\left\{1,2,\ldots,m\right\} \right) . \end{equation}$$ We now claim the following:

Theorem 3. Let $$\left( u_{0},u_{1},u_{2},\ldots\right)$$ be any sequence of elements of $$\mathbb{K}$$ such that $$\begin{equation} \left( u_{i}=a_{1}u_{i-1}+a_{2}u_{i-2}+\cdots+a_{m}u_{i-m}\text{ for all }i\geq m\right) . \end{equation}$$ Then, this sequence also satisfies $$\begin{equation} \left( u_{i}=b_{1}u_{i-1d}+b_{2}u_{i-2d}+\cdots+b_{m}u_{i-md}\text{ for all }i\geq dm\right) . \end{equation}$$

Theorem 3 makes Theorem 1 explicit: It specifies what the right $$b_{1} ,b_{2},\ldots,b_{m}$$ are. All we need is to prove Theorem 3 now.

Before we prove it, we start with a simple lemma:

Lemma 4. Let $$\left( u_{0},u_{1},u_{2},\ldots\right)$$ be as in Theorem 3. Let $$j\in\mathbb{N}$$. Then, $$\begin{equation} A\begin{pmatrix} u_{j}\\ u_{j+1}\\ \vdots\\ u_{j+m-1} \end{pmatrix} = \begin{pmatrix} u_{j+1}\\ u_{j+2}\\ \vdots\\ u_{j+m} \end{pmatrix} . \end{equation}$$

Proof of Lemma 4. Recall that $$u_{i}=a_{1}u_{i-1}+a_{2}u_{i-2}+\cdots +a_{m}u_{i-m}$$ for all $$i\geq m$$. Applying this to $$i=j+m$$, we obtain \begin{align*} u_{j+m} & =a_{1}u_{j+m-1}+a_{2}u_{j+m-2}+\cdots+a_{m}u_{j+m-m}\\ & =a_{m}u_{j+m-m}+a_{m-1}u_{j+m-\left( m-1\right) }+\cdots+a_{1}u_{j+m-1}\\ & =a_{m}u_{j}+a_{m-1}u_{j+1}+\cdots+a_{1}u_{j+m-1}. \end{align*}

But recall that $$A= \begin{pmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 1\\ a_{m} & a_{m-1} & a_{m-2} & \cdots & a_{1} \end{pmatrix}$$. Thus, \begin{align*} A \begin{pmatrix} u_{j}\\ u_{j+1}\\ \vdots\\ u_{j+m-1} \end{pmatrix} & = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 1\\ a_{m} & a_{m-1} & a_{m-2} & \cdots & a_{1} \end{pmatrix} \begin{pmatrix} u_{j}\\ u_{j+1}\\ \vdots\\ u_{j+m-1} \end{pmatrix} \\ & = \begin{pmatrix} u_{j+1}\\ u_{j+2}\\ \vdots\\ u_{j+m-1}\\ a_{m}u_{j}+a_{m-1}u_{j+1}+\cdots+a_{1}u_{j+m-1} \end{pmatrix} = \begin{pmatrix} u_{j+1}\\ u_{j+2}\\ \vdots\\ u_{j+m-1}\\ u_{j+m} \end{pmatrix} \\ & \qquad\left( \text{since }a_{m}u_{j}+a_{m-1}u_{j+1}+\cdots+a_{1} u_{j+m-1}=u_{j+m}\right) \\ & = \begin{pmatrix} u_{j+1}\\ u_{j+2}\\ \vdots\\ u_{j+m} \end{pmatrix} . \end{align*} This proves Lemma 4.

Lemma 5. Let $$\left( u_{0},u_{1},u_{2},\ldots\right)$$ be as in Theorem 3. Let $$\mathbf{u}$$ be the vector $$\begin{pmatrix} u_{0}\\ u_{1}\\ \vdots\\ u_{m-1} \end{pmatrix} \in\mathbb{K}^{m}$$. Let $$j\in\mathbb{N}$$. Then, $$\begin{equation} A^{j}\mathbf{u}= \begin{pmatrix} u_{j}\\ u_{j+1}\\ \vdots\\ u_{j+m-1} \end{pmatrix} . \end{equation}$$

Proof of Lemma 5. We shall prove Lemma 5 by induction on $$j$$:

Induction base: We have $$\begin{equation} \underbrace{A^{0}}_{=I_{m}}\mathbf{u}=I_{m}\mathbf{u}=\mathbf{u}= \begin{pmatrix} u_{0}\\ u_{1}\\ \vdots\\ u_{m-1} \end{pmatrix} = \begin{pmatrix} u_{0}\\ u_{0+1}\\ \vdots\\ u_{0+m-1} \end{pmatrix} . \end{equation}$$ In other words, Lemma 5 holds for $$j=0$$. This completes the induction base.

Induction step: Let $$i\in\mathbb{N}$$ be arbitrary. Assume that Lemma 5 holds for $$j=i$$. We must now prove that Lemma 5 holds for $$j=i+1$$.

We have assumed that Lemma 5 holds for $$j=i$$. In other words, we have $$\begin{equation} A^{i}\mathbf{u}= \begin{pmatrix} u_{i}\\ u_{i+1}\\ \vdots\\ u_{i+m-1} \end{pmatrix} . \end{equation}$$ Now, \begin{align*} \underbrace{A^{i+1}}_{=AA^{i}}\mathbf{u} & =A\underbrace{A^{i}\mathbf{u} }_{= \begin{pmatrix} u_{i}\\ u_{i+1}\\ \vdots\\ u_{i+m-1} \end{pmatrix} }=A \begin{pmatrix} u_{i}\\ u_{i+1}\\ \vdots\\ u_{i+m-1} \end{pmatrix} = \begin{pmatrix} u_{i+1}\\ u_{i+2}\\ \vdots\\ u_{i+m} \end{pmatrix} \\ & \ \ \ \ \ \ \ \ \ \ \left( \text{by Lemma 4, applied to }j=i\right) \\ & = \begin{pmatrix} u_{i+1}\\ u_{\left( i+1\right) +1}\\ \vdots\\ u_{\left( i+1\right) +m-1} \end{pmatrix} . \end{align*} In other words, Lemma 5 holds for $$j=i+1$$. This completes the induction step. Thus, Lemma 5 is proven by induction.

Proof of Theorem 3. Theorem 2 (b) (applied to $$m$$ and $$A^{d}$$ instead of $$n$$ and $$A$$) shows that $$\chi_{A^{d}}\left( A^{d}\right) =0_{m\times m}$$.

But \begin{align*} \chi_{A^{d}} & =t^{m}+\underbrace{c_{m-1}t^{m-1}+c_{m-2}t^{m-2}+\cdots +c_{0}t^{0}}_{\substack{=\sum\limits_{i=0}^{m-1}c_{i}t^{m-i}=\sum \limits_{j=1}^{m}c_{m-j}t^{m-j}\\\text{(here, we have substituted }m-j\text{ for }i\text{ in the sum)}}}\\ & =t^{m}+\sum\limits_{j=1}^{m}\underbrace{c_{m-j}}_{\substack{=-b_{j} \\\text{(since }b_{j}=-c_{m-j}\\\text{(by the definition of }b_{j}\text{))} }}t^{m-j}=t^{m}+\sum\limits_{j=1}^{m}\left( -b_{j}\right) t^{m-j}=t^{m} -\sum\limits_{j=1}^{m}b_{j}t^{m-j}. \end{align*} Substituting $$A^{d}$$ for $$t$$ on both sides of this equality, we find $$\begin{equation} \chi_{A^{d}}\left( A^{d}\right) =\underbrace{\left( A^{d}\right) ^{m} }_{=A^{dm}=A^{md}}-\sum\limits_{j=1}^{m}b_{j}\underbrace{\left( A^{d}\right) ^{m-j}}_{=A^{d\left( m-j\right) }=A^{\left( m-j\right) d}}=A^{md} -\sum\limits_{j=1}^{m}b_{j}A^{\left( m-j\right) d}. \end{equation}$$ Comparing this with $$\chi_{A^{d}}\left( A^{d}\right) =0_{m\times m}$$, we obtain $$\begin{equation} 0_{m\times m}=A^{md}-\sum\limits_{j=1}^{m}b_{j}A^{\left( m-j\right) d}. \end{equation}$$ In other words, $$\begin{equation} A^{md}=\sum\limits_{j=1}^{m}b_{j}A^{\left( m-j\right) d}. \label{pf.t3.5} \tag{1} \end{equation}$$

Now, let $$i$$ be an integer such that $$i\geq dm$$. We must prove that $$u_{i}=b_{1}u_{i-1d}+b_{2}u_{i-2d}+\cdots+b_{m}u_{i-md}$$.

The matrix $$A^{i-md}$$ is well-defined (since $$i\geq dm=md$$). Multiplying both sides of the equality \eqref{pf.t3.5} by $$A^{i-md}\mathbf{u}$$ on the right, we obtain \begin{align*} A^{md}A^{i-md}\mathbf{u} & =\left( \sum\limits_{j=1}^{m}b_{j}A^{\left( m-j\right) d}\right) A^{i-md}\mathbf{u}=\sum\limits_{j=1}^{m}b_{j} \underbrace{A^{\left( m-j\right) d}A^{i-md}}_{\substack{=A^{\left( m-j\right) d+i-md}=A^{i-jd}\\\text{(since }\left( m-j\right) d+i-md=i-jd\text{)}}}\mathbf{u}\\ & =\sum\limits_{j=1}^{m}b_{j}\underbrace{A^{i-jd}\mathbf{u}} _{\substack{= \begin{pmatrix} u_{i-jd}\\ u_{i-jd+1}\\ \vdots\\ u_{i-jd+m-1} \end{pmatrix} \\\text{(by Lemma 5, applied to }i-jd\\\text{instead of }j\text{)} }}=\sum\limits_{j=1}^{m}b_{j} \begin{pmatrix} u_{i-jd}\\ u_{i-jd+1}\\ \vdots\\ u_{i-jd+m-1} \end{pmatrix} = \begin{pmatrix} \sum\limits_{j=1}^{m}b_{j}u_{i-jd}\\ \sum\limits_{j=1}^{m}b_{j}u_{i-jd+1}\\ \vdots\\ \sum\limits_{j=1}^{m}b_{j}u_{i-jd+m-1} \end{pmatrix} . \end{align*} Comparing this with $$\begin{equation} \underbrace{A^{md}A^{i-md}}_{=A^{md+\left( i-md\right) }=A^{i}} \mathbf{u}=A^{i}\mathbf{u}= \begin{pmatrix} u_{i}\\ u_{i+1}\\ \vdots\\ u_{i+m-1} \end{pmatrix} \ \ \ \ \ \ \ \ \ \ \left( \text{by Lemma 5, applied to }i\text{ instead of }j\right) , \end{equation}$$ we obtain $$\begin{equation} \begin{pmatrix} u_{i}\\ u_{i+1}\\ \vdots\\ u_{i+m-1} \end{pmatrix} = \begin{pmatrix} \sum\limits_{j=1}^{m}b_{j}u_{i-jd}\\ \sum\limits_{j=1}^{m}b_{j}u_{i-jd+1}\\ \vdots\\ \sum\limits_{j=1}^{m}b_{j}u_{i-jd+m-1} \end{pmatrix} . \end{equation}$$ This is an equality between two vectors in $$\mathbb{K}^{m}$$. Comparing the first coordinates of these vectors in this equality, we obtain $$\begin{equation} u_{i}=\sum\limits_{j=1}^{m}b_{j}u_{i-jd}=b_{1}u_{i-1d}+b_{2}u_{i-2d} +\cdots+b_{m}u_{i-md}. \end{equation}$$ Thus, $$u_{i}=b_{1}u_{i-1d}+b_{2}u_{i-2d}+\cdots+b_{m}u_{i-md}$$ is proven. This proves Theorem 3.

As mentioned above, Theorem 1 follows immediately from Theorem 3.