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

\usepackage{enumerate}
\usepackage{breqn}
\newcommand \Conv{\mathit{C}}

\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 A Discrete Convolution on \\
\vskip .1in
the Generalized Hosoya Triangle}
\vskip 1cm
\large
\'Eva Czabarka\\
Department of Mathematics\\
University of South Carolina\\
Columbia, SC  29208 \\
USA\\
\href{mailto:czabarka@math.sc.edu}{\tt czabarka@math.sc.edu} \\
\ \\
Rigoberto Fl\'orez\\
Department of Mathematics and Computer Science\\
The Citadel\\
Charleston, SC  29409\\
USA \\
\href{mailto:rigo.florez@citadel.edu}{\tt rigo.florez@citadel.edu} \\
\ \\
Leandro Junes\\
Department of Mathematics, Computer Science and Information Systems\\
California University of Pennsylvania\\
California, PA   15419\\
USA\\
\href{mailto:junes@calu.edu}{\tt junes@calu.edu}
\end{center}

\vskip .2 in

\begin{abstract}
The \emph{generalized Hosoya triangle} is an arrangement of
numbers where each entry is a product of two generalized Fibonacci
numbers. We define a discrete convolution $\Conv$ based on the
entries of the generalized Hosoya triangle. We use $\Conv$ and
generating functions to prove that the sum of every $k$-th entry
in the $n$-th row or diagonal of generalized Hosoya triangle,
beginning on the left with the first entry, is a linear combination of
rational functions on Fibonacci numbers and Lucas numbers. A simple
formula is given  for a particular case of this convolution.
We also show that $\Conv$ summarizes several sequences in the OEIS.
As an application, we use our convolution to enumerate many
statistics in combinatorics.


\end{abstract}

\section{Introduction}
The Hosoya triangle \cite{florezHiguitaMuk, florezjunes, rflorezljunes, hosoya, koshy} consists of a triangular
array of numbers where each entry is a product of two
Fibonacci numbers (see Figure \ref{HosoyaRegular}). If we use generalized
Fibonacci numbers instead of Fibonacci numbers, then we
obtain the generalized Hosoya triangle. Several authors have been
interested in finite sums of products of Fibonacci numbers (see for
example, \cite{griffiths,koshy, moree}). The generalized
Hosoya triangle is a good visualizing tool for the study of sums of
products of generalized Fibonacci numbers, and in particular, for
the study of finite sums of products of Fibonacci numbers and Lucas numbers.

We define a discrete convolution $\Conv$ as a finite sum of products of
generalized Fibonacci numbers, and prove, using generating functions,
that it is a linear combination of five rational functions on Fibonacci
and Lucas numbers. The convolution depends on three variables
$m$, $l$, and $k$, each of them having a geometric interpretation in terms
of the generalized Hosoya triangle. Moreover, particular cases for the
variables $m$, $l$, and $k$ give known results found by several authors
\cite{griffiths,koshy, moree}. That is, our convolution generalizes
the study of finite sums of products of Fibonacci and Lucas numbers.
We also provide several examples where $\Conv$ enumerates statistics on
Fibonacci words and non-decreasing Dyck paths. In addition, our convolution
summarizes 15 distinct numeric sequences from \emph{The On-Line Encyclopedia 
of Integer Sequences}.

The known results that are generalized by our convolution are as follows:
in 2011 Griffiths \cite[Thm.~3.1]{griffiths}, using generating
functions, gave a closed formula for the sum of all
elements in the $n$-th diagonal of the Hosoya triangle. His result
can be deduced from our first main result, Theorem \ref{thm:main2},
by taking $m=n$, $l=2$, and $k=0$. Similarly, Moree \cite[Thm.~4]{moree} proves
that
\[ F_nF_1+F_{n-1}F_{2}+ \cdots + F_2F_{n-1}+F_{1}F_{n}=(nL_{n+1}+ 2F_{n})/5.\]
This identity is a particular case of our second main result, Theorem \ref{thm:main},
by taking $m=n$, $l=1$, and $k=0$.

Theorem \ref{thm:main} also relates the convolution $\Conv$ to several
counting results. In particular, $\Conv$ can be used to count the number of
elements in all subsets of $\{1, 2,\ldots,n\}$ with no consecutive integers,
the number of binary sequences of length $n$ with exactly one pair of
consecutive 1's, the total number of zeros in odd/even position for all
Fibonacci binary words of length $n$ and the total pyramid weight for all
non-decreasing Dyck paths of length $n$, (see Section
\ref{Enumerative_applications}).

In addition to these enumerative applications, the convolution $\Conv$
``compactifies" a wide variety of numeric sequences into a single definition.
The advantage of this ``compactification" is that it provides a single closed
formula (see Theorems \ref{thm:main2} and \ref{thm:main}) that might help in the
study of several sequences. The authors suspect (based on numerical computations)
that $\Conv$ summarizes more than the 15 sequences depicted in Table \ref{sloane}.


\section{Preliminaries and  examples}\label{preliminaries}
In this section we introduce notation and give some examples. We also give
some definitions that will be used throughout the paper, some of
which are well known, but we prefer to restate them here to
avoid ambiguities.
\subsection{The generalized Hosoya triangle}
We let $ \lbrace G_{n}(a,b) \rbrace _{n \in \mathbb{N}}$ denote the
\emph{generalized Fibonacci sequence} with integers $a$ and $b$. That
is,
\begin{equation}\label{generalizedfibonacci}
G_{1}(a,b)=a,  G_{2}(a,b)=b, \text{ and  } G_{n}(a,b)=G_{n-1}(a,b)+G_{n-2}(a,b) \text{ for all } n \in \mathbb{N} \setminus \{1,2\}.
\end{equation}

If there is no ambiguity with $a$ and $b$, then we let $G_n$ denote
the $n$-th term of the generalized
Fibonacci sequence, instead of $G_{n}(a,b)$. It is easy to see that $G_{n}(1,1)=F_{n}$.  The first eight terms of the generalized Fibonacci sequence with integers $a$ and $b$ are
\[ a, b, a + b, a + 2 b, 2 a + 3 b, 3 a + 5 b, 5 a + 8 b, \text{ and } 8 a + 13 b.\]

Notice that every element in this sequence is a linear combination of the integers $a$ and $b$ with Fibonacci coefficients. In general, we have that $G_{n} = a\,F_{n-2} + b\,F_{n-1}$ for all $n \in \mathbb{N}$. (See for example, \cite[Thm.~7.1, p.~109]{koshy}.)

The \emph{generalized
Hosoya sequence} $\left\{H_{a,b}(r,k)\right\}_{r \ge k\ge 1}$ is defined by the double recursion
\[ H_{a,b}(r,k)= H_{a,b}(r-1,k)+H_{a,b}(r-2,k) \]
\text{ and }
\[ H_{a,b}(r,k)= H_{a,b}(r-1,k-1)+H_{a,b}(r-2,k-2)\]
%
$\text { where  }  r>2 \text { and } 1\le k \le r \text{ with initial conditions }$
\[H_{a,b}(1,1)=a^2; \quad H_{a,b}(2,1)=ab; \quad H_{a,b}(2,2)= ab; \quad H_{a,b}(3,2)=b^2.\]
It is easy to see that if we let $a=b=1$ in the generalized
Hosoya sequence, then we obtain the regular Hosoya sequence $\left\{H(r,k)\right\}_{r \ge k\ge 1}$ as Koshy defined it \cite[p.~187--188]{koshy}. It is known that
\[H(r,k)= F_{k} \, F_{r-k+1}\]
for all natural numbers $r, k$ such that $k \le r$; see \cite[Ch.~15]{koshy}. This and Proposition \ref{prop:GenHos} show that the definition of $\left\{H_{a,b}(r,k)\right\}_{r \ge k\ge 1}$ is the right generalization for $\left\{H(r,k)\right\}_{r\ge k\ge 1}$.
\begin{proposition}[\cite{florezjunes}]\label{prop:GenHos} If $r$ and $k$ are natural numbers such that $ k \le r$, then
     \[H_{a,b}(r,k)= G_{k} \, G_{r-k+1},\]
for all integers $a, b \in \mathbb{Z}$.
\end{proposition}

The generalized Hosoya sequence gives rise to the
\emph{generalized Hosoya triangle} that is defined as a vertex-weighted grid graph
in the first quadrant of $\mathbb{R}^{2}$ as follows: consider the grid formed by all points in the first
quadrant of the $xy$-plane with natural numbers as coordinates. Every point/vertex
$(x,y) \in \mathbb{N} \times \mathbb{N}$ has weight $H_{a,b}(x+y-1,y)$. \label{gridhosoya} Figure \ref{HosoyaHs} depicts
a finite portion of the generalized Hosoya triangle where the view of perspective
is rotated 135$^{\circ}$ clockwise.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{Hosoya_Hs.eps}
\end{center}
\caption{Generalized Hosoya triangle for weights $H_{a,b}(r,k)$ with $1 \leq k \leq r \leq 6$.} \label{HosoyaHs}
\end{figure}

