<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}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#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 \LARGE\bf Hessenberg Matrices and Integer Sequences \\
\vskip .1in
}
\vskip 1cm
\large {
Milan Janji\'c \\
Department of Mathematics and Informatics\\
 University of Banja Luka \\
Republic of Srpska \\
Bosnia and Herzegovina \\
\href{mailto:agnus@blic.net}{\tt agnus@blic.net}\\
}
\end{center}

\vskip .2 in

\centerline{\emph{Dedicated to the memory of Professor Veselin Peri\'c} }

\vskip .35in

\begin{abstract}
We consider a particular case of upper  Hessenberg matrices, in which
all subdiagonal elements are $-1.$ We investigate three type of
matrices related to polynomials, generalized Fibonacci numbers, and
special compositions of natural numbers.  We give the combinatorial
meaning of the coefficients of the characteristic polynomials of these
matrices.
\end{abstract}



\section{Introduction}
We investigate a particular case of upper  Hessenberg matrices, in which all subdiagonal elements are $-1.$
  Several mathematical objects may be represented as determinants of such matrices.
   We consider three type of  matrices related to polynomials, generalized Fibonacci numbers,
    and  a special kind of composition of natural numbers.
     Our objective is to find the combinatorial meaning of the  coefficients of the characteristic polynomials.

The  coefficients of the characteristic polynomials of matrices of the
first type, that is, the sums of principal minors, are related to some
binomial identities.

The characteristic polynomials of matrices of the second kind give, as
a particular case,  the so-called
convolved Fibonacci numbers defined by Riordan \cite{riordan}.

Coefficients of the characteristic polynomial of matrices of the third
kind  are connected with a special kind of composition of natural
numbers, in which there are two different types of ones.  These were  
introduced by Deutsch \cite{eme},
and studied by Grimaldi \cite{papa}.

We prove several formulas which generate a number of sequences in
Slonae's {\it Encyclopedia} \cite{slo}.

The following result about upper Hessenberg matrices, which may be
easily proved by induction,  will be used in this paper.

\begin{theorem}\label{t1} Let the matrix $P_n$ be defined by
\begin{equation}\label{mat}P_n= \left[\begin{array}{llllll} p_{1,1}&amp;p_{1,2}&amp;p_{1,3}&amp;\cdots&amp;p_{1,n-1}&amp;p_{1,n}\\
-1&amp;p_{2,2}&amp;p_{2,3}&amp;\cdots&amp;p_{2,n-1}&amp;p_{2,n}\\ 0&amp;-1&amp;p_{3,3}&amp;\cdots&amp;p_{3,n-1}&amp;p_{3,n}\\ \vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;\vdots&amp;\vdots\\
0&amp;0&amp;0&amp;\cdots&amp;p_{n-1,n-1}&amp;p_{n-1,n}\\ 0&amp;0&amp;0&amp;\cdots&amp;-1&amp;p_{n,n}\end{array}\right],\end{equation}
 and let the sequence $a_1,a_2,\ldots$ be defined by
\begin{equation}\label{niz}a_{n+1}=\sum_{i=1}^np_{i,n}a_i,\;(n=1,2,\ldots).\end{equation}
Then \[a_{n+1}=a_1\det
P_n,\;(n=1,2,\ldots).\]
\end{theorem}

The Fibonacci numbers are defined by
$F_0 = 0, F_1 = 1,$ and $F_n =
F_{n-1} + F_{n-2}$ for $n \geq 2$
Also, we use the  well-known fact that the coefficients of the
characteristic polynomial of a matrix are, up to the sign,
sums of principal minors of the matrix.

\section{Polynomials}
We start our investigations with Hessenbeg matrices whose determinants
are polynomials.


According to Theorem \ref{t1} we have
 \begin{proposition} Let the matrix $P_{n+1}$ be defined by:  \[P_{n+1}=\left[\begin{array}{rrrrrr}
1&amp;p_{1}&amp;p_{2}&amp;\cdots&amp;p_{n-1}&amp;p_{n}\\
-1&amp;x&amp;0&amp;\cdots&amp;0&amp;0\\
0&amp;-1&amp;x&amp;\cdots&amp;0&amp;0\\
\vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;\vdots&amp;\vdots\\
0&amp;0&amp;0&amp;\cdots&amp;x&amp;0\\
0&amp;0&amp;0&amp;\cdots&amp;-1&amp;x\end{array}\right].\]  Then
 \[\det P_{n+1}=x^n+p_1x^{n-1}+\cdots+p_n.\]
\end{proposition}

We let  $S_{n+1-k}(x)$ denote  the sum of all principal minors of order $n+1-k$ of $P_{n+1},$ where $k=0,\ldots,n,$ and $S_0=1.$
\begin{proposition}\label{pr1}  The following formulas are valid
 \begin{equation}\label{e1}S_{n+1-k}(x)={n\choose k-1}x^{n-k+1}+x^{n-k}\sum_{i=0}^{n-k}p_{i}{n-i\choose k}x^{-i},\;(k=0,1,2,\ldots,n).\end{equation}

\end{proposition}

\begin{proof}
For  $k=0$ equation (\ref{e1}) means that  $S_{n+1}=\det P_{n+1},$ which is clear.

If we delete  the first row and the first column of $P_{n+1}$ we
obtain a lower triangular matrix of order $n$ with $x$'s
on the main diagonal. Hence, all principal minors of order $n-k$
obtained by deleting  the first row and the first column of $P_{n+1}$
and another $k-1$ rows and columns with the same indices  are equal
to $x^{n-k+1}$.   There are  $n\choose k-1$ such minors. This gives
the first term in equation (\ref{e1}).

We shall next calculate the minor $M_{n+1-k}$ obtained by deleting the rows and columns with indices $2\leq m_1&lt;\cdots&lt;m_k\leq n+1.$
 By deleting  the $m$th row and the $m$th column of $P_{n+1},$ for $m&gt;1,$ we obtain an upper triangular block matrix
where  the upper block is $P_{m-1}$ and thus its determinant is  equal  $\sum_{i=0}^{m-2}p_ix^{m-2-i}.$ The lower block is
 a lower triangular matrix of order $n+1-m$ with $x$'s on the main diagonal.
 It follows that $M_{n+1-k}(x)=\sum_{i=0}^{m-2}p_ix^{m-2-i}x^{n-k-m+2}.$ For a fixed $m&gt;1$ there are ${n+1-m\choose k-1}$ such minors.

We thus obtain
\[S_{n+1-k}(x)={n\choose k-1}x^{n-k+1}+\sum_{m=2}^{n-k+2}\sum_{i=0}^{m-2}p_i{n-m+1\choose k-1}x^{n-k-i},\;(k=1,2,\ldots,n).\]
Changing the order of summation yields
\[S_{n+1-k}(x)={n\choose k-1}x^{n-k+1}+\sum_{i=0}^{n-k}p_ix^{n-k-i}\sum_{m=i+2}^{n-k+2}{n-m+1\choose k-1},\;(k=1,2,\ldots,n).\]
The corollary now holds  by the following  recurrence relation for binomial coefficients:
\[\sum_{i=0}^{n-k}{n-i\choose k}={n+1\choose k+1}.\]
\end{proof}

\begin{corollary} If
 $x=1,\;p_i=1,\;(i=0,1,\ldots,n)$ then
 \[S_{n+1}=n+1,\;S_{n+1-k}={n\choose k-1}+{n+1\choose k+1},\;(k=1,2,\ldots,n).\]
\end{corollary}

Several sequences from Sloane's OIES \cite{slo} are generated by the preceding formulas. We state some of them:
\seqnum{A000124},
\seqnum{A000217},
\seqnum{A001105},
\seqnum{A001845},
\seqnum{A004006},
\seqnum{A005744},
\seqnum{A005893},
\seqnum{A006522},
\seqnum{A017281},
\seqnum{A027927},
\seqnum{A056220},
\seqnum{A057979},
\seqnum{A080855},
\seqnum{A080856},
\seqnum{A080857},
\seqnum{A105163},
\seqnum{A121555},
\seqnum{A168050}.



\begin{corollary}\label{co1}
If
  $x\not=1,\;p_i=1,\;(i=1,\ldots,n)$ in (\ref{e1}) then
\[S_{n+1}(x)=\frac{x^{n+1}-1}{x-1},\;S_{n+1-k}(x)={n\choose k-1}x^{n-k+1}+\sum_{j=0}^{n-k}{k+j\choose k}x^j,\;(k=0,1,\ldots,n).\]
\end{corollary}

According to the  well-known binomial identity
\[{k+j\choose j}=(-1)^j{-k-1\choose j},\] we see that the second term
\[\sum_{j=0}^{n-k}{k+j\choose k}x^j,\] in the preceding equation  is the partial sum of the expansion of the function $\frac{1}{(1-x)^{k+1}}$ into powers of $x.$




The characteristic matrix $Q_{n+1}(t)$  of $P_{n+1}$ has the form
\[Q_{n+1}(t)=-\left[\begin{array}{rrrrrr}
1-t&amp;p_{1}&amp;p_{2}&amp;\cdots&amp;p_{n-1}&amp;p_{n}\\
-1&amp;x-t&amp;0&amp;\cdots&amp;0&amp;0\\
0&amp;-1&amp;x-t&amp;\cdots&amp;0&amp;0\\
\vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;\vdots&amp;\vdots\\
0&amp;0&amp;0&amp;\cdots&amp;x-t&amp;0\\
0&amp;0&amp;0&amp;\cdots&amp;-1&amp;x-t\end{array}\right].\]

This is also a Hessenberg matrix. If $f_{n+1}(t)$ is the characteristic polynomial of $P_{n+1}$ then
\[f_{n+1}(t)=\det(Q_{n+1}(t))=(-1)^{n+1}\left[\sum_{k=1}^{n}p_k(x-t)^{n-k}+(1-t)(x-t)^n\right].\]
We thus obtain
\begin{proposition} The following equation holds
\begin{equation}\label{kp}\sum_{k=0}^{n+1}(-1)^{n-k+1}S_{n-k+1}(x)t^k=(-1)^{n+1}\left[\sum_{k=1}^{n}p_k(x-t)^{n-k}+(1-t)(x-t)^n\right].\end{equation}
\end{proposition}
As a consequence we shall prove a curious binomial identity.

\begin{proposition} Let $m,n\;(0\leq m\leq n)$ be arbitrary integers. Then
\[\sum_{j=m}^n\sum_{k=0}^{n-j}(-1)^k{k+j\choose j}{j\choose m}=1.\]
\end{proposition}

\begin{proof}
Take $p_i=1,\;(i=0,\ldots,n),$ $t=1,$ and $x+1$ instead of $x$   in (\ref{kp}). The left side becomes
\[L=1+\sum_{k=0}^n(-1)^{n-k+1}\left[{n\choose k-1}(x+1)^{n-k+1}+\sum_{j=0}^{n-k}(-1)^{n-k+1}{k+j\choose j}(x+1)^j\right].\]

It is easily seen that
\[\sum_{k=0}^n(-1)^{n-k+1}{n\choose k-1}(x+1)^{n-k+1}=(-x)^n-1.\]
Therefore,
\[L=(-x)^n+\sum_{k=0}^n\sum_{j=0}^{n-k}\sum_{m=0}^j(-1)^{n-k+1}{k+j\choose j}{j\choose m}x^m.\]
Changing the order of summation we have
\[L=(-x)^n+\sum_{m=0}^n\left[\sum_{j=m}^{n}\sum_{k=0}^{n-j}(-1)^{n-k+1}{k+j\choose j}{j\choose m}\right]x^m.\]

The right side of (\ref{kp}) has the form
$R=(-1)^{n+1}(x^{n-1}+x^{n-2}+\cdots+1).$

In this way we obtain
\[\sum_{m=0}^n\left[\sum_{j=m}^{n}\sum_{k=0}^{n-j}(-1)^{n-k+1}{k+j\choose j}{j\choose m}\right]x^m=(-1)^{n+1}(x^n+x^{n-1}+\cdots+1).\]
The proposition follows by comparing coefficients of the same powers of $x$ in this equation.
\end{proof}

\section{Generalized Fibonacci Numbers}
 Consider the sequence recursively given by $l_1=1,l_2=x,l_{n+1}=yl_{n-1}+xl_n,\;(n&gt;2),$ and an  upper Hessenberg matrix $L_n$ of order $n$ defined by: \[L_n=\left[\begin{array}{rrrrrr} x&amp;y&amp;0&amp;\cdots&amp;0&amp;0\\ -1&amp;x&amp;y&amp;\cdots&amp;0&amp;0\\
0&amp;-1&amp;x&amp;\cdots&amp;0&amp;0\\ \vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;\vdots&amp;\vdots\\ 0&amp;0&amp;0&amp;\cdots&amp;x&amp;y\\ 0&amp;0&amp;0&amp;\cdots&amp;-1&amp;x\end{array}\right].\]

From Theorem \ref{t1} we obtain  \[\det L_n=l_{n+1},\;(n=1,2,\ldots).\]
 For $l_1=l_2=x=y=1$ we have  $l_{n+1}=f_{n+1},$ where $f_{n+1}$ is the $n+1$th Fibonacci number. The numbers $l_n$ are usually called generalized Fibonacci numbers.

 \begin{proposition}\label{pp} Let $S_{n-k},\;(k=0,1,\ldots,n-1)$ be the sum of all principal minors of $L_n$ of order $n-k.$ Then
\begin{equation}\label{snkk}S_{n-k}=\sum_{j_1+j_2+\cdots+j_{k+1}=n+1}l_{j_1}l_{j_2}\cdots l_{j_{k+1}},\end{equation}
where the sum is taken over  $j_t\geq
1,\;(t=1,2,\ldots,k+1).$ \end{proposition}
\begin{proof}

Principal minors of $L_n$ are some convolutions of $l_n.$ For example, the minor obtained by deleting the $i$th row and
the $i$th column of $L_n$ is obviously  equal to $l_{i}\cdot l_{n-i+1}.$ Therefore, the principal minor $M(i_1,i_2,\ldots,i_k)$ of $L_n$
obtained by deleting the rows and columns with indices $1\leq i_1&lt;i_2&lt;\cdots&lt;i_k\leq n$ is \[M(i_1,i_2,\ldots,i_k)=l_{i_1}\cdot
l_{i_2-i_1}\cdots l_{i_k-i_{k-1}}\cdot l_{n-i_k+1}.\]

Denoting $i_1=j_1,i_2-i_1=j_2,\ldots, i_k-i_{k-1}=j_k,n-i_k+1=j_{k+1}$ yields
\[M(i_1,i_2,\ldots,i_k)=l_{j_1}\cdot
l_{j_2}\cdots l_{j_k}\cdot l_{j_{k+1}},\]
where $j_t\geq 1,\;(t=1,2,\ldots,k+1),$ and $j_1+\cdots+j_{k+1}=n+1.$


 Summing over all  $1\leq i_1&lt;i_2&lt;\cdots&lt;i_k\leq n$ we obtain (\ref{snkk}).

\end{proof}

From Proposition \ref{pp} we easily derive the following known result for compositions of a natural number.
\begin{proposition}
The number  $c(n+1,k+1)$ of compositions of $n+1$ into $k+1$ parts is
\[c(n+1,k+1)={n\choose k}.\]
\end{proposition}
\begin{proof} Take specifically  $l_1=x=1,\;y=0.$ Then $L_n$ is a lower triangular matrix with $1$'s on the main diagonal. Therefore,
 all of its principal minors equal $1,$ and there are ${n\choose k}$ minors of order $n-k.$ It  follows that the sum (\ref{snkk})  equals $n\choose k$,
and that  all its summands are equal $1.$
On the other hand, this sum is taken over all compositions of $n+1$ into $k+1$ parts and the proposition follows.
\end{proof}
 In Riordan's book \cite{riordan} the sum on the right side  of (\ref{snkk}) for $x=y=1$ is called
a convolved Fibonacci number and is denoted by $f^{(k+1)}_{n-k+1}.$ Hence,

\begin{corollary} The convolved Fibonacci number $f^{(k+1)}_{n-k+1}$
 is equal, up to sign, to the coefficient of $t^k$ in the  characteristic polynomial $p_n(t)$ of $L_n,$ in the case $x=y=1.$
 \end{corollary}
The following result is an explicit formula for convolved Fibonacci numbers.
 \begin{corollary} Let $f^{(k+1)}_{n-k+1}$ denote the
convolved Fibonacci number. Then \[f^{(k+1)}_{n-k+1}=\sum_{i=0}^{\lfloor\frac{n-k}{2}\rfloor}{n-i\choose i}{n-2i\choose k}.\]
\end{corollary}
\begin{proof}

The characteristic matrix of $L_n$ has the form: \[\left[\begin{array}{rrrrrr} t-1&amp;1&amp;0&amp;\cdots&amp;0&amp;0\\ -1&amp;t-1&amp;1&amp;\cdots&amp;0&amp;0\\
0&amp;-1&amp;t-1&amp;\cdots&amp;0&amp;0\\ \vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;\vdots&amp;\vdots\\ 0&amp;0&amp;0&amp;\cdots&amp;t-1&amp;1\\ 0&amp;0&amp;0&amp;\cdots&amp;-1&amp;t-1\end{array}\right].\] It follows
that  $p_n(t)=f_{n+1}(t-1),$ where $f_{n+1}(t)$ is a Fibonacci polynomial. The corollary follows from the preceding corollary and the following
 explicit formula for Fibonacci polynomials:
 \[f_{n+1}(x)=\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}{n-i\choose i}x^{n-2i}.\]



\end{proof}


Since $f_{n+1}(1)=f_{n+1}$ we also  have the following identity for Fibonacci numbers:
\begin{corollary} For Fibonacci numbers
$f_n,\;(n=0,1,\ldots)$ we have \[f_{n+1}=(-1)^n\sum_{k=0}^n\sum_{i=0}^{\lfloor\frac{n-k}{2}\rfloor}(-2)^k{n-i\choose i}{n-2i\choose k}.\]
\end{corollary}

\begin{remark}  Taking particular values for $x$ and $y$ in the matrix $L_n$ we may obtain different kinds of generalized Fibonacci numbers. For example,
taking $x=y=1,$ and taking $3$ instead of $1$ in the upper left corner of
$L_n$ we obtain a matrix whose determinant is a Lucas number. In this case Proposition
\ref{pp} shows that the coefficients of the characteristic polynomial are convolutions between Fibonacci and Lucas numbers.
\end{remark}

Many of the sequences in Sloane's {\it Encyclopedia} are generated by the sums from
Proposition \ref{pp}. Here are some of them:
\seqnum{A000045},
\seqnum{A000129},
\seqnum{A001076},
\seqnum{A001628},
\seqnum{A001629},
\seqnum{A001872},
\seqnum{A006190},
\seqnum{A006503},
\seqnum{A006504},
\seqnum{A006645},
\seqnum{A023607},
\seqnum{A052918},
\seqnum{A054457},
\seqnum{A073380},
\seqnum{A073381}.
\seqnum{A077985},
\seqnum{A152881}.


\section{Particular Compositions of  Natural Numbers}

We shall now consider a type of  Hessenberg matrices whose
determinants are Fibonacci numbers with odd indices. This will lead us
to the  compositions of a natural number with two different types of
ones,
introduced by E. Deutsch in \cite{eme}.

 \begin{proposition}\label{pp2} Let $G_n$ be the matrix of order $n$ defined by: \[G_n=\left[\begin{array}{rrrrrr}
2&amp;1&amp;1&amp;\cdots&amp;1&amp;1\\ -1&amp;2&amp;1&amp;\cdots&amp; 1&amp;1\\ 0&amp;-1&amp;2&amp;\cdots&amp;1&amp;1\\ \vdots&amp;\vdots&amp;\vdots&amp;\ddots&amp;\vdots&amp;\vdots\\ 0&amp;0&amp;0&amp;\cdots&amp;2&amp;1\\
0&amp;0&amp;0&amp;\cdots&amp;-1&amp;2\end{array}\right].\] Then \[\det G_n=f_{2n+1}.\] \end{proposition}
 \begin{proof}  According to Theorem \ref{t1} we have \[a_1=1,a_2=2,\ldots,a_{n+1}=a_1+a_2+\cdots+a_{n-1}+ 2a_n,\;(n&gt;2).\]
It follows from Identity 2 in \cite{ben} that $a_{n+1}=f_{2n+1}.$
\end{proof}
 \begin{proposition}\label{pp1} Let $S_{n-k},\;(0\leq k\leq n)$ be the sum of all minors of order $n-k$ of $G_n.$  Then
\[S_{n-k}=\sum_{j_1+j_2+\cdots+j_{k+1}=n-k}f_{2j_1+1}f_{2j_2+1}\cdots f_{2j_{k+1}+1},\] where the sum is taken over  $j_t\geq
0,\;(t=1,2,\ldots,k+1).$ \end{proposition}
\begin{proof}

Let $M(i_1,i_2,\ldots,i_k)$ be the minor of order $n-k$ obtained by deleting the rows and columns with indices $1\leq i_1&lt;i_2&lt;\cdots&lt;i_k\leq
n.$ Then \[M=\det(G_{i_1-1})\cdot\det(G_{i_2-i_1-1})\cdots\det(G_{i_k-i_{k-1}-1})\cdot\det(G_{n-i_k}).\] Applying Proposition \ref{pp2}
we obtain \[M=f_{2(i_1-1)+1}f_{2(i_2-i_1-1)+1}\cdots f_{2(i_k-i_{k-1}-1)+1} f_{2(n-i_k)+1}.\] It follows that \[S_{n-k}=\sum_{1\leq i_1&lt;i_2&lt;\cdots&lt;i_k\leq
n}f_{2(i_1-1)+1}f_{2(i_2-i_1-1)+1}\cdots f_{2(i_k-i_{k-1}-1)+1} f_{2(n-i_k)+1}.\]
If we set \[i_1-1=j_1,i_2-i_1-1=j_2,\ldots,i_k-i_{k-1}-1=j_k,n-i_k=j_{k+1},\]we have

\[S_{n-k}=\sum_{j_1+j_2+\cdots+j_{k+1}=n-k}f_{2j_1+1}f_{2j_2+1}\cdots f_{2j_{k+1}+1},\] where the sum is taken over all  $j_t\geq
0,\;(t=1,2,\ldots,k+1).$ \end{proof}

For  compositions of $n$ in which there are two types of ones Grimaldi,
in his paper \cite{papa},  shows that its number is $f_{2n+1}.$

We let  $c_{n,k}$ denote the number of such compositions in which
exactly $k$ parts equal $0.$
 We finish the paper by showing that the number $S_{n-k},$ from the
 preceding proposition, is in fact equal to $c_{n-k,k}.$

 \begin{proposition} Let $n$ be a positive integer, and let $k$ be a nonnegative integer.  Then
\begin{equation}\label{cnk}c_{n,k}=\sum_{j_1+j_2+\cdots+j_{k+1}=n}f_{2j_1+1}f_{2j_2+1}\cdots f_{2j_{k+1}+1},\end{equation} where the sum is
taken over $j_t\geq 0,\;(t=1,2,\ldots,k+1).$ \end{proposition}
\begin{proof} We use induction with respect of $k.$
 The theorem is true for $k=0,$ according to the preceding proposition.

Assume the theorem is true for $k-1.$ The greatest  value of $j_{k+1}$ is $n,$ and is obtained for $j_1=j_2=\cdots=j_k=0.$ We thus
may write $(\ref{cnk})$ in the form:
\[c_{n,k}=\sum_{j=0}^{n}f_{2j+1}\sum_{j_1+j_2+\cdots+j_{k}=n-j}f_{2j_1+1}f_{2j_2+1}\cdots
f_{2j_{k}+1}.\]
By the induction hypothesis we have
\begin{equation}\label{cnk1}c_{n,k}=\sum_{j=0}^{n}f_{2j+1}\cdot
c_{n-j,k-1}.\end{equation}
Let $(i_1,i_2,\ldots)$ be a composition of $n$ with two different types of   ones and  exactly $k$ zeroes,  and let first index,
where 0 is a summand, be $i_p.$
 Then $(i_1,i_2,\ldots,i_{p-1})$ is a composition of $j=i_1+\cdots+i_{p-1}$ with no zeroes, and $(i_{p+1},\ldots)$ is a composition of $n-j$
with exactly $k-1$ zeroes. The number of such compositions is $f_{2j+1}\cdot c(n-j,k-1),$ which is a summand on the right side of (\ref{cnk1}).
In this way the sum on the right side of (\ref{cnk1}) counts all of the  required compositions.

 \end{proof}
This part of the paper is concerned with \seqnum{A030267}.

\section{Acknowledgments} I would like to thank the referees for  valuable comments.

\begin{thebibliography}{99}
\bibitem{ben} A. T. Benjamin and J. J. Quinn, \emph{Proofs that Really
Count,} MAA, 2003.


\bibitem{eme} E.  Deutsch, Advanced exercise H-641, \emph{ Fibonacci Quart.} \textbf{44} (2006), 188.

\bibitem{papa} R. P. Grimaldi, Compositions and the alternate Fibonacci
numbers, \emph{Congr. Numer.} \textbf{186} (2007), 81--96.


\bibitem{riordan}
 J. Riordan, \emph{Combinatorial Identities,}  Wiley, 1968.

\bibitem{slo}
 N. J. A. Sloane,  \emph{Online Encyclopedia of Integer Sequences},\\
 \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B39; Secondary 11C20.

\noindent \emph{Keywords: } Hessenberg matrix, generalized Fibonacci number, Fibonacci polynomial, composition of a natural number.

\bigskip
\hrule
\bigskip

\noindent 
(Concerned with sequences \seqnum{A000045},
\seqnum{A000124},
\seqnum{A000129},
\seqnum{A000217},
\seqnum{A001076},
\seqnum{A001105},
\seqnum{A001628},
\seqnum{A001629},
\seqnum{A001845},
\seqnum{A001872},
\seqnum{A004006},
\seqnum{A005744},
\seqnum{A005893},
\seqnum{A006190},
\seqnum{A006503},
\seqnum{A006504},
\seqnum{A006522},
\seqnum{A006645},
\seqnum{A017281},
\seqnum{A023607},
\seqnum{A027927},
\seqnum{A030267},
\seqnum{A052918},
\seqnum{A054457},
\seqnum{A056220},
\seqnum{A057979},
\seqnum{A073380},
\seqnum{A073381},
\seqnum{A077985},
\seqnum{A080855},
\seqnum{A080856},
\seqnum{A080857},
\seqnum{A105163},
\seqnum{A121555},
\seqnum{A152881},
\seqnum{A168050}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 31 2010;
revised version received  July 14 2010.
Published in {\it Journal of Integer Sequences}, July 16 2010.

\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>