\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}}} \DeclareMathOperator{\mc}{mc} \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} \newtheorem{problem}[theorem]{Problem} \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 On Linear Recurrence Equations Arising \\ \vskip .1in from Compositions of Positive Integers} \vskip 1cm \large Milan Janji\'c \\ Department of Mathematics and Informatics\\ University of Banja Luka\\ Banja Luka, 78000\\ Republic of Srpska, Bosnia and Herzegovina\\ \href{mailto:agnus@blic.net}{\tt agnus@blic.net}\\ \end{center} \vskip .2 in \begin{abstract} For an arithmetic function $f_0$, we define a new arithmetic function $f_1$, generalizing the linear recurrence for the numbers of compositions of positive integers. Using $f_1$ in the same way, we then define $f_2$, and so on. We establish some patterns related to the sequence $f_1,f_2,\ldots$. Our investigations depend on the following result: if $f_0$ satisfies a linear recurrence equation of order $k$, then each function $f_m$ will also satisfy a linear recurrence equation of the same order. In several results, we derive a recurrence equation for $f_m(n)$, in terms of $m$ and $n$. For each result, we give a combinatorial meaning for $f_m(n)$ in terms of the number of restricted words over a finite alphabet. We also find new combinatorial interpretations of the Fibonacci polynomials, as well as the Chebyshev polynomials of the second kind. \end{abstract} \section{Introduction} Researchers usually investigate compositions of positive integers through their generating functions, connecting them to the so-called invert transforms. In this paper, we take a different approach. Investigating some generalizations of the linear recurrence equations for the numbers of compositions, we proceed to show that certain linear recurrences may be considered as recurrences for the numbers of some kinds of compositions. In conclusion, we provide a number of results, which illustrate some consequences of our findings. We are interested in two particular problems: obtaining a recurrence equation for $f_m(n)$ when $f_0$ is given, and investigating relationships of the sequence $f_1,f_2,\ldots$ with the number of restricted words over a finite alphabet. In our interpretation of $f_m(n)$ in terms of restricted words, the number of letters in the alphabet is determined by the parameter $m$, while the length of a word is determined by the parameter $n$. In particular, if $f_0$ takes values in $\{0,1\}$, then $f_1(n)$ counts the number of some compositions of $n$, so that $f_1$ always produces a relationship between the compositions and the binary words. In fact, our sequence of functions might be understood as a way to transfer some properties from the binary words to words over a finite alphabet. We derive connections our sequence of our sequence with the Fibonacci polynomials and the Chebyshev polynomials of the second kind. Fibonacci numbers are generalized in several ways. We finish the paper by giving the combinatorial meaning for a class of sequences when $f_0$ satisfies a particular linear recurrence equation of second order with constant coefficients. We start with the definition of our sequence. \begin{definition}\label{d1} We define a pair $(f_0,f_1)$ of arithmetic functions as follows: Let $f_0$ be an arbitrary arithmetic function. A function $f_1$ is recursively defined through the convolution \begin{equation}\label{r1} f_1(n)=\sum_{i=1}^nf_0(i)f_1(n-i),\;(n\geq 1),\end{equation} where $f_1(0)=1$. Inductively, for each $m>0$, we define the pair $(f_{m-1},f_m)$. \end{definition} \begin{corollary}\label{co1} For each $m\geq 1$, we have \[f_m(1)=f_0(1),\;f_m(2)=mf_0(1)^2+f_0(2).\] \end{corollary} \begin{proof} We use induction with respect to $m$. From Equation (\ref{r1}), we conclude that the claim holds for $m=1$. Suppose that the claim is true for $m$. Then $f_{m+1}(1)=f_m(1)$, and so $f_{m+1}(1)=f_0(1)$. In the same way, we obtain $f_{m+1}(2)=f_m(1)^2+f_m(2)$. Applying the induction hypothesis gives \[f_{m+1}(2)=f_0(1)^2+mf_0(1)^2+f_0(2)=(m+1)f_0(1)^2+f_0(2).\] \end{proof} \begin{remark} If $f_0(i)=1,(i\geq 1)$ then Equation \ref{r1} becomes the recurrence for the numbers of compositions of positive integers. \end{remark} \begin{remark} Note that $f_m$ is a particular case of $1$-determinants, defined in Janji\'c \cite{mil1}. \end{remark} Using the notion of the invert transform, we easily find the generating function for the sequence $f_1(1),f_1(2),\ldots$. \begin{proposition} The sequence $\{f_1(n)\}_{n=1}^\infty$ is the invert transform of the sequence $\{f_0(n)\}_{n=1}^\infty$. \end{proposition} \begin{proof} It is easy to see that Equation (\ref{r1}) is equivalent to \[\left[1+\sum_{i=1}^\infty f_1(i)x^i\right]\cdot\left[1-\sum_{i=1}^\infty f_0(i)x^i\right]=1.\] Hence, the generating function of the sequence $f_1(1),f_1(2), \ldots$ is \[\frac{1}{1-\sum_{i=1}^\infty f_0(i)x^i}.\] \end{proof} In general, an arithmetic function maps the set of positive (or nonnegative) integers into the set of complex numbers. The results of the next section are valid for such functions. \section{A result on linear recurrences} We proceed to prove that, if $f_0$ satisfies a linear recurrence equation of order $k$, then $f_1$ also satisfies a linear recurrence of the same order. To stress the dependence of $f_0$ and $f_1$ on $k$, we write $f_i(n;k)$ instead of $f_i(n)$ for $i=1,2$. \begin{theorem}\label{te1} Let $f_0$ be an arithmetic function, and let $k$ be a positive integer. If there exist constant numbers (complex) $a_0(1),a_0(2),\ldots,a_0(k)$ such that \begin{equation}\label{r0}f_0(n+k;k)=\sum_{i=1}^ka_0(i)f_0(n+k-i;k),(n\geq 1),\end{equation} where $f_0(1;k),f_0(2;k),\ldots,f_0(k;k)$ are arbitrary numbers (complex), then we have \begin{gather}\label{pu}f_{1}(i;k)=\sum_{j=1}^if_0(j;k)f_{1}(i-j;k),(i=1,2,\ldots,k),\text{ and}\\ \label{rr1} f_{1}(n+k;k)=\sum_{i=1}^ka_{1}(i)f_{1}(n+k-i;k),(n\geq 1),\end{gather} where \begin{multline}\label{be}a_{1}(1)=a_0(1)+f_0(1;k), \\a_{1}(i)=a_0(i)+f_0(i;k)-\sum_{j=1}^{i-1}a_0(j)f_0(i-j;k),(2\leq i\leq k). \end{multline} \end{theorem} \begin{proof} We first consider the case $k=1$. If $f_0(n+1;1)=a_0(1)f_0(n;1),(n\geq 1),$ then \[f_1(n+1;1)=\sum_{i=1}^{n+1}f_0(i;1)f_1(n+1-i;1)=f_0(1;1)f_1(n;1)+\sum_{i=2}^{n+1}f_0(i;1)f_1(n+1-i;1),\] which implies $f_1(n+1;1)=[f_0(1;1)+a_0(1)]f_1(n;1)$. Hence, Theorem \ref{te1} is true for $k=1$. Assume that $k>1$. For $1\leq i\leq k,$ we have \[f_1(n+k-i;k)=\sum_{j=1}^{n+k-i}f_0(j;k)f_1(n+k-i-j;k).\] We denote $f_1(n+k-i;k)=X_i+Y_i,(i=1,\ldots,n),$ where \begin{equation}\label{ml1} X_i=\sum_{j=1}^{k-i}f_0(j;k)f_1(n+k-i-j;k),\;Y_i=\sum_{j=k-i+1}^{n+k-i}f_0(j;k)f_1(n+k-i-j;k), \end{equation} with $X_k=0$. It follows that \begin{equation}\label{xax}\sum_{i=1}^{k}a_0(i)X_i=\sum_{i=2}^{k} \left[\sum_{j=1}^{i-1}a_0(j)f_0(i-j;k)\right]f_1(n+k-i;k).\end{equation} Also, after some calculations, we obtain \begin{equation}\label{xx}\sum_{i=1}^ka_0(i)Y_i=f_1(n+k;k) -\sum_{i=1}^{k}f_0(i;k)f_1(n+k-i;k).\end{equation} From equations (\ref{xax}) and (\ref{xx}), we obtain \begin{gather*}\sum_{i=1}^ka_if_1(n+k-i;k)=\sum_{i=1}^ka_i(X_i+Y_i)=\\ \sum_{i=2}^{k} \left[\sum_{j=1}^{i-1}a_0(j)f_0(i-j;k)\right]f_1(n+k-i;k)+f_1(n+k;k)-\sum_{j=1}^{k}f_0(j;k) f_1(n+k-j;k). \end{gather*} We finally have \[f_1(n+k;k)=\sum_{i=1}^{k}[a_i+f_0(i;k)]f_1(n+k-i;k)- \sum_{i=2}^{k} \left[\sum_{j=1}^{i-1}a_if_0(i-j,k)\right]f_1(n+k-i;k),\] which is Equation (\ref{rr1}), under the conditions (\ref{pu}). \end{proof} \begin{remark}In the conditions of Theorem \ref{te1}, we may always find an explicit formula for $f_1(n;k),$ when $k=1,2,3,4$ by solving the characteristic equations. \end{remark} The simplest case of Theorem \ref{te1} is \begin{corollary} \label{cc1} If $f_0(n+1)=af_0(n),(n\geq 1)$, for some $a$, then for $m\geq 1$ we have \[f_m(n+1)=[mf_0(1)+a]f_m(n),(n\geq 1).\] The explicit formula for $f_m$ is \[f_m(n)=f_0(1)[mf_0(1)+a]^{n-1},(n\geq 1).\] \end{corollary} \begin{proof} For $m=1,$ according to Theorem \ref{te1}, we have $a_1(1)=a+f_0(1)$, and the claim is true for $m=1$. The rest follows by induction. \end{proof} We finished this section by stating the recurrence equation for $f_m,(m\geq 1)$, assuming that $f_0$ satisfies a linear recurrence of order $2$. \begin{corollary}\label{pr2} If $f_0(1),f_0(2)$ are arbitrary, and \[f_0(n+2)=a_0(1)f_0(n+1)+a_0(2)f_0(n),\] then \begin{equation}\label{2pu}f_m(1)=f_0(1),\;f_m(2)=mf_0(1)^2+f_0(2),\end{equation} and \begin{equation}\label{ab} f_m(n+2)=a_m(1)f_m(n+1)+a_m(2)f_m(n),\end{equation} where $a_m(1)=a_0(1)+mf_0(1), a_m(2)=a_0(2)-ma_0(1)f_0(1)+mf_0(2)$. \end{corollary} \begin{proof} This is a particular case of Theorem \ref{te1}. \end{proof} We stress that in all that follows the values of arithmetical functions $f_m,(m\geq 0)$ will be nonnegative integers. \section{Compositions and words} The function $f_1$ generalizes the notions of the numbers of compositions of positive integers for several kinds of compositions. We state some of them. \begin{corollary}\label{ccc} \begin{enumerate} \item If $f_0(i)$ is either $1$ or $0$ and $Q=\{i:f_0(i)=1\},$ then $f_1(n)$ equals the number of compositions of $n,$ the parts of which belong to $Q$. \item If $f_0(i)=1$ for all $i$, then $f_1(n)(=2^{n-1})$ equals the number of all compositions of $n$. \item If $f_0(i)\geq 0$ for all $i,$ then $f_1(n)$ equals the number of the colored compositions of $n,$ in which part $i$ may appear in $f_0(i)$ different colors. \end{enumerate} \end{corollary} \begin{proof} All claims are easy to prove. \end{proof} \begin{remark} Note that Claim 3 above is, in fact, the combinatorial interpretation of the invert transform in Bernstein and Sloane \cite{slo1}. \end{remark} The Catalan numbers $C_i,\;(i=0,1,\ldots)$ may also be considered as a kind of colored compositions. \begin{proposition} If $f_0(i)=C_{i-1}$ for all $i\geq 1$, then $f_1(n)=C_n$. \end{proposition} \begin{proof} The claim follows from Segner's formula for the Catalan numbers; see Koshy \cite[Formula (5.6), p.\ 117]{kos}. \end{proof} Now we show that the function $f_1$ also counts the number of the $k$-matrix compositions, considered by Munarini at al.~\cite{rin}. A $k$-matrix composition of $n$ is a matrix with $k$ rows, in which the entries are nonnegative integers, there are no columns consisting of zeros only, and the sum of all entries equals $n$. Let $\mc(n;k)$ denote the number of such compositions. We have \begin{proposition} If $f_0(i)={k+i-1\choose k-1},\;(i=1,2,\ldots),$ then $\mc(n;k)=f_1(n)$. \end{proposition} \begin{proof} For given $i,(1\leq i\leq k)$, the equation $x_1+x_2+\cdots+x_k=i$ has ${k+i-1\choose k-1}$ nonnegative solutions. This means that there are ${k+i-1\choose k-1}\cdot \mc(n-i;k)$ $k$-matrix compositions of $n$, ending with a column having the sum of all elements equal $i$. Taking $\mc(0;k)=1,$ we obtain \[\mc(n;k)=\sum_{i=1}^n{i+k-1\choose k-1}\mc(n-i;k).\] Comparing this equation with Equation (\ref{r1}), we conclude that $\mc(n;k)=f_1(n)$. \end{proof} \begin{remark} The sequences in Sloane \cite{slo}, the members of which count $k$-compositions are: \seqnum{A003480}, \seqnum{A145839}, \seqnum{A145840}, \seqnum{A145841}, \seqnum{A161434}. \end{remark} We next note that, for a suitably chosen $f_0$, the function $f_1$ counts the number of particular partitions of positive integers. Namely, for the set $Q=\{q_1,q_2,\ldots,q_n\}$ of positive integers, we let $p(Q,n)$ denote the number of partitions of $n,$ the parts of which belong to $Q$. Janji\'c and Petkovi\'c, in \cite{mp}, consider the following function: \[a_i=\sum_{j=0}^i (-1)^{i-j}{n+k+1\choose i-j}{j,n\choose k,Q},(i\geq 0),\] where numbers ${j,n\choose k,Q}$ are defined in the following way: \begin{enumerate} \item $k=\sum_{t=1}^n(q_t-1)$. \item Consider a set $X$ consisting of $n$ blocks $X_1,X_2,\ldots,X_n,$ such that $|X_i|=q_i$ for all $i$ and an additional block $Y$, such that $|Y|=j$. \end{enumerate} The number ${j,n\choose k,Q}$ is the number of $(n+k)-$subsets of $X$ intersecting each block $X_i,\;(i=1,2,\ldots,n)$. From Janji\'c \cite[Theorem 2]{mil2}, we obtain \begin{proposition}\label{ppp} If $f_0(i)=-a_i$ for all $i$, then \[f_1(n)=p(Q,n),\;(n=1,2,\ldots,n).\] \end{proposition} \begin{remark} Some sequences in Sloane \cite{slo} generated by $f_1$ in Proposition \ref{ppp} are: \seqnum{A001401}, \seqnum{A001045}, \seqnum{A008616}, \seqnum{A008676}, \seqnum{A109707}, \seqnum{A025795}, \seqnum{A008677}, \seqnum{A025839}, \seqnum{A029144}, \seqnum{A029280}. \end{remark} \begin{corollary}\label{cor} If $a=1$, $m=1$, and $f_0(1)=p$, where $p$ is a positive integer, then $f_1(n)=p(1+p)^{n-1},$ which is the number of the colored compositions of $n$, such that each part may appear in $p$ different colors. \end{corollary} \begin{remark} Some sequences in Sloane \cite{slo} generated by $f_1$ from Corollary \ref{cor} are: \seqnum{A000079}, \seqnum{A000244}, \seqnum{A025192}, \seqnum{A020699}, \seqnum{A093138}. \end{remark} Assume that $f_0(i)=1,\;(i\geq 1)$. Then, by Corollary \ref{cor} we have \[f_m(n)=(m+1)^{n-1}.\] In this particular case, we obtain the following relationship of our sequence and numbers of words over an alphabet with $m+1$ letters. \begin{corollary}\label{cor1} The number $f_m(n)$ equals the number of words of length $n-1$ over an alphabet of $m+1$ letters. \end{corollary} We consider the case when values of $f_0$ are either $0$ or $1$. Take $g_0(i)=1,(i=1,2,\ldots)$. Then, for all $i$, we have $f_0(i)\leq g_0(i)$. Since each term in Equation (\ref{r1}) is nonnegative, we conclude that $f_m(n)\leq g_m(n),(n\geq 0)$ for each $m$, and since $g_m(n)=(m+1)^{n+1}$, we obtain \begin{proposition} If the values of $f_0$ are either $0$ or $1$, then $f_m$ counts some restricted words over the alphabet $\{0,1,\ldots,m\}$. \end{proposition} Our further investigation may be summarized by the following two problems. \begin{problem} Suppose that $f_0$ takes values either $0$ or $1$. \begin{enumerate} \item Find either a recurrence or an explicit formula for $f_m(n)$ in terms of $m$ and $n$. \item Describe the set of restricted words over the alphabet $\{0,1,\ldots,m\}$ counted by $f_m(n)$. \end{enumerate} \label{prob1} \end{problem} \begin{problem} Solve Problem~\ref{prob1} when $f_0$ may have values other than $0$ and $1$. \label{prob2} \end{problem} \section{Some results concerning Problem~\ref{prob1}} \begin{proposition}\label{ppp1} Assume that $f_0(1)=0$, and $f_0(i)=1,(i>1)$. Then we have \[f_m(1)=0,f_m(2)=1,\] and \[f_m(n+2)=f_m(n+1)+mf_m(n).\] \end{proposition} \begin{proof} The function $f_0$ clearly satisfies the following linear recurrence of order $2$.\[f_0(1)=0,f_0(2)=1, \text{ and } f_0(n+2)=a_0(1)f_0(n+1)+a_0(2)f_0(n),(n\geq 1),\] where $a_0(1)=1,a_0(2)=0$. Now the assertion is an immediate consequence of Corollary \ref{pr2}. \end{proof} \begin{corollary}\label{cof}For $n\geq 0$, the number $f_m(n+2)$ from Proposition \ref{ppp1} counts the number of words of length $n-1$, over the alphabet $\{0,1,\ldots,m\}$, where no two consecutive letters are nonzero. \end{corollary} \begin{proof} We let $g(n)$ denote the number of required words of length $n$. We have $g(0)=1=f_m(3)$, since only an empty word has length $0$. Further, we have $g(1)=m+1=f_m(4)$. Consider words of length $n+1,(n>0)$. There are $g(n)$ such words beginning with $0$. If a word begins with $j\not=0$, then the next letter must be $0$, which yields that there are $g(n-1)$ such words. Since $j$ may take $m$ different values, we see that $g(n+1)=g(n)+mg(n-1)$. It follows that $g(n-1)=f_m(n+2),(n\geq 0)$. \end{proof} \begin{remark} In the case $m=1$, Corollary \ref{cof} gives the following well-known property of the Fibonacci numbers: For $n\geq 1$, Fibonacci number $F_{n+1}$ counts $11$-avoiding binary words of length $n-1$. The case $m=2$ gives the analogous property of the Jacosthal numbers. \end{remark} \begin{remark} Some sequences in Sloane \cite{slo} generated by $f_m$ from Corollary \ref{cof} for different $m$'s are: \seqnum{A000045}, \seqnum{A001045}, \seqnum{A006130}, \seqnum{A006131}, \seqnum{A015440}, \seqnum{A015441}, \seqnum{A015442}, \seqnum{A015443}, \seqnum{A015445}, \seqnum{A015446}, \seqnum{A015447}, \seqnum{A053404}. \end{remark} \begin{proposition}\label{pr1} We define \[f_0(i)=\begin{cases}1,&\text{if $i$ is odd};\\0,&\text{if $i$ is even}.\end{cases}\] Then \[f_m(1)=1,f_m(2)=m,\] and \begin{equation}\label{kj}f_m(n+2)=mf_m(n+1)+f_m(n).\end{equation} \end{proposition} \begin{proof} The function $f_0$ satisfies the following recurrence: \[f_0(1)=1,f_0(2)=0,\] \[f_0(n+2)=a_0(1)f_0(n+1)+a_0(2)f_0(n),\] where $a_0(1)=0,a_0(2)=1$. The claim is now a simple consequence of Corollary \ref{pr2}. \end{proof} \begin{corollary}\label{cor7} If $f_0(i)$ is defined as in Proposition \ref{pr1}, then the number $f_m(n+1)$ equals the number $n$-length over the alphabet $\{0,1,\ldots,m\}$ avoiding runs of zeros of odd lengths. \end{corollary} \begin{proof} We let $d(n)$ denote the number of required words of length $n$. Then, obviously, $d(0)=1,d(1)=m$. For $n>1$, there are $md(n-1)$ words of length $n$ beginning with a nonzero letter. If a word begins with $0$, then it must begin with at least two zeros. Hence there are $d(n-2)$ such words. We conclude that $d(n)=f_{m}(n+1),(n\geq 0)$. \end{proof} As an immediate consequence of Proposition \ref{pr1}, we obtain the following connection of our functions with Fibonacci polynomials $F_n(x)$. \begin{corollary} In terms of Proposition \ref{pr1}, we have \[f_m(n)=F_n(m).\] \end{corollary} Proposition \ref{pr1} also generalizes the Fibonacci number through the golden ratio. \begin{corollary}\label{cc2} If $\alpha$ and $\beta$ are solutions of the characteristic equation of Equation (\ref{kj}), then the explicit formula for $f_m$ in Proposition \ref{pr1} is \[f_m(n)=C_1(\Phi_m)^n+C_2(-\Phi_m^{-1})^n,\] where \[C_1=\frac{f_m(2)-\beta f_m(1)}{\alpha(\alpha-\beta)}, C_2=-\frac{f_m(2)-\alpha f_m(1)}{\beta(\alpha-\beta)}.\] For $\Phi_m,$ we have \begin{enumerate} \item $\Phi_1$ is the golden ratio, that is, $\Phi_1=\frac{1+\sqrt 5}{2}$. \item $\Phi_2$ is the silver ratio, that is, $\Phi_2=1+\sqrt 2$. \item $\Phi_3$ is the bronze ratio, that is, $\Phi_3=\frac{3+\sqrt 13}{2}$. \item Generally, $\Phi_m=\frac{m+\sqrt{4+m^2}}{2}$. \end{enumerate} \end{corollary} \begin{remark} Some sequences from Sloane's \cite{slo} generated by recurrence from Corollary \ref{cc2} are: \seqnum{A000045}, \seqnum{A000129}, \seqnum{A006190}, \seqnum{A001076}, \seqnum{A052918}, \seqnum{A005668}, \seqnum{A054413}, \seqnum{A041025}, \seqnum{A041041}. \end{remark} \begin{proposition}\label{pp1} Let $k$ be a positive integer. We define \[f_0(i;k)=\begin{cases}1,& \text{if $1\leq i\leq k$;} \\0,&\text{ otherwise}.\end{cases}\] Then, for $m\geq 1$, we have \begin{equation}\label{kpu}f_m(i;k)=(m+1)^{i-1},(i=1,2,\ldots,k),\end{equation} and \begin{equation}\label{f2}f_m(n+k;k)=m\sum_{i=1}^kf_1(n+k-i;k).\end{equation} \end{proposition} \begin{proof} In this case, we have $f_0(i;k)=1,a_0(i)=0,(i=1,2,\ldots,k)$. Equation (\ref{pu}) now gives $a_1(i)=1,(1\leq i\leq k)$, which yields that Equation (\ref{f2}) holds for $m=1$. Assume that Equation (\ref{f2}) holds for $m$. To prove that $f_{m+1}(i;k)=(m+2)^{i-1},(1\leq i\leq k)$, it is enough to use induction and the identity: \[(m+2)^{i-1}=(m+1)^{i-1}+\sum_{j=1}^{i-1}(m+1)^{j-1}(m+2)^{i-1-j}.\] This identity is easy to prove. We have $a_m(i)=m,(i=1,\ldots,k)$. Using equation (\ref{be}), we obtain $a_{m+1}(1)=m+f_m(1;k)=m+1$. For $2\leq i\leq k$, using induction and the identity \[m+1= m+(m+1)^{i-1}-m\sum_{j=1}^{i-1}(m+1)^{i-1-j},\] which is also easy to prove, we conclude that the claim holds for $m+1$. \end{proof} It is known that $F_{n+2}$ equals the number of $00$-avoiding binary words of length $n$. Example \ref{pp1} generalizes this property in the following way: \begin{corollary}\label{trib} The number $f_m(n+1;k)$ from Proposition \ref{pp1} equals the number of words of length $n$ over the alphabet $\{0,1,\ldots,m\}$, avoiding runs of $k$ zeros. \end{corollary} \begin{proof} Let $g(n;k)$ denote the number of required words of length $n$. We have $g(0;k)=1,$ since only the empty word has length $0$. Next, we have $g(i;k)=(m+1)^{i},(1\leq i\leq k-1),$ since no word of length $0).\end{equation} \end{proposition} \begin{proof} It is easy to see that $f_0$ satisfies the following recurrence: \[f_0(1)=p,f_0(2)=q+p,\] \[f_0(n+2)=a_0(1)f_0(n+1)+a_0(2)f_0(n),\] where \[a_0(1)=2,a_0(2)=-1.\] Therefore we may apply Corollary \ref{pr2}. It follows that \begin{gather*}f_{m+1}(1)=f_m(1)=p,\;f_{m+1}(2)=[f_m(1)]^2+f_m(2)=\\p^2+q+p+mp^2=q+p+(m+1)p^2. \end{gather*} Also, we have \begin{gather*}a_{m+1}(1)=a_m(1)+f_m(1)=mp+2+p=(m+1)p+2,\\ a_{m+1}(2)=a_m(2)+f_m(2)-a_m(1)f_m(1)=\\mq-m p-1+q+p+mp^2-(m p+2)p =(m+1)q-(m+1)p-1,\end{gather*} and the proposition is proved. \end{proof} In a particular case of the preceding proposition, we find the combinatorial meaning of $f_m(n)$ in terms of restricted words. \begin{corollary} \begin{enumerate} \item If $f_0(i)=i,(i\geq 1)$ then, for $m\geq 1,$ we have \begin{equation}\label{ek1}f_m(1)=1,\;f_m(2)=m+2,\end{equation} \begin{equation}\label{ek2}f_m(n+2)=(m+2)f_m(n+1)-f_m(n),\;(n>0).\end{equation} \item The number $f_m(n)$ equals the number of $01$-avoiding words of length $n-1$ over the alphabet $\{0,1,2,3,\ldots,m+1\}$. \item For $n\geq 1$, we have $f_m(n)=U_{n-1}(\frac{m+2}{2})$, where $U_n(x)$ is the $n$th Chebyshev polynomial of the second kind, evaluated at $x=\frac{m+2}{2}$. \end{enumerate} \end{corollary} \begin{proof} \begin{enumerate} \item This is the case $q=p=1$ of Proposition \ref{ppoo}. \item We let $g(n)$ denote the number of required words of length $n-1$. It is clear that $g(1)=1,$ and $g(2)=m+2$. At the beginning of each word of length $n+1$ put a letter of $\{0,1,\ldots,m+1\}$ to obtain $(m+2)g(n+1)$ words of length $n+2$. Exactly $g(n)$ of these words begin with $01$. Subtracting this number from $(m+2)g(n+1)$, we conclude that $g$ satisfies Recurrence (\ref{ek2}), which means that $g(n)=f_m(n),(n\geq 1)$. \item Equations (\ref{ek1}) and (\ref{ek2}) are the recurrence for the numbers $U_{n-1}(\frac{m+2}{2})$. \end{enumerate} \end{proof} We see that, for $m=1$, formula (\ref{ek2}) is the recurrence for Fibonacci numbers of even indices, that is $f_1(n)=F_{2n},(n=1,2,\ldots)$. We stress two particular results. The first concerns a relationship between Fibonacci numbers and Chebyshev polynomials of the second kind, and the second describes the restricted words counting by $F_{2n}$. \begin{remark} \begin{enumerate} \item For $n\geq 1$, we have \[F_{2n}=U_{n-1}\left(\frac 32\right).\] \item The number $F_{2n}$ equals the number of $01$-avoiding words of length $n-1$ over the alphabet $\{0,1,2\}$. \end{enumerate} \end{remark} \begin{remark}Some sequences in Sloane \cite{slo} generated by Recurrence (\ref{ek2}) are: \seqnum{A001906}, \seqnum{A001353}, \seqnum{A004254}, \seqnum{A001109}, \seqnum{A004187}, \seqnum{A001090}, \seqnum{A018913}, \seqnum{A004189}, \seqnum{A004190}, \seqnum{A004191}, \seqnum{A078362}, \seqnum{A007655}, \seqnum{A078364}, \seqnum{A077412}, \seqnum{A078366}, \seqnum{A049660}, \seqnum{A078368}, \seqnum{A075843}, \seqnum{A092499}, \seqnum{A077421}, \seqnum{A097778}. \end{remark} We finish our investigation with a result which gives a combinatorial interpretation in terms of restricted words for a class of the functions $f_m$, when $f_0$ satisfies a linear recurrence equation of the second order. \begin{proposition}\label{p1} Let $p>1$ and $q$ be integers such that $1\leq q\leq p$. Define $f_0$ recursively in the following way: \[f_0(1)=1,\;f_0(2)=p,\] and \[f_0(n+2)=(p-1)f_0(n+1)+(p-q)f_0(n),\;(n\geq 1).\] Then, for $m\geq 0$, we have \[f_m(1)=1, f_m(2)=m+p,\] and \begin{equation}\label{pq}f_m(n+2)=(m+p-1)f_m(n+1)+(m+p-q)f_m(n).\end{equation} \end{proposition} \begin{proof} We again apply Corollary \ref{pr2}. Clearly, $f_m(1)=1, f_m(2)=m+p$. Further we have \begin{gather*}a_{m+1}(1)=f_m(1)+a_m(1)=1+m+p-1=m+p,\\ a_{m+1}(2)=f_m(2)+a_m(2)-f_m(1)a_m(1)=\\m+p+m+p-q-m-p+1=m+1+p-q.\end{gather*} \end{proof} \begin{corollary} For $m\geq 0$, the number $f_m(n+1)$ from Proposition \ref{p1} equals the number of $ii$-avoiding words of length $n$ over the alphabet $\{0,1,\ldots,m+p-1\}$, for $i\in\{0,1,\ldots,q-1\}$. \end{corollary} \begin{proof} Let $g(n)$ be the number of required words of length $n$. We obviously have $g(0)=1,g(1)=m+p$. It remains to prove that $g(n)$ satisfies recurrence equation (\ref{pq}). There are $(m+p-q)g(n)$ words of length $n+2$ in which the first two letters are the same. The remaining words begin with two different letters. At the beginning of a word of length $n+1$ which begins with a letter $i$, put a letter $j\;(j\not=i)$ to obtain $(m+p-1)$ words of length $n+2$, the second letter of which is $i$. When $i$ runs over all elements of the alphabet, we obtain all words of length $n+2$ beginning with two different letters. Hence, \[g(n+2)=(m+p-1)g(n+1)+(m+p-q)g(n),(n\geq 0).\] We conclude that $g(n)=f_m(n+1),(n\geq 0)$. \end{proof} \begin{remark}Some sequences in Sloane \cite{slo} generated by the preceding corollary are: \seqnum{A000045}, \seqnum{A000129}, \seqnum{A126473} , \seqnum{A126501}, \seqnum{A126528}, \seqnum{A122391}, \seqnum{A180037}, \seqnum{A099842}, \seqnum{A003948}, \seqnum{A015451}, \seqnum{A003949}, \seqnum{A015453}, \seqnum{A003950}, \seqnum{A015454}, \seqnum{A003951}, \seqnum{A015455}, \seqnum{A003952}, \seqnum{A003953}, \seqnum{A015456}, \seqnum{A015457}, \seqnum{A003954}, \seqnum{A170732}, \seqnum{A170733}, \seqnum{A170734}. \end{remark} \begin{remark} Note that the first two sequences in the above remark are Fibonacci and Pell numbers. \end{remark} \begin{thebibliography}{9} \bibitem{slo1} M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, {\em Linear Algebra Appl.} {\bf 226/228}, (1996), 57--72. \bibitem{mil1} M. Janji\'c, Determinants and recurrence sequences, {\em J. Integer Seq.} {\bf 15} (2012), \href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Janjic/janjic42.html}{Article 12.3.5}. \bibitem{mp} M. Janji\'c and B. Petkovi\'c, A counting function generalizing binomial coefficients and some other classes of integers, {\em J. Integer Seq.} {\bf 17} (2014), \href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic/janjic45.html}{Article 14.3.5}. \bibitem{mil2} M. Janji\'c, A generating function for the numbers of insets, {\em J. Integer Seq.} {\bf 17} (2014), \href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic2/janjic53.html}{Article 14.9.7}. \bibitem{kos} T. Koshy, {\em Catalan Numbers with Applications}, Oxford University Press, 2009. \bibitem{rin} E. Munarini, M. Poneti, and S. Rinaldi, Matrix compositions, {\it FPSAC 2006: Formal Power Series and Algebraic Combinatorics}, San Diego, 2006, pp.~445--456. Available at \url{http://garsia.math.yorku.ca/fpsac06/papers/49.pdf}. \bibitem{slo} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 11B39. \noindent \emph{Keywords: } linear recurrence equation, composition, Fibonacci number, restricted word. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000073}, \seqnum{A000078}, \seqnum{A000079}, \seqnum{A000129}, \seqnum{A000244}, \seqnum{A001045}, \seqnum{A001076}, \seqnum{A001090}, \seqnum{A001109}, \seqnum{A001353}, \seqnum{A001401}, \seqnum{A001591}, \seqnum{A001592}, \seqnum{A001906}, \seqnum{A003480}, \seqnum{A003948}, \seqnum{A003949}, \seqnum{A003950}, \seqnum{A003951}, \seqnum{A003952}, \seqnum{A003953}, \seqnum{A003954}, \seqnum{A004187}, \seqnum{A004189}, \seqnum{A004190}, \seqnum{A004191}, \seqnum{A004254}, \seqnum{A005668}, \seqnum{A006130}, \seqnum{A006131}, \seqnum{A006190}, \seqnum{A007655}, \seqnum{A008616}, \seqnum{A008676}, \seqnum{A008677}, \seqnum{A015440}, \seqnum{A015441}, \seqnum{A015442}, \seqnum{A015443}, \seqnum{A015445}, \seqnum{A015446}, \seqnum{A015447}, \seqnum{A015451}, \seqnum{A015453}, \seqnum{A015454}, \seqnum{A015455}, \seqnum{A015456}, \seqnum{A015457}, \seqnum{A018913}, \seqnum{A020699}, \seqnum{A025192}, \seqnum{A025795}, \seqnum{A025839}, \seqnum{A028859}, \seqnum{A029144}, \seqnum{A029280}, \seqnum{A041025}, \seqnum{A041041}, \seqnum{A049660}, \seqnum{A052918}, \seqnum{A053404}, \seqnum{A054413}, \seqnum{A075843}, \seqnum{A077412}, \seqnum{A077421}, \seqnum{A078362}, \seqnum{A078364}, \seqnum{A078366}, \seqnum{A078368}, \seqnum{A079262}, \seqnum{A086347}, \seqnum{A092499}, \seqnum{A093138}, \seqnum{A097778}, \seqnum{A099842}, \seqnum{A104144}, \seqnum{A109707}, \seqnum{A119826}, \seqnum{A122189}, \seqnum{A122265}, \seqnum{A122391}, \seqnum{A125145}, \seqnum{A126473}, \seqnum{A126501}, \seqnum{A126528}, \seqnum{A145839}, \seqnum{A145840}, \seqnum{A145841}, \seqnum{A155020}, \seqnum{A161434}, \seqnum{A168082}, \seqnum{A168083}, \seqnum{A168084}, \seqnum{A170732}, \seqnum{A170733}, \seqnum{A170734}, \seqnum{A180033}, \seqnum{A180037}, \seqnum{A180167}, \seqnum{A209239}, \seqnum{A220469}, \seqnum{A220493}, and \seqnum{A249169}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 9 2014; revised version received January 30 2015; February 5 2015; February 25 2015. Published in {\it Journal of Integer Sequences}, May 17 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}