We define the \emph{$r$-th row of the generalized Hosoya triangle} as the collection of all
the weights
\[\{ H_{a,b}(r,1),H_{a,b}(r,2), \ldots, H_{a,b}(r,r-1),H_{a,b}(r,r)\}\]
with their corresponding vertices.

Proposition \ref{prop:GenHos} shows that every weight of the generalized
Hosoya triangle is the product of two generalized Fibonacci numbers. In
particular, if we use  Proposition \ref{prop:GenHos} for all entries of
Figure \ref{HosoyaHs}, we obtain Figure \ref{HosoyaFirst}.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=.55]{Hosoya_Gs.eps}
\end{center}
\caption{The first six rows of the generalized Hosoya triangle.} \label{HosoyaFirst}
\end{figure}

Thorough the rest of the paper we ignore the axes in any generalized Hosoya triangle figure.

We now give some examples of generalized Hosoya triangles. We can construct different triangles by fixing values for the integers $a$ and $b$. Fixing $a=b=1$ in (\ref{generalizedfibonacci}) we obtain the Fibonacci sequence
\[G_{1}= 1, \quad G_{2}=1,  \quad G_{3}=2,  \quad G_{4}=3,  \quad G_{5}=5,  \quad G_{6}=8,   \ldots \]
Substituting these values in Figure \ref{HosoyaFirst}, we obtain the regular Hosoya triangle.
(See \cite{florezHiguitaMuk,florezjunes, rflorezljunes, hosoya, koshy} and Figure \ref{HosoyaRegular}.)


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{HosoyaRegular.eps}
\end{center}
\caption{The first six rows of the regular Hosoya triangle.} \label{HosoyaRegular}
\end{figure}

Fixing $a=7$ and $b=2$ in (\ref{generalizedfibonacci})  we obtain the sequence
\[G_{1}= 7, \quad G_{2}=2,  \quad G_{3}=9,  \quad G_{4}=11,  \quad G_{5}=20,  \quad G_{6}=31,   \ldots \]
\noindent Substituting these values in Figure \ref{HosoyaFirst}, we obtain a
Hosoya triangle with $a=7$ and $b=2$. (See Figure \ref{Hosoya_Triangle_a_b} part  (a).)
Similarly, fixing  $a=5$ and  $b=8$ in (\ref{generalizedfibonacci})  we obtain another numerical sequence
\[G_{1}= 5, \quad G_{2}=8,  \quad G_{3}=13,  \quad G_{4}=21,  \quad G_{5}=34,  \quad G_{6}=55,  \ldots \]
The Hosoya triangle generated by this new sequence is depicted in Figure \ref{Hosoya_Triangle_a_b} part  (b).


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{Hosoya_Triangle_a_b_2.eps}
\end{center}
\caption{Two generalized Hosoya triangles.} \label{Hosoya_Triangle_a_b}
\end{figure}

\subsection{Discrete convolution on the generalized Hosoya triangle}

We let $\lceil x \rceil$ denote the ceiling or least integer function
of the real number $x$. We now define an operator $\Conv$ that will be called \emph{convolution},
that acts on the weights of
the generalized Hosoya triangle as follows: if $l, m>0$ and $k\ge 0$ are
integers, then
\begin{equation} \label{eqn:DefGenFib} \Conv_{a,b}(m,l,k)= \sum_{i=0}^{\left \lceil \frac{m}{l(k+1)} \right \rceil -1} G_{(k+1)i+1}(a,b) \cdot G_{m-l(k+1)i}(a,b).
\end{equation}
If there is no ambiguity with the integers $a$ and $b$, instead of (\ref{eqn:DefGenFib}),
 we write
\[ \Conv(m,l,k)= \sum_{i=0}^{\left \lceil \frac{m}{l(k+1)} \right \rceil -1} G_{(k+1)i +1}\cdot G_{m-l(k+1)i}. \]


The convolution $\Conv_{a,b}(m,l,k)$ summarizes several sums of products of
Fibonacci numbers, Lucas numbers, and has a geometric interpretation in
terms of the vertices of the generalized Hosoya triangle.

We begin the study of the convolution $\Conv$ by discussing some examples. We first notice that $\{ \Conv_{1,1}(m,1,0)\}_{m \in \mathbb{N}}$
is the sequence of Fibonacci numbers convolved with themselves. (See Sloane \seqnum{A001629} and \cite{moree}.) Indeed,
\[ \Conv_{1,1}(m,1,0)= \sum_{i=0}^{m -1} F_{i+1} \cdot F_{m-i} = F_{1} \, F_{m}+ F_{2} \, F_{m-1}+ \cdots +F_{m} \, F_{1}. \]
Similarly, $\{ \Conv_{1,3}(m,1,0)\}_{m \in \mathbb{N}}$ is the sequence of Lucas numbers convolved with themselves; see Sloane \seqnum{A004799}. In general, $\{ \Conv_{a,b}(m,1,0)\}_{m \in \mathbb{N}}$ is the sequence of generalized Fibonacci numbers convolved with themselves. That is, $\Conv_{a,b}(m,1,0)$ is the sum of all entries in the $m$-th row of the generalized Hosoya triangle. For instance, in  (\ref{mrow}) these are the entries  of the $m$-th row of the generalized Hosoya triangle.  \label{conv}
\begin{equation} \label{mrow}
G_{1}\,G_{m} \quad G_{2}\,G_{m-1}  \quad G_{3}\,G_{m-2} \quad \cdots \quad G_{m-2}\,G_{3} \quad G_{m-1}\,G_{2} \quad G_{m}\,G_{1}
\end{equation}

We consider examples of $\Conv_{a,b}(m,1,0)$ for some values of
$a, b$, and $m$. If we fix $a=b=1$ and $m=6$, then $\Conv_{1,1}(6,1,0)$
is the sum of all the weights of the $6$-th row of Figure \ref{HosoyaRegular}.
That is,
\[ \Conv_{1,1}(6,1,0)= \sum_{i=0}^{5} F_{i+1} \cdot F_{6-i} =8+5+6+6+5+8 = 38.\]

If we fix $a=7, b=2$, and $m=5$, then $\Conv_{7,2}(5,1,0)$
is the sum of all the weights of the $5$-th row of Figure \ref{Hosoya_Triangle_a_b} part (a). Therefore,
\[ \Conv_{7,2}(5,1,0)= \sum_{i=0}^{4} G_{i+1}(7,2) \cdot G_{5-i}(7,2) =140  +  22  + 81 + 22   + 140 = 405.\]

We now give an interpretation to the convolution $\Conv_{a,b}(m,1,k)$ for $k\geq 1$
and fixed numbers $a, b$, and $m$.
We first notice that
 \[ \Conv_{a,b}(m,1,1)= \sum_{i=0}^{\left \lceil \frac{m}{2} \right \rceil -1} G_{2i +1}\cdot G_{m-2i}.\]
That is, $\Conv_{a,b}(m,1,1)$ is the sum of all the weights in the $m$-th row of the generalized Hosoya triangle starting at
$G_{1}\,G_{m}$ and ``jumping" one vertex. (See (\ref{mrow}) for the $m$-th row of the generalized Hosoya triangle.) Similarly, it is easy to see that
\[ \Conv_{a,b}(m,1,2)= \sum_{i=0}^{\left \lceil \frac{m}{3} \right \rceil -1} G_{3i +1}\cdot G_{m-3i}. \]
That is, $\Conv_{a,b}(m,1,2)$ is the sum of all the weights in the $m$-th row of the generalized Hosoya triangle starting at
$G_{1}\,G_{m}$ and ``jumping" two vertices.
In general, the convolution  $\Conv_{a,b}(m,1,k)$ for $k \geq 1$, is the sum of all the weights in the $m$-th row of the
generalized Hosoya triangle starting at $G_{1}\,G_{m}$ and ``jumping" $k$ vertices. For instance, $\Conv_{1,1}(6,1,1)$ is the sum of the weights in the $6$-th row in Figure \ref{HosoyaRegular} starting at $F_{1}\,F_{6}=8$ and
jumping one vertex. That is, the convolution $\Conv_{1,1}(6,1,1)$ is the sum of
$8$, $6$, and $5$. So,
\[\Conv_{1,1}(6,1,1) = \displaystyle{\sum_{i=0}^{2} F_{2i+1} \cdot F_{6-2i}}= \displaystyle{8+ 6 + 5=19. }\]
 Similarly, $\Conv_{5,8}(6,1,2)$ is the sum of the weights in the $6$-th row in Figure \ref{Hosoya_Triangle_a_b} part (b) starting at $G_{1}\,G_{6}=275$ and jumping two entries. Therefore,
\[\Conv_{5,8}(6,1,2) = \displaystyle{\sum_{i=0}^{1} G_{3i+1} \cdot G_{6-3i}}= \displaystyle{275+273=548. }\]


