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!
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\} $.
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:
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 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:
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.
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.