\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Impulse Response Sequences and \\ \vskip .1in Construction of Number Sequence Identities } \vskip 1cm \large Tian-Xiao He\\ Department of Mathematics \\ Illinois Wesleyan University\\ Bloomington, IL 61702-2900 \\ USA\\ \href{mailto:the@iwu.edu}{\tt the@iwu.edu} \\ \end{center} \vskip .2 in \begin{abstract} In this paper, we investigate impulse response sequences over the integers by presenting their generating functions and expressions. We also establish some of the corresponding identities. In addition, we give the relationship between an impulse response sequence and all linear recurring sequences satisfying the same linear recurrence relation, which can be used to transfer the identities among different sequences. Finally, we discuss some applications of impulse response sequences to the structure of Stirling numbers of the second kind, the Wythoff array, and the Boustrophedon transform. \end{abstract} \vskip .2in \newcommand\be{\begin{equation}} \newcommand\ee{\end{equation}} \newcommand\bn{\begin{eqnarray}} \newcommand\en{\end{eqnarray}} \newcommand\bns{\begin{eqnarray*}} \newcommand\ens{\end{eqnarray*}} \newcommand\bC{{\mathbb C}} \newcommand\bR{{\mathbb R}} \newcommand\bN{{\mathbb N}} \newcommand\bZ{{\mathbb Z}} \section{Introduction} Many number and polynomial sequences can be defined, characterized, evaluated, and classified by linear recurrence relations with certain orders. A number sequence $\{ a_n\}$ is called a sequence of order $r$ if it satisfies the linear recurrence relation of order $r$ \begin{equation}\label{eq:1} a_n= \sum^r_{j=1}p_j a_{n-j}, \quad n\geq r, \end{equation} for some constants $p_j$, $j=1,2,\ldots, r$, $p_r\not= 0$, and initial conditions $a_j$ $(j=0,1,\ldots, r-1)$. Linear recurrence relations with constant coefficients are important in subjects including combinatorics, pseudo-random number generation, circuit design, and cryptography, and they have been studied extensively. To construct an explicit formula of the general term of a number sequence of order $r$, one may use a generating function, a characteristic equation, or a matrix method (See Comtet \cite{Com}, Niven, Zuckerman, and Montgomery \cite{NZM}, Strang \cite{Str}, Wilf \cite{Wilf}, etc.) Let $A_{r}$ be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:1}) with coefficient set $E_{r}=\{ p_{1}, p_{2}, \ldots, p_r\}$. To study the structure of $A_r$ with respect to $E_r$, we consider the {\it impulse response sequence} (or, {\it IRS} for abbreviation) in $A_r$, which is a particular sequence in $A_r$ with initials $a_0=a_1=\cdots =a_{r-2}=0$ and $a_{r-1}=1$. The study of impulse response sequences in a finite field has been considerably active in the theory of finite fields. A summary work on this subject can be found in Lidl and Niederreiter \cite{LN}. In this paper, we investigate the same concept in ${\bZ}$. If $r=2$, the IRS in ${\bZ}$ is the well known {\it Lucas sequence}. In this sense, an IRS of order $r>2$ is an extension of a Lucas sequence in a high order setting. In the next section, we will give the generating function and the expression of the IRS of $A_r$ and find out the relationship between the IRS and other sequences in the set $A_r$. Several examples of IRS in sets $A_2$ and $A_3$ will be given in Section $3$. The work shown in Sections $2$ and $3$ is partially motivated by Shiue and the author \cite{HS}, which presented a method for the construction of general term expressions and identities for the linear recurring sequences of order $r=2$ by using the reduction order method. However, the reduction method is too complicated for the linear recurring sequences of order $r>2$, although our method can be applied readily to linear recurring sequences with arbitrary order by using their relationship with impulse response sequences. In Section $4$, we shall give some applications of IRS in the discussion of the structure of {\it Stirling numbers of the second kind}, the {\it Wythoff array}, and the {\it Boustrophedon transform}. \section{Impulse response sequences} Among all the homogeneous linear recurring sequences satisfying $r$th order homogeneous linear recurrence relation (\ref{eq:1}) with a nonzero $p_{r}$ and arbitrary initial conditions $\{ a_{j}\}^{r-1}_{j=0}$, we define the impulse response sequence (IRS) with respect to $E_{r}=\{ p_{j}\}^{r}_{j=1}$ as the sequence with initial conditions $a_{0}=a_{r-2}=0$ and $a_{r-1}=1$. In particular, when $r=2$, the homogeneous linear recurring sequences with respect to $E_{2}=\{ p_{1}, p_{2}\}$ satisfy \be\label{eq:5.1} a_n= p_{1}a_{n-1}+p_{2} a_{n-2}, \quad n\geq 2, \ee with arbitrary initial conditions $a_{0}$ and $a_{1}$, or, initial vector $(a_0, a_1)$. If the initial vector $(a_{0}, a_{1})=(0,1)$, the corresponding sequence generated by using (\ref{eq:5.1}) is the IRS with respect to $E_{2}$, is called the Lucas sequence. For instance, the {\it Fibonacci sequence} $\{ F_{n}\}$ is the IRS with respect to $\{ 1,1\}$, the {\it Pell number sequence} $\{ P_{n}\}$ is the IRS with respect to $\{ 2,1\}$, and the {\it Jacobsthal number sequence} $\{ J_n\}$ is the IRS with respect to $\{1,2\}$. In the following, we will present the structure of the linear recurring sequences defined by (\ref{eq:1}) using their characteristic polynomial. This structure provides a way to find the relationship between those sequences and the IRS. Let $A_{r}$ be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:1}) with coefficient set $E_{r}=\{ p_{1}, p_{2}, \ldots, p_r\}$, and let $\tilde F^{( r)}_{n}$ be the IRS of $A_{r}$, namely, $\tilde F^{(r)}_n$ satisfies (\ref{eq:1}) with initial conditions $\tilde F^{(r)}_0=\cdots =\tilde F^{(r)}_{r-2}=0$ and $\tilde F^{(r)}_{r-1}=1$. Suppose $\{ a_n\}\in A_r$. Let $B=|p_1|+|p_2|+\cdots +|p_r|$, and for $n\in {\bN}_0$ let $M_n=\max\{ |a_0|, |a_1|, \ldots, |a_n|\}$. Thus, for $n\geq r$, $M_n\leq BM_{n-1}$. By induction, $|a_n|\leq C B^n$ for some constant $A$ and $n=0,1,2,\ldots.$ A sequence satisfying a bound of this kind is called a sequence having at most {\it exponential growth} (see \cite{NZM}). Therefore, the generating function $\sum_{j\geq 0} a_j t^j$ of such sequence has a positive radius of convergence, $0< c< 1/B$. More precisely, if $|t|\leq c$, then by comparison with the convergent geometric series $\sum_{j\geq 0} CB^j c^j$, the series $\sum_{j\geq 0} a_j t^j$ converges absolutely. In the following, we always assume that $\{ a_n\}$ has at most exponential growth. \begin{proposition}\label{pro:3.1} Let $\{ a_{n}\}\in A_{r}$, i.e., let $\{ a_{n}\}$ be the linear recurring sequence defined by (\ref{eq:1}). Then its generating function $P_r(t)$ can be written as \be\label{eq:3.1} P_r(t)=\{ a_{0}+\sum^{r-1}_{n=1}\left( a_{n}-\sum^{n}_{j=1}p_{j}a_{n-j}\right)t^{n}\}/\{1-\sum^{r}_{j=1}p_{j}t^{j}\}. \ee Hence, the generating function for the IRS with respect to $\{ p_j\}$ is \be\label{eq:3.2} \tilde P_r(t)=\frac{ t^{r-1}}{1-\sum^{r}_{j=1}p_{j}t^{j}}. \ee \end{proposition} \begin{proof} Multiplying $t^{n}$ on the both sides of (\ref{eq:1}) and summing from $n=r$ to infinity yields \bns &&\sum_{n\geq r}a_{n}t^{n}=\sum_{n\geq r}\sum^{r}_{j=1}p_{j}a_{n-j}t^{n}=\sum^{r}_{j=1}p_{j}\sum_{n\geq r}a_{n-j}t^{n}\\ &=&\sum^{r-1}_{j=1}p_{j}\left( \sum_{n\geq j}a_{n-j}t^{n}-\sum^{r-1}_{n=j}a_{n-j}t^{n}\right) +p_{r}\sum_{n\geq r}a_{n-r}t^{n}\\ &=&\sum^{r-1}_{j=1}p_{j}\left( t^{j}\sum_{n\geq 0}a_{n}t^{n}-\sum^{r-1}_{n=j}a_{n-j}t^{n}\right) +p_{r}t^{r}\sum_{n\geq 0}a_{n}t^{n}\\ \ens Denote $P_r(t)=\sum_{n\geq 0}a_{n}t^{n}$. Then the equation of the leftmost and the rightmost sides can be written as \[ P_r(t)-\sum^{r-1}_{n=0}a_{n}t^{n}=P_r(t)\sum^{r-1}_{j=1}p_{j}t^{j} -\sum^{r-1}_{j=1}\sum^{r-1}_{n=j}p_{j}a_{n-j}t^{n}+p_{r}t^{r}P_r(t), \] which implies \[ P_r(t)\left( 1-\sum^{r}_{j=1}p_{j}t^{j}\right)=\sum^{r-1}_{n=0}a_{n}t^{n}-\sum^{r-1}_{n=1}\sum^{n}_{j=1}p_{j}a_{n-j}t^{n}. \] Therefore, (\ref{eq:3.2}) follows immediately. By substituting $a_{0}=\cdots =a_{r-2}=0$ and $a_{r-1}=1$ into (\ref{eq:3.1}), we obtain (\ref{eq:3.2}). \end{proof} We now give the explicit expression of $\tilde F^{(r)}_n$ in terms of the zeros of the characteristic polynomial of recurrence relation shown in (\ref{eq:1}). \begin{theorem}\label{thm:1.3} Sequence $\{\tilde F^{(r)}_n\}_n$ is the IRS with respect to $\{p_j\}$ defined by (\ref{eq:1}) with $\tilde F^{( r)}_{0}=\tilde F^{( r)}_{1}=\cdots =\tilde F^{( r)}_{r-2}=0$ ane $\tilde F^{(r)}_{r-1}=1$ if and only if \be\label{eq:5.7} \tilde F^{(r)}_n =\sum^\ell_{j=1}\frac {{n\choose m_j-1}\alpha^{n-m_j+1}_j}{\prod^\ell_{k=1, k\not= j}(\alpha_j-\alpha_k)} \ee for $n\geq r$, where $\alpha_1,\alpha_2,\ldots, \alpha_\ell$ are the distinct real or complex zeros of characteristic polynomial, $p(t)=t^r-p_1t^{r-1}-\cdots -p_r$, of the recurrence relation (\ref{eq:1}) with the multiplicities $m_1,m_2,\ldots, m_\ell$, respectively, and $m_1+m_2+\cdots +m_\ell=r$. In particular, if all $\alpha_1,\alpha_2, \ldots$, $\alpha_r$ are of multiplicity one, then (\ref{eq:5.7}) becomes to \be\label{eq:5.7.2} \tilde F^{(r)}_n=\sum^r_{j=1}\frac{\alpha^n_j}{\prod^r_{k=1,k\not= j} (\alpha_j-\alpha_k)}, \quad n\geq r, \ee \end{theorem} \begin{proof} First, we prove (\ref{eq:5.7.2}). Then we use it to prove the necessity of (\ref{eq:5.7}). Let $\alpha_{j}$, $j=1,2,\ldots,\ell$, be $\ell$ zeros of the characteristic polynomial $t^{n}-\sum^{r}_{i=1}p_{i}t^{n-i}$. Then from (\ref{eq:3.2}) \bn\label{eq:5.7.3} &&\tilde P_r(t)=\frac{t^{r-1}}{1-\sum^r_{j=1}p_j t^j}=\frac{1/t}{(1/t)^r-\sum^r_{j=1}p_j(1/t)^{n-j}}\nonumber \\ &=&\frac{1/t}{\prod^r_{j=1}(1/t-\alpha_j)}=\frac{t^{r-1}}{\prod^r_{j=1} (1-\alpha_j t)}. \en We now prove (\ref{eq:5.7.2}) from (\ref{eq:5.7.3}) by using mathematical induction for $r$ under the assumption that all solutions $\alpha_j$ are distinct. Because $[t^n]\tilde P_r(t)=\tilde F^{(r)}_n$, we need to show \be\label{eq:5.7.4} [t^n]\tilde P_r(t)=[t^n] \frac{t^{r-1}}{\prod^r_{j=1} (1-\alpha_j t)}=\sum^r_{j=1}\frac{\alpha^n_j}{\prod^r_{k=1,k\not= j} (\alpha_j-\alpha_k)}, \quad n\geq r. \ee (\ref{eq:5.7.4}) is obviously true for $r=1$. Assume (\ref{eq:5.7.4}) holds for $r=m$. We find \[ [t^n]\tilde P_{m+1}(t)=[t^n] \frac{t^{m}}{\prod^{m+1}_{j=1} (1-\alpha_j t)}, \] which implies \[ [t^n] (1-\alpha_{m+1}t)\tilde P_{m+1}(t)=[t^{n-1}] \frac{t^{m-1}}{\prod^{m}_{j=1} (1-\alpha_j t)} =\sum^m_{j=1}\frac{\alpha^{n-1}_j}{\prod^m_{k=1,k\not= j} (\alpha_j-\alpha_k)} \] because of the induction assumption. Noting $[t^n] \tilde P_{m+1}(t)=\tilde F^{(m+1)}_n$, from the last equations one may write \be\label{eq:5.7.5} \tilde F^{(m+1)}_n -\alpha_{m+1}\tilde F^{(m+1)}_{n-1}=\sum^m_{j=1}\frac{\alpha^{n-1}_j}{\prod^m_{k=1,k\not= j} (\alpha_j-\alpha_k)}, \ee which has the solution \be\label{eq:5.7.6} \tilde F^{(m+1)}_n= \sum^{m+1}_{j=1}\frac{\alpha^{n}_j}{\prod^{m+1}_{k=1,k\not= j} (\alpha_j-\alpha_k)}. \ee Indeed, we have \bns &&\alpha_{m+1}\tilde F^{(m+1)}_{n-1}+\sum^m_{j=1}\frac{\alpha^{n-1}_j}{\prod^m_{k=1,k\not= j} (\alpha_j-\alpha_k)}\\ &=&\alpha_{m+1}\sum^{m+1}_{j=1}\frac{\alpha^{n-1}_j}{\prod^{m+1}_{k=1,k\not= j} (\alpha_j-\alpha_k)}+\sum^m_{j=1}\frac{\alpha^{n-1}_j}{\prod^m_{k=1,k\not= j} (\alpha_j-\alpha_k)}\\ &=&\sum^m_{j=1}\frac{\alpha^{n-1}_j}{\prod^{m+1}_{k=1,k\not= j} (\alpha_j-\alpha_k)}\left( \alpha_{m+1}+\alpha_j-\alpha_{m+1}\right) +\frac{\alpha^{n}_{m+1}}{\prod^{m}_{k=1} (\alpha_{m+1}-\alpha_k)}\\ &=&\sum^{m+1}_{j=1}\frac{\alpha^{n}_j}{\prod^{m+1}_{k=1,k\not= j} (\alpha_j-\alpha_k)}=\tilde F^{(m+1)}_n, \ens and (\ref{eq:5.7.6}) is proved. To prove (\ref{eq:5.7}), it is sufficient to show it holds for the case of one multiple zero, say $\alpha_i$ with the multiplicity $m_i$. The formula of $\tilde F^{(r)}_n$ in this case can be derived from (\ref{eq:5.7.2}) by using the limit process. More precisely, let $m_i$ zeros of the characteristic polynomial, denoted by $\alpha_{i_j}$, $1\leq j\leq m_i$, approach $\alpha_i$. Then (\ref{eq:5.7.2}) will be reduced to the corresponding (\ref{eq:5.7}) with respect to $\alpha_i$. Indeed, taking the limit as $\alpha_{i_j}$, $1\leq j\leq m_i$, approaches $\alpha_i$ on both sides of (\ref{eq:5.7.2}), yields \bn &&\lim_{(\alpha_{i_1}, \ldots, \alpha_{i_{m_i}})\to (\alpha_i, \ldots, \alpha_i)}\tilde F^{(r)}_n\nonumber\\ &=&\frac{1}{\prod^{r-m_i+1}_{k=1,k\not= i}(\alpha_i-\alpha_k)}\lim_{(\alpha_{i_1}, \ldots, \alpha_{i_{m_i}})\to (\alpha_i, \ldots, \alpha_i)}\left( \frac{\alpha^n_{i_1}}{\prod^{m_i}_{k=2}(\alpha_{i_1}-\alpha_{i_k})}+\frac{\alpha^n_{i_2}}{\prod^{m_i}_{k=1,k\not=2}(\alpha_{i_2}-\alpha_{i_k})}\right.\nonumber\\ &&\qquad \quad \left. +\cdots+\frac{\alpha^n_{i_{m_i}}}{\prod^{m_i}_{k=1,k\not= m_i}(\alpha_{i_{m_i}}-\alpha_{i_k})}\right) +\sum^r_{j=1, j\not= i}\frac{\alpha^n_j}{\prod^r_{k=1,k\not= j} (\alpha_j-\alpha_k)}.\label{eq:5.7.7} \en It is obvious that the summation in the parentheses of equation (\ref{eq:5.7.7}) is the expansion of the {\it divided difference} of the function $f(t)=t^n$, denoted by $f[\alpha_{i_1},\alpha_{i_2},\ldots, \alpha_{i_{m_i}}]$, at nodes $\alpha_{i_1}, \alpha_{i_2},\ldots, \alpha_{i_{m_i}}$. Using the mean value theorem (see, for example, \cite{Rud}) for divided difference (see, for example, \cite[Thm.\ 3.6]{BF}), one may obtain \[ \lim_{(\alpha_{i_1}, \ldots, \alpha_{i_{m_i}})\to (\alpha_i, \ldots, \alpha_i)}f[\alpha_{i_1},\alpha_{i_2},\ldots, \alpha_{i_{m_i}}]=\frac{f^{(m_i-1)}(\alpha_i)}{(m_i-1)!}={n\choose {m_i-1}} \alpha^{n-m_i+1}_i. \] Therefore, by taking the limit as $\alpha_{i_j}\to \alpha_i$ for $1\leq j\leq m_i$ on both sides of (\ref{eq:5.7.7}), we obtain \[ \lim_{(\alpha_{i_1}, \ldots, \alpha_{i_{m_i}})\to (\alpha_i, \ldots, \alpha_i)}\tilde F^{(r)}_n= \frac{{n\choose {m_i-1}}\alpha_i^{n-m_1+1}}{\prod^{r-m_i+1}_{k=1,k\not= i}(\alpha_i-\alpha_k)}+ \sum^r_{j=1, j\not= i}\frac{\alpha^n_j}{\prod^r_{k=1,k\not= j} (\alpha_j-\alpha_k)}, \] which implies the correctness of (\ref{eq:5.7}) for the multiple zero $\alpha_i$ of multiplicity $m_i$. Therefore, (\ref{eq:5.7}) follows by taking the same argument for each multiple zero of the characteristic polynomial $P_r(t)$ shown in Proposition \ref{pro:3.1}. Finally, we prove sufficiency. For $n\geq r$, \bns &&\sum^{r}_{i=1}p_{i}\tilde F^{( r)}_{n-i}=\sum^\ell_{j=1}\frac{ \sum^{r}_{i=1}p_{i}{n\choose m_j-1}\alpha^{n-i-m_j+1}_j}{\prod^\ell_{k=1, k\not= j}(\alpha_j-\alpha_k)}\\ &=&\sum^\ell_{j=1}\frac{ {n\choose m_j-1}\alpha^{-m_j+1}_j\sum^{r}_{i=1}p_{i}\alpha^{n-i}_j}{\prod^\ell_{k=1, k\not= j}(\alpha_j-\alpha_k)}\\ &=&\sum^\ell_{j=1}\frac{ {n\choose m_j-1}\alpha^{n-m_j+1}_j}{\prod^\ell_{k=1, k\not= j}(\alpha_j-\alpha_k)}=\tilde F^{( r)}_{n}, \ens where we have used $\alpha_j^n=\sum^r_{i=1}p_i\alpha_j^{n-i}$ because of $p(\alpha_j)=0$. Therefore, the sequence $\{ \tilde F^{( r)}_{n}\}$ satisfies the linear recurrence relation (\ref{eq:1}) and is the IRS with respect to $\{p_j\}$. \end{proof} The IRS of a set of linear recurring sequences is a kind of basis so that every sequence in the set can be represented in terms of the IRS. For this purpose, we need to extend the indices of IRS $\tilde F^{(r)}_n$ of $A_r$ to the negative indices down to till $n=-r+1$, where $A_{r}$ is the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:1}) with coefficient set $E_{r}=\{ p_{1}, p_{2}, \ldots, p_r\}$, $p_r\not= 0$. For instance, $\tilde F^{(r)}_{-1}$ is defined by \[ \tilde F^{(r)}_{r-1}=p_1 \tilde F^{(r)}_{r-2} +p_2\tilde F^{(r)}_{r-3}+\cdots +p_r\tilde F^{(r)}_{-1}, \] which implies $\tilde F^{(r)}_{-1}=1/p_r$ because $\tilde F^{(r )}_0=\cdots =\tilde F^{(r)}_{r-2}=0$ and $\tilde F^{(r)}_{r-1}=1$. Similarly, we may use \[ \tilde F^{(r)}_{r+j}=p_1\tilde F^{(r)}_{r+j-1}+p_2\tilde F^{(r)}_{r+j-2}+\cdots +p_r\tilde F^{(r)}_{j} \] to define $\tilde F^{(r)}_j$, $j=-2,\ldots, -r+1$ successively. The following theorem shows how to represent linear recurring sequences in terms of the extended IRS $\{ \tilde F^{(r)}_n\}_{n\geq -r+1}$. \begin{theorem}\label{thm:1.4} Let $A_{r}$ be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:1}) with coefficient set $E_{r}=\{ p_{1}, p_{2}, \ldots, p_r\}$, $p_{r}\not= 0$, and let $\{\tilde F^{( r)}_{n}\}_{n\geq -r+1}$ be the (extended) IRS of $A_{r}$. Then, for any $a_n\in A_r$, one may write $a_n$ as \be\label{eq:5.8} a_n=a_{r-1}\tilde F^{(r)}_n+\sum^{r-2}_{j=0} \sum^{r-2}_{k=j} a_kp_{r+j-k}\tilde F^{(r)}_{n-1-j}. \ee \end{theorem} \begin{proof} Considering the sequences on the both sides of (\ref{eq:5.8}), we find that both sequences satisfy the same recurrence relation (\ref{eq:1}). Hence, to prove the equivalence of two sequences, we only need to show that they have the same initial vector $(a_0, a_1, \ldots, a_{r-1})$ because of the uniqueness of the linear recurring sequence defined by (\ref{eq:1}) with fixed initial conditions. First, for $n=r-1$, the conditions $\tilde F^{(r )}_0=\cdots =\tilde F^{(r)}_{r-2}=0$ and $\tilde F^{(r)}_{r-1}=1$ are applied on the right-hand side of (\ref{eq:5.8}) to obtain its value as $a_{r-1}$, which shows (\ref{eq:5.8}) holds for $n=r-1$. Secondly, for all $0\leq n\leq r-2$, one may write the right-hand side RHS of (\ref{eq:5.8}) as \[ RHS=0+\sum^{r-2}_{k=0} a_k \left( \sum^{k}_{j=0} p_{r+j-k}\tilde F^{(r)}_{n-1-j}\right) =\sum^{r-2}_{k=0}a_{k}\delta_{k,n}=a_{n}, \] where the Kronecker delta symbol $\delta_{k,n}$ is $1$ when $k=n$ and zero otherwise, and the following formula is used: \be\label{eq:5.8.2} \sum^{k}_{j=0} p_{r+j-k}\tilde F^{( r)}_{n-1-j}=\delta_{k,n}. \ee (\ref{eq:5.8.2}) can be proved by splitting it into three cases: $n=, >,$ and $< k$, respectively. If $n=k$, we have \bns &&\sum^{k}_{j=0} p_{r+j-k}\tilde F^{( r)}_{n-1-j}=\sum^{k}_{j=0} p_{r+j-k}\tilde F^{( r)}_{k-1-j}\\ &=&p_{r}\tilde F^{( r)}_{-1}+p_{r-1}\tilde F^{( r)}_{0}+p_{r-2}\tilde F^{( r)}_{1}+\cdots +p_{r-k}\tilde F^{( r)}_{k-1}\\ &=&p_{r}\tilde F^{( r)}_{-1}=1, \ens where we use $\tilde F^{( r)}_{-1}=1/p_{r}$ and the fact $\tilde F^{( r)}_{j}=0$ for all $j=0,1,\ldots, k-1$ due to $k-1\leq r-3$ and the initial values of $\tilde F^{( r)}_{n}$ being zero for all $0\leq n\leq r-2$. If $n>k$, we have \[ \sum^{k}_{j=0} p_{r+j-k}\tilde F^{( r)}_{n-1-j}=p_{r}\tilde F^{( r)}_{n-k-1}+p_{r-1}\tilde F^{( r)}_{n-k}+\cdots+p_{r-k}\tilde F^{( r)}_{n-1}=0 \] because $\tilde F^{( r)}_{j}=0$ for all $j=n-k-1, n-k, \ldots, n-1$ due to the definition of $\tilde F^{( r)}_{n}$ and the condition of $-12$, the corresponding IRS is a higher-order Fibonacci sequence. For instance, $\tilde F^{(3)}_n$, $\tilde F^{(4)}_n$, $\tilde F^{(5)}_n$, $\tilde F^{(6)}_n$, $\tilde F^{(7)}_n$, etc. are Tribonacci numbers (\seqnum{A000073}), Tetranacci numbers (\seqnum{A000078}), Pentanacci numbers (\seqnum{A001591}), Heptanacci numbers (\seqnum{A122189}), Octanacci numbers (\seqnum{A079262}), etc., respectively. \end{remark} \section{Examples} We now give some examples of IRS for $r=2$ and $3$. Let $A_{2}$ be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:5.1}) with coefficient set $E_{2}=\{ p_{1}, p_{2}\}$. Hence, from Theorems \ref{thm:1.3} and \ref{thm:1.4} and the definition of the impulse response sequence of $A_{2}$ with respect to $E_{2}$, we obtain \begin{corollary}\label{cor:5.2} Let $A_{2}$ be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:5.1}) with coefficient set $E_{2}=\{ p_{1}, p_{2}\}$, and let $\{\tilde F^{(2)}_{n}\}$ be the IRS (i.e., the Lucas sequence) of $A_{2}$. Suppose $\alpha$ and $\beta$ are two zeros of the characteristic polynomial of $A_{2}$, which do not need to be distinct. Then \be\label{eq:5.2} \tilde F^{(2)}_{n}=\begin{cases} \frac{\alpha^{n}-\beta^{n}}{\alpha -\beta}, & \text{if } \alpha\not= \beta;\\ n \alpha^{n-1}, & \text{if } \alpha =\beta.\end{cases} \ee In addition, every $\{ a_{n}\}\in A_{2}$ can be written as \be\label{eq:5.3} a_{n}=a_{1}\tilde F^{(2)}_{n}-\alpha \beta a_{0}\tilde F^{(2)}_{n-1}, \ee and $a_{n}$ reduces to $a_{1}\tilde F^{(2)}_{n}-\alpha^{2}a_{0}\tilde F^{(2)}_{n-1}$ when $\alpha=\beta$. Conversely, there is an expression for $\tilde F^{(2)}_n$ in terms of $\{a_n\}$ as \be\label{eq:5.4} \tilde F^{(2)}_n= c_1 a_{n+1}+c_2 a_{n-1}, \ee where \be\label{eq:5.5} c_1= \frac{a_{1}-a_{0}p_{1}}{p_{1}(a^{2}_{1}-a_{0}a_{1}p_{1}-a^{2}_{0}p_{2})},\quad c_2= -\frac{a_{1}p_2}{p_{1}(a^{2}_{1}-a_{0}a_{1}p_{1}-a^{2}_{0}p_{2})}, \ee provided that $p_1\not= 0$, and $a^{2}_{1}-a_{0}a_{1}p_{1}-a^{2}_{0}p_{2}\not= 0$. \end{corollary} \begin{proof} (\ref{eq:5.2}) is a special case of (\ref{eq:5.7}) and (\ref{eq:5.7.2}) and can be found from (\ref{eq:5.7}) and (\ref{eq:5.7.2}) by using the substitution $r=2$, $a_0=0$ and $a_1=1$. Again from (\ref{eq:5.8}) and (\ref{eq:5.8.3}) \bn\label{eq:5.3-0} a_n&=&a_{1}\tilde F_{n}+ a_{0}p_{2}\tilde F_{n-1}=a_{1}\tilde F_{n}-\alpha \beta a_{0}\tilde F_{n-1}\nonumber\\ &=&\begin{cases} a_1 \frac{\alpha^{n}-\beta^{n}}{\alpha -\beta} -\alpha \beta a_0\frac{\alpha^{n-1}-\beta^{n-1}}{\alpha -\beta}, & \text{if } \alpha\not= \beta;\\ a_1(n\alpha^{n-1})-\alpha^2 ((n-1)\alpha^{n-2}), & \text{if } \alpha =\beta \end{cases}. \en By using (\ref{eq:5.9}) and (\ref{eq:5.10}), we now prove (\ref{eq:5.4}) and (\ref{eq:5.5}), respectively. Denote by $L: {\bZ}\times{\bZ}\mapsto {\bZ}$ the operator $L(a_{n-1}, a_{n-2}):=p_{1}a_{n-1}+p_{2}a_{n-2}=a_{n}$. As presented before, $L$ is linear, and the sequence $\{a_{n}\}$ is uniquely determined by $L$ from a given initial vector ($a_{0}$, $a_{1}$). Define $a_{-1}=(a_{1}-p_{1}a_{0})/p_{2}$, then $(a_{-1}, a_{0})$ is the initial vector that generates $\{ a_{n-1}\}_{n\geq 0}$ by $L$. Similarly, the vector $(a_{1}, p_{1}a_{1}+p_{2}a_{0})$ generates sequence $\{ a_{n+1}\}_{n\geq }$ by using $L$. Note the initial vector of $\tilde F^{(2)}_{n}$ is $(0,1)$. Thus (\ref{eq:5.4}) holds if and only if the initial vectors on the two sides are equal: \be\label{eq:5.6} (0,1)=c_1 (a_{1}, p_{1}a_{1}+p_{2}a_{0})+c_2\left( \frac{a_{1}-p_{1}a_{0}}{p_{2}}, a_{0}\right), \ee which yields the solutions (\ref{eq:5.5}) for $c_1$ and $c_2$ and completes the proof of the corollary. \end{proof} Recall that \cite{HS} presented the following result. \begin{proposition}\label{pro:5.1}\cite{HS} Let $\{ a_n\}$ be a sequence of order $2$ satisfying linear recurrence relation (\ref{eq:5.1}), and let $\alpha$ and $\beta$ be two zeros of the characteristic polynomial $x^{2}-p_{1} x-p_{2}=0$ of the relation (\ref{eq:5.1}). Then \be\label{eq:5.1-2} a_n=\begin{cases} \left( \frac{a_1-\beta a_0}{\alpha-\beta}\right) \alpha^n- \left(\frac{a_1-\alpha a_0}{\alpha-\beta}\right) \beta^n, & \text{if } \alpha\not= \beta;\\ na_1 \alpha^{n-1}-(n-1)a_0\alpha^{n}, & \text{if } \alpha =\beta.\end{cases} \ee \end{proposition} The paper \cite{HS} also gives a method for finding the expressions of the linear recurring sequences of order $2$ and the interrelationship among those sequences. However, \cite{HS} also pointed out ``the method presented in this paper (i.e., Proposition \ref{pro:5.1}) cannot be extended to the higher order setting.'' In Section $2$, we have shown our method based on the IRS can be extended to the higher setting. Here, Proposition \ref{pro:5.1} is an application of our method in a particular case. In addition, it can be easily seen that (\ref{eq:5.1-2}) can be derived from (\ref{eq:5.3-0}). Corollary \ref{cor:5.2} presents the interrelationship between a linear recurring sequence with respect to $E_{2}=\{ p_{1}, p_{2})$ and its IRS, which can be used to transfer the identities of one sequence to the identities of other sequences in the same set. \begin{example} Let us consider $A_{2}$, the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:5.1}) with coefficient set $E_{2}=\{ p_{1}, p_{2}\}$. If $E_{2}=\{1,1\}$, then the corresponding characteristic polynomial has zeros $\alpha =(1+\sqrt{5})/2$ and $\beta =(1-\sqrt{5})/2$, and (\ref{eq:5.4}) gives the expression of the IRS of $A_{2}$, which is the Fibonacci sequence $\{ F_{n}\}$: \[ F_{n}= \frac{1}{\sqrt{5}}\left\{ \left( \frac{1+\sqrt{5}}{2}\right)^{n}-\left( \frac{1-\sqrt{5}}{2}\right)^{n}\right\}. \] The sequence in $A_{2}$ with the initial vector $(2,1)$ is the {\it Lucas number sequence} (which is different from the Lucas sequence) $\{ L_{n}\}$. From (\ref{eq:5.3}) and (\ref{eq:5.4}) and noting $\alpha \beta=-1$, we have the well-known formulas (see, for example, \cite{Koshy}): \[ L_{n}=F_{n}+2F_{n-1}=F_{n+1}+F_{n-1}, \quad F_{n}=\frac{1}{5}L_{n-1}+\frac{1}{5}L_{n+1}. \] By using the above formulas, one may transfer identities of Fibonacci number sequence to those of Lucas number sequence and vice versa. For instance, the above relationship can be used to prove that the following two identities are equivalent: \bns &&F_{n+1}F_{n+2}-F_{n-1}F_{n}=F_{2n+1}\\ &&L^{2}_{n+1}+L^{2}_{n}=L_{2n}+L_{2n+2}. \ens It is clear that both of the identities are equivalent to the Carlitz identity, $F_{n+1}L_{n+2}-F_{n+2}L_{n}=F_{2n+1}$, shown in \cite{Car}. \end{example} \begin{example} Let us consider $A_{2}$, the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:5.1}) with coefficient set $E_{2}=\{ p_1=p, p_2=1\}$. Then (\ref{eq:5.1-2}) tell us that $\{ a_{n}\}\in A_{2}$ satisfies \be\label{eq:9**} a_n=\frac{2a_1-(p-\sqrt{4+p^2})a_0}{2\sqrt{4+p^2}} \alpha^n-\frac{2a_1-(p+\sqrt{4+p^2})a_0}{2\sqrt{4+p^2}}\left( -\frac{1}{\alpha}\right)^n, \ee where $\alpha$ is defined by \be\label{eq:9*} \alpha =\frac{p+\sqrt{4+p^2}}{2} \,\,\,\mbox{and} \,\, \, \beta =-\frac{1}{\alpha}=\frac{p-\sqrt{4+p^2}}{2}. \ee Similarly, let $E_{2}=\{1,q\}$. Then \[ a_n= \begin{cases} \frac{2a_1-(1-\sqrt{1+4q})a_0}{2\sqrt{1+4q}}\alpha_1^n- \frac{2a_1-(1+\sqrt{1+4q})a_0}{2\sqrt{1+4q}}\alpha_2^n, & \text{if } q\not=- \frac{1}{4};\\ \frac{1}{2^n} (2n a_1-(n-1) a_0), & \text{if } q=-\frac{1}{4},\end{cases} \] where $\alpha=\frac{1}{2}(1+\sqrt{1+4q})$ and $\beta=\frac{1}{2}(1-\sqrt{1+4q})$ are solutions of equation $x^2-x-q=0$. The first special case (\ref{eq:9**}) was studied by Falbo \cite{Fal}. If $p=1$, the sequence is clearly the Fibonacci sequence. If $p=2$ (resp., $q=1$), the corresponding sequence is the sequence of numerators (when two initial conditions are $1$ and $3$) or denominators (when two initial conditions are $1$ and $2$) of the convergent of a continued fraction to $\sqrt{2}$: $\{ \frac{1}{1}$, $\frac{3}{2}$, $\frac{7}{5},$ $\frac{17}{12}, \frac{41}{29} \ldots\}$, called the closest rational approximation sequence to $\sqrt{2}$. The second special case is for the case of $q=2$ (resp., $p=1$), the resulting $\{ a_n\}$ is the Jacobsthal type sequences (See Bergum, Bennett, Horadam, and Moore \cite{BBHM}). \end{example} By using Corollary \ref{cor:5.2}, for $E_{2}=\{p,1\}$, the IRS of $A_2$ with respect to $E_2$ is \[ \tilde F^{(2)}_{n}=\frac{1}{\sqrt{4+p^{4}}}\left\{ \left( \frac{p+\sqrt{4+p^{2}}}{2}\right)^{n}-\left( \frac{p-\sqrt{4+p^{2}}}{2}\right)^{n}\right\}. \] In particular, the IRS for $E_{2}=\{2,1\}$ is the well-known Pell number sequence $\{P_{n}\}=\{0,1,2,5,12,29,\ldots\}$ with the expression \[ P_{n}=\frac{1}{2\sqrt{2}}\left\{ (1+\sqrt{2})^{n}-(1-\sqrt{2})^{n}\right\}. \] Similarly, for $E_{2}=\{1,q\}$, the IRS of $A_2$ with respect to $E_2$ is \[ \tilde F^{(2)}_{n}=\frac{1}{\sqrt{1+4q}}\left\{ \left( \frac{1+\sqrt{1+4q}}{2}\right)^{n}-\left( \frac{1-\sqrt{1+4q}}{2}\right)^{n}\right\}. \] In particular, the IRS for $E_{2}=\{1,2\}$ is the well-known Jacobsthal number sequence $\{J_{n}\}=\{0,1,1,3,5,11,21,\ldots\}$ with the expression \[ J_{n}=\frac{1}{3}\left( 2^{n}-(-1)^{n}\right). \] The Jacobsthal-Lucas numbers $\{ j_{n}\}$ in $A_{2}$ with respect to $E_{2}=\{1,2\}$ satisfying $j_{0}=2$ and $j_{1}=1$ has the first few elements as $\{ 2,1,5,7,17,31,\ldots\}$. From (\ref{eq:5.3}), one may deduce \[ j_{n}=J_{n}+4J_{n-1}=2^{n}+(-1)^{n}. \] In addition, the above formula can transform all identities of the Jacobsthal-Lucas number sequence to those of Jacobsthal number sequence and vice-versa. For example, we have \bns &&J^{2}_{n}+4J_{n-1}J_{n}=J_{2n},\\ &&J_{m}J_{n-1}-J_{n}J_{m-1}=(-1)^{n}2^{n-1}J_{m-n},\\ &&J_{m}J_{n}+2J_{m}J_{n-1}+2J_{n}J_{m-1}=J_{m+n} \ens from \bns &&j_{n}J_{n}=J_{2n},\\ &&J_{m}j_{n}-J_{n}j_{m}=(-1)^{n}2^{n+1}J_{m-n},\\ &&J_{m}j_{n}-J_{n}j_{m}=2J_{m+n}, \ens respectively. Similarly, we can show that the following two identities are equivalent: \[ j_{n}=J_{n+1}+2J_{n-1},\quad J_{n+1}=J_{n}+2J_{n-1}. \] \begin{remark} Corollary \ref{cor:5.2} can be extended to the linear nonhomogeneous recurrence relations of order $2$ with the form: $a_{n}=p a_{n-1}+q a_{n-2} +\ell$, $\ell \not= 0$, for $p+q\not= 1$. It can be seen that the above recurrence relation is equivalent to the homogeneous form (\ref{eq:5.1}) $b_n=p b_{n-1}+q b_{n-2}$, where $b_n=a_n-k$ and $k=\frac{\ell}{1-p-q}.$ \label{3.2} \end{remark} \begin{example} An obvious example of Remark~\ref{3.2} is the Mersenne number $M_n=2^n-1$, $n\geq 0$, which satisfies the linear recurrence relation of order $2$: $M_n=3 M_{n-1}-2 M_{n-2}$ ( with $ M_0=0$ and $M_1=1$) and the non-homogeneous recurrence relation of order $1$: $M_n=2M_{n-1}+1$ (with $M_0=0$). It is easy to check that sequence $M_n=(k^{n}-1)/(k-1)$ satisfies both the homogeneous recurrence relation of order $2$, $M_n=(k+1)M_{n-1}-k M_{n-2}$, and the non-homogeneous recurrence relation of order $1$, $M_n=k M_{n-1}+1$, where $M_0=0$ and $M_1=1$. Here, $M_n$ is the IRS with respect to $E_2=\{3,-2\}$. Another example is Pell number sequence that satisfies both homogeneous recurrence relation $P_n=2P_{n-1}+P_{n-2}$ and the non-homogeneous relation $\bar P_n=2\bar P_{n-1}+\bar P_{n-2}+1$, where $P_n=\bar P_n+1/2$. \end{example} \begin{remark} Niven, Zuckerman, and Montgomery \cite{NZM} studied some properties of two sequences, $\{G_n\}_{n\geq 0}$ and $\{ H_n\}_{n\geq 0}$, defined respectively by the linear recurrence relations of order $2$: \[ G_n=pG_{n-1}+q G_{n-2} \quad and \quad H_n=p H_{n-1}+q H_{n-2} \] with initial conditions $G_0=0$ and $G_1=1$ and $H_0=2$ and $H_1=p$, respectively. Clearly, $G_n=\tilde F^{(2)}_n$, the IRS of $A_2$ with respect to $E_2=\{p_1=p, p_2=q\}$. Using Corollary \ref{cor:5.2}, we may rebuild the relationship between the sequences $\{G_n\}$ and $\{ H_n\}$: \bns &&H_{n}=pG_{n}+2qG_{n-1},\\ &&G_{n}=\frac{q}{p^{2}+4q}H_{n-1}+\frac{1}{p^{2}+4q}H_{n+1}. \ens \end{remark} We now give more examples of higher order IRS in $A_3$. \begin{example} Consider set $A_3$ of all linear recurring sequences defined by (\ref{eq:1}) with coefficient set $E_3=\{ p_1=1, p_2=1, p_3=1\}$. The IRS of $A_3$ is the tribonacci number sequence $\{ 0,0,1,1,2,4,7,13,24,44,\ldots\}$ (\seqnum{A000073}). From Proposition \ref{pro:3.1}, the generating function of the tribonacci sequence is \[ \tilde P_3(t)=\frac{t^2}{1-t-t^2-t^3}. \] Theorem \ref{thm:1.3} gives the expression of the general term of tribonacci sequence as \[ \tilde F^{(3)}_n=\frac{\alpha^n_1}{(\alpha_1-\alpha_2)(\alpha_1-\alpha_3)}+ \frac{\alpha^n_2}{(\alpha_2-\alpha_1)(\alpha_2-\alpha_3)}+\frac{\alpha^n_3}{(\alpha_3-\alpha_1)(\alpha_3-\alpha_2)}, \] where \bns &&\alpha_1=-\frac{1}{3}-\frac{C}{3}+\frac{2}{3C},\\ &&\alpha_2=-\frac{1}{3}+\frac{C}{6}(1+i\sqrt{3})-\frac{1}{3C}(1-i\sqrt{3}),\\ &&\alpha_3=-\frac{1}{3}+\frac{C}{6}(1-i\sqrt{3})-\frac{1}{3C}(1+i\sqrt{3}), \ens in which $C=((6\sqrt{33}-34)/2)^{1/3}.$ The tribonacci-like sequence $\{ a_n\}=\{ 2,1,1,4,6,11,$ $21,\ldots\}$ (\seqnum{A141036}) is in the set $A_3$. From Theorem \ref{thm:1.4} and its corollary \ref{cor:1.5}, $a_n$ can be presented as \bn\label{eq:5.13} a_n&=&a_2\tilde F^{(3)}_n+\sum^1_{j=0}\sum^1_{k=j}a_k\tilde F^{(3)}_{n-j-1}. \nonumber\\ &=&a_2\tilde F^{(3)}_n+(a_0+a_1)\tilde F^{(3)}_{n-1}+a_1\tilde F^{(3)}_{n-2}. \en Using (\ref{eq:5.11}) and (\ref{eq:5.12}) in Theorem \ref{thm:1.6}, we may obtain the expression \be\label{eq:5.14} \tilde F^{(3)}_n=\frac{6}{19} a_{n+1}-\frac{4}{19}a_n-\frac{1}{19} a_{n-1}, \quad n\geq 0, \ee where $a_{-1}:=-2$ due to the linear recurrence relation $a_n=a_{n-1}+a_{n-2}+a_{n-3}$. It is easy to see the identity \[ \tilde F^{(3)}_n=2 \tilde F^{(3)}_{n-1}-\tilde F^{(3)}_{n-4}, \quad n\geq 4, \] because the right-hand side is equal to $\tilde F^{(3)}_{n-1}+\tilde F^{(3)}_{n-2}+\tilde F^{(3)}_{n-3}$ after substituting into $\tilde F^{(3)}_{n-1}=\tilde F^{(3)}_{n-2}+\tilde F^{(3)}_{n-3}+\tilde F^{(3)}_{n-4}$. Thus, by using (\ref{eq:5.14}) we have an identity for $\{ a_n\}$: \bns &&6 a_{n+1}-16 a_n+7 a_{n-1}+2a_{n-2}+6 a_{n-3}-4 a_{n-4}-a_{n-5}=0\\ \ens for all $n\geq 5$. Similarly from the identity $a_n=2a_{n-1}-a_{n-4}$, $n\geq 4$, and relation (\ref{eq:5.13}), we have the identity \[ \tilde F^{(3)}_{n}+\tilde F^{(3)}_{n-1}-5\tilde F^{(3)}_{n-2}-2\tilde F^{(3)}_{n-3}+\tilde F^{(3)}_{n-4}+3\tilde F^{(3)}_{n-5}+\tilde F^{(3)}_{n-6}=0 \] for all $n\geq 6$. \end{example} It is easy to see there exists $r$ number sequences, denoted by $\{a^{(j)}_n\}$, $j=1,2,\ldots, r$, in $A_r$ with respect to $E_r$ such that for any $\{ a_n\}\in A_r$ we have \[ a_n=\sum^r_{j=1} c_j a^{(j)}_n, \quad n\geq 0, \] where ${\bf c}=(c_1,c_2,\ldots, c_r)$ can be found from the system consisting of the above equations for $n=0, 1,\ldots, r-1$. In this sense, we may call $\{a^{(j)}_n\}$, $j=1,2,\ldots, r$, a basis of $A_r$ with respect to $E_r$. For instance, for $r=2$, let $\{ a^{(1)}_n\}$ be $\{F_n\}$, the IRS of $A_2$ with respect to $E_2=\{1,1\}$ (i.e., the Fibonacci sequence), and let $\{ a^{(2)}_n\}$ be the Lucas number sequence $\{ L_n\}$. Then $\{ \{ F_n\}, \{ L_n\}\}$ is a basis of $A_2$ because. Thus, for any $\{ a_n\}\in A_2$ with respect to $E_2=\{1,1\}$ and the initial vector $(a_0, a_1)$, we have \[ a_n=\left(a_1-\frac{1}{2} a_0\right)F_n +\frac{1}{2} a_0 L_n, \] where the coefficients of the above linear combination are found from the system \[ \left[\begin{array}{ll}0&2\\1&1\end{array}\right] \left[ \begin{array}{l} c_1\\ c_2\end{array}\right]=\left[ \begin{array}{l}a_0\\a_1\end{array}\right]. \] Obviously, if $\{ L_n\}$ is replaced by any sequence $\{ a^{(2)}_n\}$ in $A_2$ with respect to $E_2=\{1,1\}$, provided the initial vector $(a^{(2)}_0, a^{(2)}_1)$ of $\{ a^{(2)}_n\}$ satisfies \be\label{eq:5.15} \det \left[\begin{array}{ll}0&a^{(2)}_0\\1&a^{(2)}_1\end{array}\right] \not= 0, \ee then $\{ \{ F_n\}, \{ a^{(2)}_n\}\}$ is a basis of $A_2$ with respect to $E_2=\{ 1,1\}$. However, if $a^{(2)}_0=1$ and $a^{(2)}_1=0$, then the corresponding $a^{(2)}_n=F_{n-1}$, and the corresponding basis $\{ \{ F_n\}, \{ a^{(2)}_n=F_{n-1}\}\}$ is called a trivial basis. Thus, for $A_2$ with respect to $E_2=\{ p_1, p_2\}$, $\{ \{ \tilde F^{(2)}_n\}, \{ a^{(2)}_n\}\}$ forms a non-trivial basis, if the initial vector $(a^{(2)}_0, a^{(2)}_1)$ of $\{ a^{(2)}_n\}$ satisfies (\ref{eq:5.15}) and $a^{(2)}_0\not= 1/p_2$ when $a^{(2)}_1=0$. The second condition guarantees that the basis is not trivial, otherwise $a^{(2)}_n=\tilde F^{(2)}_{n-1}$. \section{Applications} In this section, we will give the applications of IRS to the Stirling numbers of the second kind, Wythoff array, and the Boustrophedon transform. Let $A_{r}$ be the set of all linear recurring sequences defined by the homogeneous linear recurrence relation (\ref{eq:1}) with coefficient set $E_{r}=\{ p_{1}, p_{2}, \ldots, p_r\}$, and let $\tilde F^{( r)}_{n}$ be the IRS of $A_{r}$. Theorems \ref{thm:1.4} gives expressions of $\{a_{n}\}\in A_{r}$ and the IRS of $A_{r}$ in terms of each other. We will give a different expression of $\{a_{n}\}\in A_{r}$ in terms of $\tilde F^{( r)}_{n}$ using the generating functions of $\{a_{n}\}$ and $\{ \tilde F^{( r)}_{n}\}$ shown in Proposition \ref{pro:3.1}. More precisely, let $\{ a_{n}\}\in A_{r}$. Then Proposition \ref{pro:3.1} shows that its generating function $P(t)$ can be written as (\ref{eq:3.1}). In particular, the generating function for the IRS with respect to $\{ p_j\}$ is presented as (\ref{eq:3.2}). Comparing the coefficients of $P(t)$ and $\tilde P(t)$, one finds \begin{proposition}\label{pro:3.0} Let $\{ a_{n}\}$ be an element of $A_{r}$, and let $\{ \tilde F^{( r)}_{n}\}$ be the IRS of $A_{r}$. Then \bn &&\tilde F^{( r)}_{n}=[t^{n-r+1}]\frac{1}{1-\sum^{r}_{j=1}p_{j}t^{j}}\label{eq:3.3}\\ &&a_{n}=a_{0}\tilde F^{( r)}_{n+r-1}+\sum^{r-1}_{k=1}(a_{k}-\sum^{k}_{j=1}p_{j}a_{k-j})\tilde F^{( r)}_{n+r-k-1}.\label{eq:3.3.2} \en \end{proposition} \begin{proof} Eq.~(\ref{eq:3.3}) comes from \[ \tilde F^{( r)}_{n}=[t^{n}]\tilde P(t)=[t^{n-r+1}]\frac{1}{1-\sum^{r}_{j=1}p_{j}t^{j}}. \] Hence, \bns &&a_{n}=[t^{n}]P(t)=a_{0}[t^{n}]\frac{1}{1-\sum^{r}_{j=1}p_{j}t^{j}}+[t^{n}]\frac{\sum^{r-1}_{k=1}\left( a_{k}-\sum^{k}_{j=1}p_{j}a_{k-j}\right)t^{k}}{1-\sum^{r}_{j=1}p_{j}t^{j}}\\ &=&a_{0}\tilde F^{( r)}_{n+r-1}+\sum^{r-1}_{k=1}\left( a_{k}-\sum^{k}_{j=1}p_{j}a_{k-j}\right)[t^{n-k}] \frac{1}{1-\sum^{r}_{j=1}p_{j}t^{j}}, \ens which implies (\ref{eq:3.3}). \end{proof} \begin{proposition}\label{pro:3.2} If \be\label{eq:3.-1} g(t)=\frac{ t^{r-1}}{1-\sum^{r}_{j=1}p_{j}t^{j}} \ee is the generating function of a sequence $\{ b_n\}$, then $\{ b_n\}$ satisfies \[ b_n=\begin{cases} 0, & \text{if } n=0,1,\ldots, r-2;\\ 1, & \text{if } n=r-1;\\ \sum^r_{j=1}p_j b_{n-j}, & \text{if } n\geq r. \end{cases} \] \end{proposition} \begin{proof} It is clear that \bns &&b_j=[t^j] g(t)=[t^{j-r+1}]\frac{ 1}{1-\sum^{r}_{j=1}p_{j}t^{j}}\\ &=&[t^{j-r+1}]\sum_{k\geq 0} \left( \sum^{r}_{j=1}p_{j}t^{j}\right)^k=\begin{cases} 0 & \text{if } 0\leq j\leq r-2,\\ 1 & \text{if } j=r-1.\end{cases} \ens For $n\geq r$, \bns &&\sum^r_{j=1} p_j b_{n-j}=\sum^r_{j=1} p_j [t^{n-j}]g(t)\\ &=&[t^n]\sum^r_{j=1}t^{r-1} \frac{ p_jt^{j}}{1-\sum^{r}_{i=1}p_{i}t^{i}}\\ &=&[t^n] t^{r-1} \left( \frac{ 1}{1-\sum^{r}_{i=1}p_{i}t^{i}}-1\right)\\ &=&[t^n]g(t)-[t^n]t^{r-1}=b_n, \ens which completes the proof. \end{proof} The Stirling numbers of the second kind $S(n,k)$ count the number of ways to partition a set of $n$ labelled objects into $k$ unlabeled subsets. We now prove that the sequence $\{b_n =S(n+1,k)\}_{n\geq 0}$ is the IRS of $A_k$ for any $k\in{\bN}_0$ by using the structure of the triangle of the Stirling numbers of the second kind shown in Table $1$. \begin{center} $\begin{array}{c|rrrrrrr} n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & 1 \\ 1 & 0& 1 \\ 2 & 0& 1 & 1 \\ 3 & 0& 1 & 3 & 1 \\ 4 & 0 & 1 & 7 & 6& 1 \\ 5 & 0 & 1& 15 & 25 & 10 & 1 \\ 6 & 0 & 1 & 31 & 90 & 65 & 15 & 1 \\ \end{array}$ \medskip \centerline{Table $1$. Triangle of the Stirling numbers of the second kind} \end{center} \begin{theorem}\label{thm:3.3} Let $S(n,k)$ be the Stirling numbers of the second kind. Then, for any fixed integer $k>0$, $S(n+1,k)$ is the IRS of $A_k$, i.e., \be\label{eq:3.4} S(n+1,k)=\tilde F^{(k)}_n, \ee where $A_k$ is the set of linear recurring sequences $\{ a_n\}$ generated by \be\label{eq:3.5} a_n=\sum^k_{j=1}p_j a_{n-j}, \ee which has characteristic polynomial \begin{equation}\label{eq:3.6} P(t)=t^k-\sum^k_{j=1}p_j t^{k-j}=\prod^k_{j=1} (1-j t). \end{equation} Thus, the generating function of $\{ S(n+1,k)\}$ is \be\label{eq:3.7} \tilde P(t)=\frac{t^k}{\prod^k_{j=1} (1-jt)}. \ee \end{theorem} \begin{proof} $\{S(n,k)\}_{0\leq k\leq n}$ obeys the recurrence relation \be\label{eq:3.8} S(n+1,k)=k S(n,k)+S(n,k-1), \quad 0\leq k\leq n, \ee which can be explained by using the definition of $S(n,k)$ shown above. A partition of the $n+1$ objects into $k$ nonempty subsets either contains the subset $\{ n+1\}$ or it does not. The number of ways that $\{ n+1\}$ is one of the subsets is given by $S(n,k-1)$, since we must partition the remaining $n$ objects into the available $k-1$ subsets. The number of ways that $\{ n+1\}$ is not one of the subsets is given by $k S(n,k)$ because we partition all elements other than $n+1$ into $k$ subsets with $k$ choices for inserting the element $n+1$. Summing these two values yields (\ref{eq:3.8}). Write (\ref{eq:3.8}) as \[ S(n,k-1)=S(n+1,k)-kS(n,k), \quad 0< k\leq n. \] Denote by $g_{k-1}(t)$ and $g_k(t)$ the generating functions of $k-1$st and $k$th columns of the Stirling triangle shown in Table $2$. Then the above equation means \[ [t^n] g_{k-1}(t)=S(n,k-1)=S(n+1,k)-kS(n,k)=[t^{n+1}]g_k(t)-k [t^n]g_k(t)=[t^{n+1}](1-kt)g_k(t) \] for $0< k\leq n$. Therefore, we have \[ g_k(t)=\frac{t}{1-kt}g_{k-1}(t). \] Since $g_1(t)=t/(1-t)$, we obtain the generating function of $\{ S(n,k)\}$ for $k>0$ \be\label{eq:3.9} g_k(t)=\frac{t^{k}}{\prod^k_{j=1} (1-jt)}. \ee Denote $b_n=S(n+1,k)$ and the generating function of $\{ b_n\}$ by $B(t)$. Then \[ b_n=[t^n] B(t)=S(n+1,k)=[t^{n+1}] g_k(t), \quad 0