Several sequences in Sloane \cite{integer2} are summarized by the convolution $\Conv_{a,b}(m,1,k)$. In particular,
the sequences
\[\{\Conv_{1,1}(2n,1,1)\}_{n \in \mathbb{N}}, \quad \{\Conv_{1,3}(2n,1,1)\}_{n \in \mathbb{N}}, \quad \{\Conv_{2,1}(2n,1,1)\}_{n \in \mathbb{N}}
\text{, \; and }\; \{\Conv_{1,1}(2n-1,1,1)\}_{n \in \mathbb{N}}\]
correspond to \seqnum{A001870}, \seqnum{A061171}, \seqnum{A203574}, and \seqnum{A030267}, respectively.

We now give an interpretation to the convolution $\Conv_{a,b}(m,l,0)$ for $l\geq 1$ and fixed numbers $a, b$, and $m$.
The convolution $\Conv_{a,b}(m,1,0)$ was already mentioned in page \pageref{conv} and
it is the sum of all the weights in the $m$-th row of the generalized Hosoya triangle. We consider the convolution $\Conv_{a,b}(m,2,0)$. It is easy to see that
\begin{equation}\label{conv:maindiag}
\Conv_{a,b}(m,2,0)= \sum_{i=0}^{\left \lceil \frac{m}{2} \right \rceil -1} G_{i +1}\cdot G_{m-2i}.
\end{equation}

We consider some particular values of $m$ to visualize (\ref{conv:maindiag}) in the generalized Hosoya triangle.
If we set $m=3$, $m=7$, and $m=10$ in (\ref{conv:maindiag}),
then

\begin{align}
  \Conv_{a,b}(3,2,0)&= \sum_{i=0}^{1} G_{i +1}\cdot G_{3-2i}=G_{1}\,G_{3}+G_{2}\,G_{1}, \label{diag1} \\
  \Conv_{a,b}(7,2,0)&= \sum_{i=0}^{3} G_{i +1}\cdot G_{7-2i}=G_{1}\,G_{7}+G_{2}\,G_{5}+G_{3}\,G_{3} + G_{4}\,G_{1}, \label{diag2}\\
  \Conv_{a,b}(10,2,0)&= \sum_{i=0}^{4} G_{i +1}\cdot G_{10-2i}=G_{1}\,G_{10}+G_{2}\,G_{8}+G_{3}\,G_{6} + G_{4}\,G_{4}
  +G_{5}\,G_{2}. \label{diag3}
\end{align}
The convolutions (\ref{diag1}), (\ref{diag2}), and (\ref{diag3}) are depicted in Figure \ref{HosoyaMainDiag}.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{HosoyaMainDiag.eps}
\end{center}
\caption{The convolutions $\Conv_{a,b}(3,2,0), \Conv_{a,b}(7,2,0)$, and $\Conv_{a,b}(10,2,0)$.} \label{HosoyaMainDiag}
\end{figure}

Notice that $\Conv_{a,b}(3,2,0), \Conv_{a,b}(7,2,0)$, and $\Conv_{a,b}(10,2,0)$
are the sums of all the weights over the main diagonals of the generalized
Hosoya triangle that begin at $G_{1} \, G_{3}, G_{1} \,G_{7}$, and
$G_{1} \,G_{10}$, respectively. In general, the convolution
$\Conv_{a,b}(m,2,0)$ for $m \geq 3$ is the sum of all the
weights over the line of the generalized Hosoya triangle
that passes through the vertices with coordinates $(m,1)$ and $(m-2,2)$.
If $m\in \{1,2\}$, then $\Conv_{a,b}(m,2,0)=G_{1} \,G_{m}$.

Some sequences in Sloane \cite{integer2} are summarized by the convolution $\Conv_{a,b}(m,2,0)$. In particular,
the sequences $\{\Conv_{1,1}(2n,2,0)\}_{n \in \mathbb{N}}$ and $\{\Conv_{1,1}(2n-1,2,0)\}_{n \in \mathbb{N}}$
correspond to \seqnum{A056014} and \seqnum{A094292}, respectively. Griffiths
\cite{griffiths} studied a particular case of $\Conv_{a,b}(m,2,0)$.
Indeed, \cite[Thm.~3.1]{griffiths} provides a closed formula for $\Conv_{1,1}(m,2,0)$.
That is,
\[ \Conv_{1,1}(m,2,0)=\frac{1}{2}\left( F_{m+3}-F_{2 \lfloor \frac{m}{2}
 \rfloor -\lfloor \frac{m-5}{2} \rfloor} \right). \]

We prove a more general result in this article. We give a closed formula for $\Conv_{a,b}(m,l,k)$
for all integers $a, b, m, l, k$ with $l,m>0$ and $k\ge 0$ (see Theorems \ref{thm:main2}
and \ref{thm:main}).


We now consider the convolution $\Conv_{a,b}(m,3,0)$ for fixed numbers $a, b$, and $m$. It is easy to see that
\begin{equation}\label{conv:maindiag2}
\Conv_{a,b}(m,3,0)= \sum_{i=0}^{\left \lceil \frac{m}{3} \right \rceil -1} G_{i +1}\cdot G_{m-3i}.
\end{equation}
We fix some particular values of $m$ to visualize (\ref{conv:maindiag2}) in the generalized Hosoya triangle.
If we set $m=3$, $m=7$, and $m=10$ in (\ref{conv:maindiag2}),
then
\begin{align}
  \Conv_{a,b}(3,3,0)&= \sum_{i=0}^{0} G_{i +1}\cdot G_{3-3i}=G_{1}\,G_{3}, \label{twodiag1} \\
  \Conv_{a,b}(7,3,0)&= \sum_{i=0}^{2} G_{i +1}\cdot G_{7-3i}=G_{1}\,G_{7}+G_{2}\,G_{4}+G_{3}\,G_{1}, \label{twodiag2}\\
  \Conv_{a,b}(10,3,0)&= \sum_{i=0}^{3} G_{i +1}\cdot G_{10-3i}=G_{1}\,G_{10}+G_{2}\,G_{7}+G_{3}\,G_{4} + G_{4}\,G_{1}. \label{twodiag3}
\end{align}
The convolutions (\ref{twodiag1}), (\ref{twodiag2}), and (\ref{twodiag3}) are depicted in Figure \ref{HosoyaSecondDiag}.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{HosoyaSecondDiag.eps}
\end{center}
\caption{The convolutions $\Conv_{a,b}(3,3,0), \Conv_{a,b}(7,3,0)$, and $\Conv_{a,b}(10,3,0)$.} \label{HosoyaSecondDiag}
\end{figure}

The convolutions $\Conv_{a,b}(7,3,0)$ and $\Conv_{a,b}(10,3,0)$ are the sums of all the weights
over the line of the generalized Hosoya triangle that is determined by the pair of points
$((7,1),(4,2))$ and $((10,1),(7,2))$, respectively. In general, the convolution
$\Conv_{a,b}(m,3,0)$ for $m \geq 4$ is the sum of all the weights over the line of the generalized Hosoya
triangle that passes through the points $(m,1)$ and $(m-3,2)$. If $m\in \{1,2,3\}$, then
$\Conv_{a,b}(m,3,0)=G_{1} \,G_{m}$.

We recall that in this paper the generalized Hosoya triangle as a grid is viewed in perspective and it is rotated 135$^{\circ}$ clockwise (see page \pageref{gridhosoya}). Notice that all lines in Figure \ref{HosoyaMainDiag}, when $l=2$,
have slope $-1/2$ and all lines in Figure \ref{HosoyaMainDiag}, when $l=3$, have slope $-1/3$. Figure \ref{HosoyaManyIncl} depicts $\Conv_{a,b}(10,l,0)$ for $l\in \{1,\ldots,4\}$.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{HosoyaManyIncl.eps}
\end{center}
\caption{The convolutions $\Conv_{a,b}(10,l,0)$ for $l\in \{1,\ldots,4\}$.} \label{HosoyaManyIncl}
\end{figure}

We can now interpret $\Conv_{a,b}(m,l,0)$ in terms of the generalized Hosoya
triangle for every $l \geq 1$. The convolution $\Conv_{a,b}(m,l,0)$
for $m \geq l+1$ is the sum of all the weights over the line that passes through the points $(m,1)$
 and $(m-l,2)$ in the generalized Hosoya triangle. If $m \in \{1,\ldots,l\}$, then
