<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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&gt;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&gt;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&gt;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&gt;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,&amp;\text{if $i$ is odd};\\0,&amp;\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&gt;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,&amp; \text{if $1\leq i\leq k$;} \\0,&amp;\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 $&lt;k$ has a run of $k$ zeros.  Suppose that $n\geq k$.
We calculate $g(n+k-1;k),(n\geq 1)$. There are  $mg(n+k-2;k)$ words of length
$n+k-1$, beginning with a nonzero letter. The remaining words begin with $0$.
It is clear that there are  $mg(n+k-3;k)$ words beginning with an isolated zero.
In the same way, we have $mg(n+k-4;k)$ words beginning with the run of two isolates zeros, and so on.

Finally, there are $mg(n+1;k)$ words beginning  with $k-1$ successive zeros.
Hence, \[g(n+k-1;k)=m\sum_{i=1}^kg(n+k-1-i;k),(n\geq 1).\]
We see that $g(n;k)$ and $f_m(n+1;k)$ satisfy the same recurrence equation.
\end{proof}
\begin{remark}
In particular, the function $f_1(n+1;2)$ counts binary words with no adjacent zeros. It follows that $f_1(n+1;2)=F_{n+2}$. The case $k=3$ produces analogous property of Tribonacci numbers, and so on.
\end{remark}
\begin{remark}  Several sequences in Sloane \cite{slo} generated by $f_m$ form Corollary \ref{trib} are:
\seqnum{A000045}, \seqnum{A028859}, \seqnum{A155020},  \seqnum{A125145}, \seqnum{A086347}, \seqnum{A180033}, \seqnum{A180167}, \seqnum{A000073}, \seqnum{A119826}, \seqnum{A000078}, \seqnum{A209239}, \seqnum{A001591}, \seqnum{A001592}, \seqnum{A122189}, \seqnum{A079262}, \seqnum{A104144}, \seqnum{A122265}, \seqnum{A168082}, \seqnum{A168083}, \seqnum{A168084},
 \seqnum{A220469}, \seqnum{A220493}, \seqnum{A249169}.

\end{remark}
\section{Some results concerning Problem~\ref{prob2}}
We first derive a recursion for $f_m$ in the case when $f_0$ is a linear function of $i$.

\begin{proposition}\label{ppoo} If $p,q\not=0$ are arbitrary numbers, and   $f_0(i)=q(i-1)+p,(i\geq 1)$, then
\begin{equation}\label{ee1}f_m(1)=p,\;f_m(2)=q+p+mp^2,\end{equation}
\begin{equation}\label{ee2}f_m(n+2)=(mp+2)f_m(n+1)+(mq-mp-1)f_m(n),\;(n&gt;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&gt;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&gt;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}

                                                                                

</pre></body></html>