1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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 ... $\endgroup$ – darij grinberg May 13 '18 at 19:18
  • 1
    $\begingroup$ ... 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? $\endgroup$ – darij grinberg May 13 '18 at 19:21
  • $\begingroup$ @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. $\endgroup$ – alexhak May 13 '18 at 19:45
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg May 13 '18 at 19:50
  • $\begingroup$ This has previously been discussed at math.stackexchange.com/questions/1777724/… too. $\endgroup$ – darij grinberg Jun 26 '18 at 11:38
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.