$\Conv_{a,b}(m,l,0)=G_{1} \,G_{m}$. In general, if $L'$ is the line passing
through the point $(m,1)$ with slope $-1/l$, then $\Conv_{a,b}(m,l,0)=\sum_{(x,y)\in L' \cap (\mathbb{N}\times\mathbb{N})} G_x\cdot G_y$, (see Figure \ref{HosoyaManyIncl}).
Notice that $L' \cap (\mathbb{N}\times\mathbb{N})$ is a non-empty
finite set of points (the point  $(m,1)$ is always an element of
$L' \cap (\mathbb{N}\times\mathbb{N})$)
and the points are pairs of natural numbers.

Since we already have a geometric interpretation of $\Conv_{a,b}(m,l,0)$
for $l \geq 1$, the geometric interpretation of $\Conv_{a,b}(m,l,k)$
for $k \geq 1$ follows easily. Indeed, $\Conv_{a,b}(m,l,k) =\sum_{(x,y)\in L'_k} G_x\cdot G_y$
where $L'_{k} \subseteq L' \cap (\mathbb{N}\times\mathbb{N}), (m,1) \in L'_k$,
and $ L'_{k}$ is obtained from $L' \cap (\mathbb{N}\times\mathbb{N})$ by jumping $k$ vertices starting
at $(m,1)$.  For instance, $\Conv_{a,b}(10,2,1)=\sum_{(x,y)\in L'_1} G_x\cdot G_y$
where $ L'_{1}=\{(10,1), (6,3), (2,5)\}$ (see Figure \ref{HosoyaManyIncl}). Thus,
\[\Conv_{a,b}(10,2,1)=G_{1}\,G_{10}+G_{3}\,G_{6}+G_{5}\,G_{2}.\]

Similarly, $\Conv_{a,b}(10,1,3)=\sum_{(x,y)\in L'_3} G_x\cdot G_y$ where
$ L'_{3}=\{(10,1), (6,5), (2,9)\}$ (see Figure~\ref{HosoyaManyIncl}). Therefore,

\[\Conv_{a,b}(10,1,3)=G_{1}\,G_{10}+G_{5}\,G_{6}+G_{9}\,G_{2}.\]


\section{A closed formula for $\Conv(m,l,k)$}

In this section, we give a closed formula to calculate the convolution
$\Conv(m,l,k)$ for $l>1$. We recall that $L_{n}$ represents the sequence of Lucas numbers. That is,
$L_0=2$, $L_1=1$, and $L_n=L_{n-1}+L_{n-2}$, with $n>1$.
Some authors have found some useful results to determine
the sums of  products of Fibonacci numbers.  For example,  Griffiths
\cite{griffiths} prove that the sum of the consecutive elements lying on the $n$-th
main diagonal of the Hosoya triangle is a combination of
Lucas and Fibonacci numbers (see Figure \ref{HosoyaMainDiag}).  In fact, his result can be calculated by $\Conv_{1,1}(m,2,0)$.
Using ordinary generating functions, he proved that
\begin{equation}\label{convl2}
\Conv_{1,1}(m,2,0)=\sum_{i=0}^{\lceil \frac{m}{2}\rceil-1} F_{i+1}F_{m-2i}=\frac{1}{2} \left(F_{m+3}- F_{2\lfloor{m/2}\rfloor- \lfloor{(m-5)/2}\rfloor}\right).
\end{equation}

Moree \cite{moree} gives another example. He proved that the sum of the
consecutive elements lying on the $n$-th row of the Hosoya triangle is a combination of
Lucas and Fibonacci numbers. Thus,
\begin{equation}\label{convl3}
\Conv_{1,1}(m,1,0) = \sum_{i=0}^{m-1}F_{i+1}F_{m-i}=\frac{mL_{m+1}+ 2F_{m}}{5}.
\end{equation}

Notice that equations (\ref{convl2}) and (\ref{convl3}) use regular Fibonacci numbers,
and their deduction follows from algebraic manipulations of basic generating functions.
In contrast, the deduction of the closed formula for $\Conv_{a,b}(m,l,k)$ requires extensive
calculations using generalized Fibonacci numbers. We use generating functions to
prove that the convolution is an average of five terms. Each of those terms
is a rational function on Lucas numbers.

We remind the reader of the following notation: let $\alpha$ and $\beta$ be the
positive and negative roots, respectively, of the quadratic equation
$x^{2}-x-1=0$. That is, $\alpha=(1+\sqrt{5})/2$, and
$\beta=(1-\sqrt{5})/2$. Note that $\alpha \beta=-1$. It is well known that
$F_{n}=(\alpha^{n}-\beta^{n})/\sqrt{5}$ and
$L_{n}=\alpha^{n}+\beta^{n}$ for all $n \in \mathbb{Z}$. (See for
example, \cite[Thms.~5.6 and 5.8]{koshy}.)

\begin{theorem}[\cite{koshy}] \label{thm:BinetFormula} If $c=a+(a-b)\beta$, $d=a+(a-b)\alpha$, and $n \in \mathbb{Z}$,
then
\[  G_{n}=\frac{c\alpha^{n} -d\beta^{n}}{\sqrt{5}}. \]
\end{theorem}

\begin{proposition}\label{prop:identities}If $k$, $r$, and $n$ are non-negative integers and $c=a+(a-b)\beta$, $d=a+(a-b)\alpha$, then
       \begin{enumerate}[(i)]
            \item $c^{2}\alpha^{n} + d^{2}\beta^{n} =a^{2}L_{n-4} + 2ab\,L_{n-3} +b^{2}L_{n-2} $,

            \item $\displaystyle{\sum_{n=0}^{\infty}G_{kn+r}\,x^{n}=\dfrac{1}{\sqrt{5}}
                  \left[ \dfrac{c\alpha^{r}}{1-\alpha^{k}\,x} -\dfrac{d\beta^{r}}{1-\beta^{k}\,x}   \right]}$,

            \item $\displaystyle{\sum_{n=0}^{\infty}G_{kn+r}\,x^{n}=\dfrac{G_{r}+(-1)^{k+1}G_{r-k}\,x}{1-L_{k}\,x+(-1)^{k}\,x^{2}}}$,

            \item If $k>0$, then $\displaystyle{\sum_{n=0}^{\infty}\dfrac{F_{k(n+1)}}{F_{k}}\,x^{n}=\dfrac{1}{1-L_{k}\,x+(-1)^{k}\,x^{2}}}$.
       \end{enumerate}
\end{proposition}

\begin{proof} We prove part (i) by induction on $n$. Let $S(n)$ be the statement
\[a^{2}L_{n-4} + 2ab\,L_{n-3} +b^{2}L_{n-2}=c^{2}\alpha^{n} + d^{2}\beta^{n}\]
for a non-negative integer $n$. It is easy to see that $S(0)$ and
$S(1)$ are true. We suppose that $S(n-1)$ and $S(n)$ are true for a
fixed integer $n \geq 2$ and prove that $S(n+1)$ is true. It is easy
to see that using the recursive definition of Lucas numbers, $S(n-1)$, and $S(n)$
we obtain
\begin{eqnarray*}
 a^{2}L_{n-3} + 2ab\,L_{n-2} +b^{2}L_{n-1}&=&(c^{2}\alpha^{n} + d^{2}\beta^{n})+(c^{2}\alpha^{n-1}
                        + d^{2}\beta^{n-1})\\
                        &=&c^{2}\alpha^{n-1}(\alpha+1)+d^{2}\beta^{n-1}(\beta+1)\\
                        &=&c^{2}\alpha^{n+1} + d^{2}\beta^{n+1}.
\end{eqnarray*}
Thus, $S(n+1)$ is true.

We now prove part (ii). Using Theorem \ref{thm:BinetFormula}, we can see that
\[ \sum_{n=0}^{\infty}G_{kn+r}\,x^{n}=
    \sum_{n=0}^{\infty} \dfrac{c\alpha^{kn+r} -d\beta^{kn+r}}{\sqrt{5}}\,x^{n}=
    \dfrac{1}{\sqrt{5}} \left[ c\alpha^{r}\sum_{n=0}^{\infty}(\alpha^{k}x)^{n}
    - d\beta^{r}\sum_{n=0}^{\infty}(\beta^{k}x)^{n} \right].
\]
The proof now follows by noticing that $\sum_{n=0}^{\infty}y^{n}=\dfrac{1}{1-y}$.

We prove part (iii). Using part (ii), we can write
\[ \sum_{n=0}^{\infty}G_{kn+r}\,x^{n}=\dfrac{1}{\sqrt{5}} \left[  \dfrac{c\alpha^{r}}{1-\alpha^{k}x} - \dfrac{d\beta^{r}}{1-\beta^{k}x} \right] =\dfrac{1}{\sqrt{5}}\left[
    \dfrac{c\alpha^{r} -d\beta^{r} +(d\beta^{r}\alpha^{k} -
    c\alpha^{r}\beta^{k})\,x}{1-(\alpha^{k} +\beta^{k})x + (\alpha
    \beta)^{k}\,x^{2}}  \right].
\]
Since $L_{k}=\alpha^{k} +\beta^{k}$ and  $\alpha \beta=-1$, we
obtain that
\begin{align*}
    \sum_{n=0}^{\infty}G_{kn+r}\,x^{n} &= \dfrac{1}{\sqrt{5}}
    \left[ \dfrac{c\alpha^{r} -d\beta^{r} + (d\beta^{r}\alpha^{k} -
    c\alpha^{r}\beta^{k})\,x}{1-L_{k}x + (-1)^{k}\,x^{2}}  \right]\\
    &= \dfrac{1}{\sqrt{5}}\left[  \dfrac{c\alpha^{r} -d\beta^{r} -
    (\alpha \beta)^{k} (c\alpha^{r-k} - d\beta^{r-k})\,x}{1-L_{k}x +
    (-1)^{k}\,x^{2}}  \right].
\end{align*}
The proof now follows by Theorem \ref{thm:BinetFormula}.

We now prove part (iv). Using part (iii) with $a=b=1$ and $r=0$ we can easily see that
\[  \sum_{n=0}^{\infty}F_{kn}\,x^{n}=
    \dfrac{F_{0}+(-1)^{k+1}F_{-k}\,x}{1-L_{k}\,x+(-1)^{k}\,x^{2}}
    = \dfrac{F_{k}\,x}{1-L_{k}\,x+(-1)^{k}\,x^{2}} \; .
\]
Dividing on both sides of this equality by
$F_{k}\,x$, part (iv) follows.
\end{proof}

\begin{lemma}\label{for:mainthm}
If $k\ge 0$ and $l>0$ are integers, then every natural
number $m$ can be written in the form $m=l (k+1)n+r$ where $n\in \mathbb{Z}_{\ge 0}$ and $0<r\le l (k+1)$. Moreover,
\[n=\left\lceil\frac{m}{l (k+1)}-1\right\rceil \quad \text{ and } \quad
r=m-\left\lceil \dfrac{m}{l (k+1)} -1 \right\rceil l (k+1). \]
\end{lemma}

\begin{proof}
Using the division algorithm with $m$ and $l (k+1)$, there are $n' \in \mathbb{N}$
and $r' \in \mathbb{Z}_{\ge 0}$ such that $m=l (k+1)n' +r'$ where $0\leq r'< l (k+1)$. If $r' >0$,
then we can take $n=n'$ and $r=r'$. Thus, it is clear that $m=l (k+1)n+r$ and $0<r<l (k+1)$.

If $r'=0$, then $m=l (k+1)n'=l (k+1)(n'-1)+l (k+1)$. Taking $n=n'-1$ and $r=l (k+1)$ we obtain that
$m=l (k+1)n+r$ with $0<r\le l (k+1)$.

For the moreover part, we assume that
$m=l (k+1)n+r$ where $n \in \mathbb{Z}_{\ge 0}$ and $0<r \leq l (k+1)$. Therefore,
\begin{equation}\label{mainlemma}
   r=m-l (k+1)n.
\end{equation}
Thus,
$0<m-l (k+1)n\le l (k+1)$. This shows that $\dfrac{m}{l (k+1)}-1\le n < \dfrac{m}{l (k+1)}$. Therefore,
$n=\left\lceil\frac{m}{l (k+1)}-1\right\rceil$. This and  (\ref{mainlemma}) prove the Lemma.
\end{proof}

We now introduce some notation and definitions needed for
Theorem \ref{thm:main2}. Suppose that $m>0$, $k \ge 0$, and $l>1$ are integers. If

\[
\begin{array}{lll}
 n=\left\lceil\dfrac{m}{l (k+1)}-1\right\rceil ;   		& r=m- l(k+1)n; 	 	\\
 w_{1}=(k+1)(n-l+1) +(r+1);  	\quad \quad  \quad	& w_{2}=m+1;    	\\
 w_{3}=(k+1)n +(r+1);     					 	& w_{4}=m+l(k+1)-k; \\
 w_{5}=(k+1)(n+1)-(k+r);                              		 	& w_{6}=m+l(k+1) +k; \\
 w_{7}=(k+1)(n+l+1)-(r-1); 					& w_{8}=m-1,
\end{array}
\]
  then we define
  \[
\begin{array}{lll}
 	S_{1}&=cd \left[\dfrac{(-1)^{k+r}L_{w_{5}}-L_{w_{6}}+(-1)^{r}L_{w_{7}}+
  			(-1)^{l(k+1)}L_{w_{8}}}{(-1)^{k+1} + (-1)^{l(k+1)} - L_{(l+1)(k+1)}} \right],  \\ \\
 	S_{2} &=  \dfrac{ a^{2}L_{w_{3}-4} + 2abL_{w_{3}-3} + b^{2}L_{w_{3}-2}}
	                                     { (-1)^{(l+1)(k+1)}-L_{(l-1)(k+1)}+1},\\ \\
       S_{3} &= \dfrac{ a^{2}L_{w_{1}-4} + 2abL_{w_{1}-3} + b^{2}L_{w_{1}-2}}
	                                   { -1+ (-1)^{(l+1)(k+1)} \left(L_{(l-1)(k+1)}-1\right)},\\ \\	
\end{array}
\]	                                     	
 \[
\begin{array}{lll}	                                     				
  	S_{4} &= \dfrac{ a^{2}L_{w_{4}-4} + 2abL_{w_{4}-3}+ b^{2}L_{w_{4}-2} }
	                                    {(-1)^{l(k+1)+k} + L_{(l-1)(k+1)}-1}, \\ \\
   	S_{5} &=  \dfrac{ a^{2}L_{w_{2}-4} + 2abL_{w_{2}-3} + b^{2}L_{w_{2}-2}}
	             {(-1)^{(l+1)(k+1)} + (-1)^{l(k+1)+k} L_{(l-1)(k+1)}+ 1}.
\end{array}
\]


\begin{theorem} \label{thm:main2} If $S_{1}, S_{2},  S_{3}, S_{4}, \text{ and  } S_{5} $ are as above,  then
\[
\Conv(m,l, k) = \dfrac{S_{1} + S_{2} + S_{3} + S_{4} + S_{5}}{5} .
\]
\end{theorem}

\begin{proof} We prove the theorem by finding the generating
function of the sequence $\Conv(m,l,k)$ with fixed  positive integers $k$ and $l$.  We
use Lemma \ref{for:mainthm} to simplify computations. That is,
we let  $m=l(k+1)n+r$ where $n\in \mathbb{Z}_{\ge 0}$ and $0<r\le l(k+1)$.

We consider the generating function of the sequence
$\left\{\Conv \left(l(k+1)n+r,l,k\right) \right\}_{n =0}^{\infty}$ for fixed numbers $r$, $l$, and $k$.
Using the definition of $\Conv(m,l,k)$ one can see that
\[ \Conv \left(l(k+1)n+r,l,k\right) = \sum_{i=0}^{n}G_{(k+1)i +1} \cdot G_{l(k+1)(n-i) + r}.\]
Therefore,
\[
    \sum_{n=0}^{\infty}\Conv\left(l(k+1)n+r,l,k\right)\, x^{n} = \left(
    \sum_{n=0}^{\infty} G_{(k+1)n+1}\, x^{n} \right) \cdot \left(
    \sum_{n=0}^{\infty} G_{l(k+1)n+r}\, x^{n} \right).
\]
This and Proposition \ref{prop:identities} part (ii) imply that the
formal power series
\[\sum_{n=0}^{\infty}\Conv \left(l(k+1)n+r,l,k\right)\, x^{n}\]
 is equal to
\begin{dmath}\label{eq:long}
	\dfrac{1}{5} \left[ \dfrac{c^{2} \alpha^{r+1}}{ \left(1-\alpha^{k+1}x\right) \left (1-\alpha^{l(k+1)}x \right)} +
	\dfrac{d^{2} \beta^{r+1}}{\left(1-\beta^{k+1}x\right) \left(1-\beta^{l(k+1)}x\right)}  +
	cd \left( \dfrac{ \beta^{r-1}}{ \left(1-\alpha^{k+1}x \right) \left(1-\beta^{l(k+1)}x\right)} +
	\dfrac{ \alpha^{r-1}}{\left(1-\beta^{k+1}x \right) \left(1-\alpha^{l(k+1)}x \right)}\right) \right].
\end{dmath}
We consider the term
$\dfrac{ \beta^{r-1}}{(1-\alpha^{k+1}x)(1-\beta^{l(k+1)}x)}$ of (\ref{eq:long}).
Using partial fractions and $\sum_{n=0}^{\infty}x^{n}=1/(1-x)$, one can easily see that
\begin{align*}
	\dfrac{ \beta^{r-1}}{\left(1-\alpha^{k+1}x\right) \left(1-\beta^{l(k+1)}x\right)} &
	=  \dfrac{\beta^{r-1}}{\alpha^{k+1}-\beta^{l(k+1)}} \left[ \dfrac{\alpha^{k+1}} {1-\alpha^{k+1}x } - \dfrac{\beta^{l(k+1)}} {1-\beta^{l(k+1)}x } \right]\\
                          							   & =  \dfrac{\beta^{r-1}}{\alpha^{k+1}-\beta^{l(k+1)}}  \left[\alpha^{k+1} \sum_{n=0}^{\infty} \alpha^{n(k+1)}x^{n} - \beta^{l(k+1)} \sum_{n=0}^{\infty} \beta^{l (k+1)n}x^{n} \right]\\
							   			   &= \sum_{n=0}^{\infty}\beta^{r-1}\left( \dfrac{\alpha^{(k+1)(n+1)}- \beta^{l(k+1)(n+1)}}{\alpha^{k+1}-\beta^{l(k+1)}}\right)\,x^{n}.
\end{align*}
That is,
\begin{equation}\label{formulaa}
\dfrac{ \beta^{r-1}}{ \left(1-\alpha^{k+1}x\right) \left(1-\beta^{l(k+1)}x\right)} =  \sum_{n=0}^{\infty}\beta^{r-1}\left( \dfrac{\alpha^{(k+1)(n+1)}- \beta^{l(k+1)(n+1)}}{\alpha^{k+1}-\beta^{l(k+1)}}\right)\,x^{n}.
\end{equation}

Similarly, we get that
\begin{equation}\label{formulab}
  \dfrac{ \alpha^{r-1}}{ \left(1-\beta^{k+1}x\right) \left(1-\alpha^{l(k+1)}x\right)} =
    \sum_{n=0}^{\infty}\alpha^{r-1}\left( \dfrac{\beta^{(k+1)(n+1)}- \alpha^{l(k+1)(n+1)}}{\beta^{k+1}-\alpha^{l(k+1)}}\right)\,x^{n}.
\end{equation}

To simplify notation, we use $u=k+1$, $t=n+1$,  $v=k+r$, $s=t+l$, and $z=r-1$. Now, from (\ref{formulaa}) and (\ref{formulab}) we  have that
	\[ \dfrac{\beta^{r-1}}{ \left(1-\alpha^{u}x\right) \left(1-\beta^{lu}x\right)} +
	 \frac{\alpha^{r-1}}{ \left(1-\beta^{u}x \right) \left(1-\alpha^{lu}x \right)}\]
is equal to

\begin{align*}
	& \phantom{=} \sum_{n=0}^{\infty} \left[  \beta^{z}\left( \dfrac{\alpha^{ut}- \beta^{lut}}{\alpha^{u}-\beta^{lu}}\right) +
	 \alpha^{z}\left( \dfrac{\beta^{ut}- \alpha^{lut}}{\beta^{u}-\alpha^{lu}}\right) \right]\,x^{n} \\
	& =\sum_{n=0}^{\infty}  \left[  \frac{\beta^{z} \left( \alpha^{ut}- \beta^{lut} \right) \left( \beta^{u}-\alpha^{lu} \right) +
	\alpha^{z} \left( \beta^{ut}- \alpha^{lut}\right) \left( \alpha^{u}-\beta^{lu}\right)}{\left( \alpha^{u}-\beta^{lu} \right) \left( \beta^{u}-\alpha^{lu} \right)} \right] x^{n} \\
	& = \sum_{n=0}^{\infty} \frac{ \left( \beta^{v}\alpha^{ut} + \alpha^{v}\beta^{ut} \right) -\left( \beta^{lut +v} +
	\alpha^{lut +v} \right)-\left( \beta^{z}\alpha^{us}  + \alpha^{z}\beta^{us} \right)+
	\left(\beta^{lut+z} \alpha^{lu} +\alpha^{lut+z} \beta^{lu}\right)}{(-1)^{u} - \left( \alpha^{(l+1)u} + \beta^{(l+1)u} \right)+ (-1)^{lu}}x^{n} \\
	& = \sum_{n=0}^{\infty} \frac{(\alpha \beta)^{v} \left(  \alpha^{ut-v}  +
	 \beta^{ut-v}\right) -L_{lut+v}-(\alpha \beta)^{z}\left( \alpha^{us-z}  +
	 \beta^{us-z}\right)+(\alpha \beta)^{lu} \left( \alpha^{lun+z} +\beta^{lun+z}\right) }{(-1)^{u}+(-1)^{lu} -L_{(l+1)u}}x^{n} \\
	& = \sum_{n=0}^{\infty} \frac{(-1)^{v}L_{ut-v}-L_{lut+v}-(-1)^{z} L_{us-z}+
	(-1)^{lu}L_{lun+z}}{(-1)^{u}+(-1)^{lu} -L_{(l+1)u}}x^{n}\\
	&= \sum_{n=0}^{\infty} \frac{S_{1}}{cd} \, x^{n}.
\end{align*}
Thus,
\begin{equation}\label{formulac}
	 \sum_{n=0}^{\infty} \dfrac{S_{1}}{cd} \, x^{n}=\dfrac{ \beta^{r-1}}{\left(1-\alpha^{k+1}x \right) \left(1-\beta^{l(k+1)}x\right)} +
 	\dfrac{ \alpha^{r-1}}{\left(1-\beta^{k+1}x\right) \left(1-\alpha^{l(k+1)}x\right)}.
\end{equation}
We now consider the terms
\[
\dfrac{c^{2} \alpha^{r+1}}{(1-\alpha^{k+1}x)(1-\alpha^{l(k+1)}x)}
	 \quad \text{ and } \quad
\dfrac{d^{2} \beta^{r+1}}{ \left(1-\beta^{k+1}x \right) \left(1-\beta^{l(k+1)}x \right)}
\]
 of (\ref{eq:long}).
Using partial fractions and
$\sum_{n=0}^{\infty}x^{n}=1/(1-x)$, one can easily write
\begin{eqnarray}
\frac{c^{2} \alpha^{r+1}}{ \left(1-\alpha^{k+1}x \right) \left(1-\alpha^{l(k+1)}x \right)}
	= &\displaystyle{\sum_{n=0}^{\infty}c^{2}\frac{\alpha^{ut+r+1} - \alpha^{lut+r+1}}{\alpha^{u}-\alpha^{lu}}\, x^{n} \text{ and}} \label{formulad}\\
\frac{d^{2} \beta^{r+1}}{(1-\beta^{k+1}x)(1-\beta^{l(k+1)}x)}
	= &\displaystyle{\sum_{n=0}^{\infty}d^{2}\frac{\beta^{ut+r+1} - \beta^{lut+r+1}}{\beta^{u}-\beta^{lu}}\, x^{n}.} \label{formulae}
\end{eqnarray}

To simplify notation, we use $y=r+1$. From (\ref{formulad}) and (\ref{formulae}) we have that
\[
	\dfrac{c^{2} \alpha^{r+1}}{(1-\alpha^{k+1}x)(1-\alpha^{l(k+1)}x)} +
	\dfrac{d^{2} \beta^{r+1}}{(1-\beta^{k+1}x)(1-\beta^{l(k+1)}x)}
\]
is equal to

\begin{align*}
& \sum_{n=0}^{\infty} \frac{c^{2} \left( \alpha^{ut+y} - \alpha^{lut+y} \right) \left( \beta^{u}-\beta^{lu} \right)
  +d^{2} \left( \beta^{ut+y} - \beta^{lut+y} \right) \left( \alpha^{u}-\alpha^{lu}\right) }{ \left( \alpha^{u}-\alpha^{lu} \right) \left( \beta^{u}-\beta^{lu} \right)}\, x^{n} \\
& = \sum_{n=0}^{\infty} \left[ \frac{ \left(c^{2}\alpha^{ut+y} \beta^{u} + d^{2}\beta^{ut+y} \alpha^{u}  \right) -
\left(c^{2}\alpha^{lut+y} \beta^{u} + d^{2}\beta^{lut+y} \alpha^{u}  \right)}{ \left( \alpha \beta \right)^{u} +
 \left( \alpha \beta \right)^{lu} - \left( \alpha^{u}\beta^{lu} + \alpha^{lu}\beta^{u} \right)}    \,+    \right. \\
&\phantom{------}  \left.  \frac{-\left( c^{2}\alpha^{ut+y} \beta^{lu} + d^{2}\beta^{ut+y} \alpha^{lu} \right) +
 \left( c^{2}\alpha^{lut+y} \beta^{lu} + d^{2}\beta^{lut+y} \alpha^{lu} \right)}{\left( \alpha \beta \right)^{u} +
 \left( \alpha \beta \right)^{lu} - \left( \alpha^{u}\beta^{lu} + \alpha^{lu}\beta^{u} \right)}\, \right] x^{n}  \\
& = \sum_{n=0}^{\infty}   \left[ \frac{ \left( \alpha \beta \right)^{u} \left(c^{2}\alpha^{u(t-1)+y} +
 d^{2}\beta^{u(t-1)+y}  \right) - \left( \alpha \beta \right)^{u} \left(c^{2}\alpha^{u(lt-1)+y}  +
 d^{2}\beta^{u(lt-1)+y}  \right)}{ \left( \alpha \beta \right)^{u} + \left( \alpha \beta \right)^{lu} -
 \left( \alpha \beta \right)^{u} \left( \beta^{(l-1)u} + \alpha^{(l-1)u} \right)} \,+     \right. \\
&\phantom{----}   \left.    \frac{-\left( \alpha \beta \right)^{lu}\left( c^{2}\alpha^{u(t-l)+y} +
d^{2}\beta^{u(t-l)+y}  \right) + \left( \alpha \beta \right)^{lu}\left( c^{2}\alpha^{lu(t-1)+y} +
d^{2}\beta^{lu(t-1)+y}  \right)}{\left( \alpha \beta \right)^{u} + \left( \alpha \beta \right)^{lu} -
\left( \alpha \beta \right)^{u} \left( \beta^{(l-1)u} + \alpha^{(l-1)u} \right)}\,  \right]   x^{n}\\
& = \sum_{n=0}^{\infty}  \left[  \frac{ \left( -1 \right)^{u} \left(c^{2}\alpha^{u(t-1)+y} +
d^{2}\beta^{u(t-1)+y}  \right) - \left( -1 \right)^{u} \left(c^{2}\alpha^{u(lt-1)+y}  +
d^{2}\beta^{u(lt-1)+y}  \right)}{ \left( -1 \right)^{u} + \left( -1 \right)^{lu} -
 \left( -1 \right)^{u} \left( \beta^{(l-1)u} + \alpha^{(l-1)u} \right)} \,+    \right. \\
&\phantom{----} \left.  \frac{-\left( -1 \right)^{lu}\left( c^{2}\alpha^{u(t-l)+y} + d^{2}\beta^{u(t-l)+y}  \right) +
 \left( -1 \right)^{lu}\left( c^{2}\alpha^{lu(t-1)+y} + d^{2}\beta^{lu(t-1)+y}  \right)}{\left( -1 \right)^{u} +
  \left( -1 \right)^{lu} - \left( -1 \right)^{u} \left( \beta^{(l-1)u} + \alpha^{(l-1)u} \right)}\,   \right]   x^{n}.
\end{align*}
This and Proposition (\ref{prop:identities}) part (i) imply that
\begin{equation}\label{formulaf}
	\frac{c^{2} \alpha^{r+1}}{(1-\alpha^{k+1}x)(1-\alpha^{l(k+1)}x)} +
	\frac{d^{2} \beta^{r+1}}{(1-\beta^{k+1}x)(1-\beta^{l(k+1)}x)}=
	\sum_{n=0}^{\infty} \left( S_{2} +S_{3} +S_{4} +S_{5}  \right)\, x^{n}.
\end{equation}
Thus, (\ref{eq:long}), (\ref{formulac}), and (\ref{formulaf}) imply that
\[
	\sum_{n=0}^{\infty}\Conv \left(l(k+1)n+r,l,k\right)\, x^{n} =
	\sum_{n=0}^{\infty} \left( \dfrac{S_{1} + S_{2} + S_{3} + S_{4} + S_{5}}{5} \right)\, x^{n}.
\]
This proves the theorem.
\end{proof}
Notice that the conclusion of Theorem \ref{thm:main2} does not work when $l=1$.
The denominators of $S_{2}, S_{3}, S_{4}$, and $S_{5} $, are always zero when $l=1$.

\section{The special case $\Conv_{a,b}(m,1,k)$}\label{special_case}

In the previous section we gave a closed formula for $\Conv_{a,b}(m,l,k)$ where $l>1$ is an integer.
However, the formula cannot be applied when $l=1$.  The purpose of this section
is to obtain a simple formula for the special case $\Conv_{a,b}(m,1,k)$.

The convolution $\Conv_{1,1}(m,1,k)$ can be use to enumerate several combinatorial objects. In particular, this
convolution counts some types of Fibonacci words and pyramid weights of all non-decreasing
Dyck paths of a given length; see \cite{florezevajunes,denise}. Section \ref{Enumerative_applications} gives detailed
examples on how to apply the convolution in counting problems.

To simplify notation, we use $\Conv_{a,b}(m,k)$ to mean  $\Conv_{a,b}(m,1,k)$ or
we use $\Conv(m,k)$ instead of  $\Conv_{a,b}(m,1,k)$, if there is no ambiguity with $a$ and $b$.


Theorem \ref{thm:main} generalizes Moree's result {\cite[Thm.~4]{moree}}
from the regular Hosoya triangle to the generalized Hosoya triangle. Moreover, our generalization also considers the sum (\ref{convl3}) in
the generalized Hosoya triangle ``jumping" $k$ vertices, for any $k \geq 0$.

\begin{theorem}\label{thm:main} Let  $k \ge 0$ and $m>0$ be integers and let $q=\left\lceil\dfrac{m}{k+1}\right\rceil $. If  $r=m- (q-1) (k+1) $,
then
\[
\Conv(m,k) =\frac{q}{5} \left( a^{2}L_{m-3} + 2ab\,L_{m-2}
+b^{2}L_{m-1} \right) + cd \frac{F_{q (k+1) }}{5F_{(k+1)}}L_{r-1} \;.
\]
\end{theorem}

\begin{proof} We prove this theorem using the same technique as in
Theorem \ref{thm:main2}. That is, we find the generating function of the sequence $\Conv(m,k)$
with $k$ fixed and use Lemma \ref{for:mainthm} to simplify computations.

Let  $m=(k+1)n+r$ where $n\in \mathbb{Z}_{\ge 0}$ and $0<r\le k+1$.
We consider the generating function of the sequence
$\left\{\Conv \left((k+1)n+r,k\right) \right\}_{n =0}^{\infty}$ for fixed numbers $r$ and $k$.
Using the definition of $\Conv(m,k)$, one can see that
\[ \Conv \left((k+1)n+r,k\right) = \sum_{i=0}^{n}G_{(k+1)i +1} \cdot G_{(k+1)(n-i) + r} \; .\]
Therefore,
\[
    \sum_{n=0}^{\infty}\Conv\left((k+1)n+r,k\right)\, x^{n} = \left(
    \sum_{n=0}^{\infty} G_{(k+1)n+1}\, x^{n} \right) \cdot \left(
    \sum_{n=0}^{\infty} G_{(k+1)n+r}\, x^{n} \right).
\]
This last equality and Proposition \ref{prop:identities} part (ii) imply that
\begin{align*}
    \sum_{n=0}^{\infty}\Conv((k+1)n+r,k)\, x^{n}= &  \frac{1}{\sqrt{5}} \left[ \frac{c \alpha}{1-\alpha^{k+1}x}
    - \frac{d \beta} {1-\beta^{k+1}x}  \right]
    \frac{1}{\sqrt{5}}  \left[ \frac{c \alpha^{r}}{1-\alpha^{k+1}x}
    -  \frac{d \beta^{r}}{1-\beta^{k+1}x}  \right]  \\
    =& \frac{1}{5} \left[ \frac{c^{2}\alpha^{r +1}}
    {(1-\alpha^{k+1}x)^{2}} + \frac{d^{2}\beta^{r
    +1}}{(1-\beta^{k+1}x)^{2}} - \frac{cd \alpha \beta
    (\alpha^{r-1} + \beta^{r-1})}{1-L_{k+1}x + (-1)^{k+1}x^{2}} \right].\\
\end{align*}
Since $\alpha \beta =-1$ and $L_{r-1} = \alpha^{r-1} + \beta^{r-1}$,
we obtain
\[ \sum_{n=0}^{\infty}\Conv((k+1)n+r,k)\, x^{n} =
    \frac{1}{5} \left[ \frac{c^{2}\alpha^{r +1}}
    {(1-\alpha^{k+1}x)^{2}} + \frac{d^{2}\beta^{r +1}}
    {(1-\beta^{k+1}x)^{2}} + \frac{cd L_{r-1}}{1-L_{k+1}x + (-1)^{k+1}x^{2}} \right].
\]
This last equality, the Taylor series $\dfrac{1}{(1-ax)^{2}}
=\sum_{n=0}^{\infty}(n+1)a^{n}x^{n}$, and Proposition
\ref{prop:identities} part (iv) imply that
$5\sum_{n=0}^{\infty}\Conv((k+1)n+r,k)\, x^{n} $ is equal to
\begin{align*}
    &  c^{2}\alpha^{r +1} \sum_{n=0}^{\infty}(n+1)\alpha^{(k+1)n}x^{n}
    + d^{2}\beta^{r +1}\sum_{n=0}^{\infty}(n+1)\beta^{(k+1)n}x^{n} +
    cd L_{r-1}\sum_{n=0}^{\infty}\dfrac{F_{(k+1)(n+1)}}{F_{k+1}}\,x^{n}\\
    =& \sum_{n=0}^{\infty} \left[ (n+1)c^{2}\alpha^{(k+1)n +r+1} +
    (n+1)d^{2}\beta^{(k+1)n +r+1} + cd L_{r-1} \frac{F_{(k+1)(n+1)}}{F_{(k+1)}} \right] \,x^{n}.
\end{align*}
Thus,
\[
    5\Conv\left((k+1)n+r,k\right)=(n+1) \left(c^{2}\alpha^{(k+1)n
    +r+1} +  d^{2}\beta^{(k+1)n +r+1} \right) + cd
    L_{r-1}\frac{F_{(k+1)(n+1)}}{F_{(k+1)}}.
    \]
This and Proposition \ref{prop:identities} part (i) imply that
$5 \Conv\left((k+1)n+r,k\right)$ is equal to
\[  (n+1) \left( a^{2}L_{(k+1)n +r-3} +
    2ab\,L_{(k+1)n +r-2} +b^{2}L_{(k+1)n +r-1} \right) +
    cd L_{r-1}\frac{F_{(k+1)(n+1)}}{F_{(k+1)}}.
\]
Since $m=(k+1)n +r$, Lemma \ref{for:mainthm} implies that
\[
\Conv(m,k) =\frac{q}{5} \left( a^{2}L_{m-3} + 2ab\,L_{m-2}
+b^{2}L_{m-1} \right)
 + cd \frac{F_{q (k+1) }}{5F_{(k+1)}}L_{r-1} \;.
\]
This proves the theorem.  \end{proof}

\section{Enumerative applications of $\Conv_{a,b}(m,l, k)$}\label{Enumerative_applications}
The convolution $\Conv_{a,b}(m,l, k)$ summarizes several sequences in \cite{integer2},
see for example, Table~\ref{sloane}. Moreover, particular cases of our convolution
can be use to enumerate many statistics in combinatorics. For instance,
$\Conv_{1,1}(n,0)$ is the number of elements in all subsets of
$\{1,2,\ldots,n\}$ with no consecutive integers. If we take $n=5$, then we can easily see that all the subsets of $\{1,2,3,4,5\}$ that have no consecutive elements are:
\[ \{\},\{1\},\{2\},\{3\},\{4\},\{5\},\{1,3\},\{1,4\},\{1,5\},\{2,4\},\{2,5\}, \{3,5\},\{1,3,5\}, \]
and  the total number of elements in all these subsets (counting repetitions) is $20=C(5,0)$.


The convolution $\Conv_{1,1}(n-1,0)$ counts also binary words. Indeed, if $n \geq 2$ is a natural number, then $\Conv_{1,1}(n-1,0)$ is the number of binary sequences of length $n$ with exactly one pair of consecutive 1's.
For instance, if $n=5$, then all the binary sequences of length $5$ with exactly one pair of consecutive 1's are
\[ \begin{array}{lllll}
 1  1  0  1  0; \quad & 1  1  0  0  1; \quad & 1  1  0  0  0; \quad & 1  0  1  1  0; \quad & 1  0  0  1  1; \\
 0  1  1  0  1; & 0  1  1  0  0; & 0  1  0  1  1; & 0  0  1  1  0; & 0  0  0  1  1. \\
\end{array}\]
The number of these binary sequences is $10=\Conv_{1,1}(4,0)$. For more enumerative applications of $\Conv_{1,1}(n,0)$ see Sloane \seqnum{A001629}.

Another familiar presentation  of $\Conv_{1,1}(n,0)$ is given in \cite[p.~222]{koshy} by
\[ \Conv_{1,1}(n,0)= \sum_{2j \leq n} j { n-j \choose j}.\]

Whoever is familiar with \emph {non-decreasing Dyck paths}, should be interested in the following enumerative application of $\Conv_{1,1}(n,1)$; see Proposition \ref{thm:OldResults}. For a reference and notation, see \cite{florezevajunes}. Proposition \ref{thm:OldResults} can be proved easily using Theorem \ref{thm:main} and  \cite[Thm.~4.2]{florezevajunes}.

\begin{proposition} \label{thm:OldResults} If $n \in \mathbb{N}$, then the sum of the weights of all pyramids in all non-decreasing Dyck paths of length $2n$ is $\Conv_{1,1}(2n-1,1) = (2nF_{2n+1}+(2-n)F_{2n})/5$.		
\end{proposition}

We now discuss some enumerative applications of $\Conv_{1,1}(n,1)$. A \emph{Fibonacci binary word} consists of a strings of zeros and ones having no two zeros sub-words \cite{klavzar, integer2}. In the example below, we can
see that the total number of zeros in odd position for all Fibonacci binary words of length $4$ is $5=\Conv_{1,1}(4,1)$.
\[ \textbf{0}110,\quad \quad11\textbf{0}1,\quad \textbf{0}111,\quad
\textbf{0}1\textbf{0}1,\quad 1111,\quad 1110,\quad 1011,\quad
1010.\]
In general, the total number of zeros in odd position for all Fibonacci binary words
of length $n$ is $\Conv_{1,1}(n,1)$; see Sloane \seqnum{A129720}. Similarly,
the total number of zeros in even position for all Fibonacci binary words of length $4$
is $5=\Conv_{1,1}(4,1)$:
\[ 011\textbf{0},\quad \quad1101,\quad 0111,\quad
0101,\quad 1111,\quad 111\textbf{0},\quad 1\textbf{0}11,\quad
1\textbf{0}1\textbf{0}.\]
In general, the total number of zeros in even position for all Fibonacci binary words of length $2n$ is $\Conv_{1,1}(2n,1)$; see Sloane \seqnum{A129722}.

The \emph{Fibonacci cube} is a graph that has Fibonacci binary words as vertices, two vertices being adjacent whenever they differ in exactly one coordinate. Klav\v{z}ar and Peterin \cite{klavzar} use $\Conv_{1,1}(n-1,0)$ to count the number of edges of the Fibonacci cube.

\begin{table}
\begin{center}
\begin{tabular}{|l|l||l|l|l|}
\hline
Convolution 		& Sloane           &  Convolution  		     & Sloane  \\ \hline
$\Conv_{1,1}(n,0)$  &\seqnum{A001629} & $\Conv_{1,1}(2n-1,1)$ 	 & \seqnum{A030267}  \\
$\Conv_{1,1}(2n,1)$ &\seqnum{A001870} & $\Conv_{1,1}(2n+1,0)$ 	 & \seqnum{A054444}\\
$\Conv_{1,2}(n,0)$ 	&\seqnum{A004798} & $\Conv_{2,1}(2n-1,0)$	 & \seqnum{A203573}\\
$\Conv_{2,1}(n,0)$ 	&\seqnum{A099924} & $\Conv_{1,3}(2n-1,0)$ 	 & \seqnum{A060934}\\
$\Conv_{1,3}(n,0)$ 	&\seqnum{A004799} & $\Conv_{1,1}(2n,2, 0)$   & \seqnum{A056014}\\
$\Conv_{1,3}(2n,1)$ &\seqnum{A061171} & $\Conv_{1,1}(2n-1,2, 0)$ & \seqnum{A094292} \\
$\Conv_{2,1}(2n,1)$ &\seqnum{A203574} & $\Conv_{1,1}(2n,1)$      & \seqnum{A129722} \\
$\Conv_{1,1}(n,1)$  &\seqnum{A129720} &                          &                  \\
\hline
\end{tabular}
\end{center}
\caption{Some sequences in \cite{integer2} summarized by the convolution $\Conv_{a,b}(m,l, k)$.} \label{sloane}
\end{table}

\section{Acknowledgements}
The second author was partially supported by The Citadel Foundation.
The third author was supported by the FPDC travel grant at California University of Pennsylvania.

\begin{thebibliography}{9}

\bibitem{florezevajunes} \'E.~Czabarka, R.~Fl\'orez, and L.~Junes,
Some enumerations on non-decreasing Dyck paths,
to appear.

\bibitem{denise} A.~Denise and R.~Simion,
Two combinatorial statistics on Dyck paths,
\emph{Discrete Math.} {\bf 137} (1995), 155--176.

\bibitem{florezHiguitaMuk} R.~Fl\'{o}rez, R.~Higuita, and A.~Mukherjee,
Alternating sums in the Hosoya polynomial triangle,
\emph{J. Integer Seq.}, \textbf{17} (2014), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Mukherjee/mukh2.html}{Article 14.9.5}.

\bibitem{florezjunes} R.~Fl\'{o}rez, R.~Higuita, and L.~Junes,
GCD property of the generalized star of David in generalized Hosoya triangle,
\emph{J. Integer Seq.}, \textbf{17} (2014), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Florez/florez3.html}{Article 14.3.6}.

\bibitem{rflorezljunes} R.~Fl\'{o}rez and L.~Junes,
GCD properties in Hosoya's triangle, \emph{Fibonacci Quart.} \textbf{50} (2012), 163--174.

\bibitem{griffiths} M.~Griffiths,
Fibonacci diagonals,
\emph{Fibonacci Quart.} \textbf{10} (2011), 51--56.

\bibitem{hosoya} H.~Hosoya,
Fibonacci triangle,
\emph{Fibonacci Quart.} \textbf{14} (1976), 173--178.

\bibitem{klavzar} S.~Klav\v{z}ar and I.~Peterin,
Edge-counting vectors, Fibonacci cubes, and Fibonacci triangle.
\emph{Publ. Math. Debrecen}, \textbf{71} (2007), 267--278.

\bibitem{koshy} T.~Koshy,
\emph{Fibonacci and Lucas Numbers with Applications},
Wiley-Interscience, 2001.

\bibitem{moree} P.~Moree,
Convoluted convolved Fibonacci numbers,
\emph{J. Integer Seq.}, \textbf{7} (2004), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.html}{Article 04.2.2}.

\bibitem{integer2} N.~J.~A.~Sloane,
The On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org/}.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 05A15.

\noindent \emph{Keywords: }
Hosoya triangle, generalized Fibonacci number, convolution,
non-decreasing Dyck path, Fibonacci binary word.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001629}, \seqnum{A001870}, \seqnum{A004798}, \seqnum{A004799},
\seqnum{A030267}, \seqnum{A054444}, \seqnum{A056014},
\seqnum{A060934}, \seqnum{A061171}, \seqnum{A094292}, \seqnum{A099924},
\seqnum{A129720}, \seqnum{A129722}, \seqnum{A203573}, and
\seqnum{A203574}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 24 2014;
revised versions received September 16 2014; December 6 2014.
Published in {\it Journal of Integer Sequences}, January 8 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}



.