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

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

\newcommand {\stirlingf}[2]{\genfrac[]{0pt}{}{#1}{#2}}
\newcommand {\lah}[2]{\genfrac{\lfloor}{\rfloor}{0pt}{}{#1}{#2}}
\newcommand {\stirlings}[2]{\genfrac \{ \}{0pt}{}{#1}{#2}}

\begin{center}
\vskip 1cm{\LARGE\bf Combinatorial Expressions Involving \\
\vskip .02in
Fibonacci, Hyperfibonacci, and Incomplete \\
\vskip .1in
Fibonacci Numbers}
\vskip 1cm
{\large Hac\`{e}ne Belbachir and Amine Belkhir \\
USTHB, Faculty of Mathematics\\
RECITS Laboratory, DG-RSDT\\
BP 32, El Alia \\
16111  Bab Ezzouar, Algiers\\
Algeria\\
\href{mailto:hbelbachir@usthb.dz}{\tt hbelbachir@usthb.dz} \\
\href{mailto:hacenebelbachir@gmail.com}{\tt hacenebelbachir@gmail.com} \\
\href{mailto:abelkhir@usthb.dz}{\tt abelkhir@usthb.dz} \\
\href{mailto:ambelkhir@gmail.com}{\tt ambelkhir@gmail.com}\\
}
\end{center}

\vskip .2 in

\begin{abstract}
We give a combinatorial interpretation, an explicit formula and
some other properties of hyperfibonacci numbers. Further, we deduce relationships between Fibonacci,
hyperfibonacci, and incomplete Fibonacci numbers.
\end{abstract}

\section{Introduction}

The hyperfibonacci numbers $F_{n}^{\left(r\right) }$ introduced recently by Dil and Mez\H{o} \cite{Mezo}. There are defined by the relation
\begin{equation}
F_{n}^{\left( r\right) }=\sum_{k=0}^{n}F_{k}^{\left( r-1\right) },\text{
with \ }F_{n}^{\left( 0\right) }=F_{n}\text{ \ and \ }F_{0}^{\left( r\right)
}=0,\text{ \ }F_{1}^{\left( r\right) }=1,  \label{eq1}
\end{equation}
where $r$ is a positive integer and $F_{n}$ is the $n$-th Fibonacci number
defined recursively by
\begin{equation*}
F_{n}=F_{n-1}+F_{n-2},\text{ for }n\geq 2,\text{ and \ }F_{0}=0,\text{ }%
F_{1}=1.
\end{equation*}

The double recurrence relation for the hyperfibonacci numbers is given by
\begin{equation}
F_{n}^{\left( r\right) }=F_{n-1}^{\left( r\right) }+F_{n}^{\left( r-1\right)
}.  \label{eq2}
\end{equation}

The Fibonacci number $F_{n+1}$ counts the number of tilings of a
$\left( 1\times n\right) $-board with cells labeled $1,2,\ldots ,n$ using
$\left( 1\times 1\right) $-squares and $\left( 1\times 2\right) $-dominoes.
We follow the notation introduced by Benjamin and Quinn \cite{Benj} and define $f_{n}=F_{n+1}$ and get $f_{n}=f_{n-1}+f_{n-2}$
with $f_{0}=f_{1}=1$.

\begin{figure}[h]
\begin{center}
\begin{tabular}{lllllllllllll}
\cline{7-7}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp; \multicolumn{1}{|l}{\  \ } &amp; \multicolumn{1}{|l}{} &amp;  &amp;  &amp;
&amp;  &amp;  \\ \cline{7-7}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ \cline{4-5}\cline{9-10}\cline{10-10}
&amp;  &amp;  &amp; \multicolumn{1}{|l}{\  \ } &amp; \multicolumn{1}{|l}{\  \ } &amp;
\multicolumn{1}{|l}{} &amp;  &amp;  &amp; \multicolumn{1}{|l}{\  \ } &amp; \  \  &amp;
\multicolumn{1}{|l}{} &amp;  &amp;  \\ \cline{4-5}\cline{9-10}\cline{10-10}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\
\cline{1-3}\cline{6-8}\cline{11-13}\cline{12-13}
\multicolumn{1}{|l}{\  \ } &amp; \multicolumn{1}{|l}{\  \ } &amp; \multicolumn{1}{|l}{
\  \ } &amp; \multicolumn{1}{|l}{} &amp;  &amp; \multicolumn{1}{|l}{\  \ } &amp;
\multicolumn{1}{|l}{\  \ } &amp; \  \  &amp; \multicolumn{1}{|l}{} &amp;  &amp;
\multicolumn{1}{|l}{\  \ } &amp; \  \  &amp; \multicolumn{1}{|l|}{\  \ } \\
\cline{1-3}\cline{6-8}\cline{11-13}\cline{13-13}
\end{tabular}%
\end{center}
\caption{Tilings of length $1,2$ and $3$ using squares and dominoes.}
\label{figure 1}
\end{figure}

The following lemma will be used to establish our results.
\begin{lemma} \label{lemma:1a} \cite{Benj}
The number of $n$-tilings using exactly $k$ dominoes is
\begin{equation}
{n-k \choose k},\  \  \left( k=0,1,\ldots ,\left \lfloor n/2\right \rfloor
\right) ,  \label{eq3}
\end{equation}
where $\left \lfloor n\right \rfloor $ is the integer part of $n$.
\end{lemma}
From Lemma \ref{lemma:1a}, Benjamin and Quinn  \cite{Benj} gave a closed form for $f_{n}$ by summing over
all values of $k$, the number of ways to tile an $n$-board with squares and dominoes is
\begin{equation}
f_{n}=\sum_{k=0}^{\left \lfloor n/2\right \rfloor}{n-k \choose k}.  \label{EQ55}
\end{equation}
Our aim is to investigate, as the authors do for generalized Fibonacci and Lucas sequences \cite{Bel, bel2}, the tilings
approach to give a combinatorial interpretation for hyperfibonacci numbers. More precisely, in Section 2, a combinatorial interpretation
of hyperfibonacci numbers is presented. In Section 3, we give a closed form for hyperfibonacci numbers. Finally, in Section 4, we provide a combinatorial interpretation for incomplete Fibonacci numbers and we establish a relation between incomplete Fibonacci numbers and hyperfibonacci numbers.

\section{Combinatorial interpretation}
In this section, we present combinatorial interpretation for hyperfibonacci numbers. Later, we derive a relation involving hyperfibonacci and Fibonacci numbers.

\begin{theorem}
Let $f_{n}^{\left( r\right) }$ counts the number of ways to tile an\ $\left(
n+2r\right) $-board with at least $r$ dominoes. Then $f_{0}^{\left( r\right)
}=1$, $f_{n}^{\left( 0\right) }=f_{n}$, and for $n\geq 2$,
\begin{equation}
f_{n}^{\left( r\right) }=f_{n-1}^{\left( r\right) }+f_{n}^{\left( r-1\right)
}.  \label{eq4}
\end{equation}
\end{theorem}

\begin{proof}
We start by verifying the initial conditions. For $n=0$, there is one $2r$
-tiling with at least $r$ dominoes, and for $r=0$, there are $f_{n}$ $n$-tilings with
at least $0$ dominoes (there is no restriction on the number of dominoes).
Now, if $n\geq 2$, an $\left( n+2r\right) $-board can either end with a square or with a domino. If it ends with a
square, then the remaining $\left( n+2r-1\right) $-board can be tiled with
at least $r$ dominoes in $f_{n-1}^{\left( r\right) }$ ways. If it ends with
a domino, then the remaining $\left( n+2r-2\right) $-board can be tiled with
at least $r-1$ dominoes in $f_{n}^{\left( r-1\right) }$ ways.
\end{proof}
As$\ f_{0}^{\left( r\right) }=F_{1}^{\left( r\right) }=1$ and $f_{n}^{\left(
0\right) }=F_{n+1}^{\left( 0\right) }=F_{n+1},$ it seen that for $n\geq 0$,
we have $f_{n}^{\left( r\right) }=F_{n+1}^{\left( r\right) }$. Letting
$f_{-1}^{\left( r\right) }=0$, because there is not $\left( 2r-1\right)$-tiling
 with at least $r$ dominoes. Now, we have a combinatorial interpretation for the hyperfibonacci numbers.
\begin{theorem}
For $n$,$r\geq 0$, $F_{n+1}^{\left( r\right) }=f_{n}^{\left( r\right) }$ counts
the number of ways to tile an \ $\left( n+2r\right) $-board with at least $r$
dominoes.
\end{theorem}
The first few values of $f_{n}^{\left( r\right) }$ are as follows:
\begin{table}[h]
\begin{center}
\begin{tabular}{c|ccccccccccc}
$n$ &amp; \textbf{0} &amp; \textbf{1} &amp; \textbf{2} &amp; \textbf{3} &amp; \textbf{4} &amp;
\textbf{5} &amp; \textbf{6} &amp; \textbf{7} &amp; \textbf{8} &amp; \textbf{9} &amp; \textbf{10}
\\ \hline
$f_{n}^{\left( 0\right) }$ &amp; 1 &amp; 1 &amp; 2 &amp; 3 &amp; 5 &amp; 8 &amp; 13 &amp; 21 &amp; 34 &amp; 55 &amp; 89
\\
$f_{n}^{\left( 1\right) }$ &amp; 1 &amp; 2 &amp; 4 &amp; 7 &amp; 12 &amp; 20 &amp; 33 &amp; 54 &amp; 88 &amp; 143 &amp;
232 \\
$f_{n}^{\left( 2\right) }$ &amp; 1 &amp; 3 &amp; 7 &amp; 14 &amp; 26 &amp; 46 &amp; 79 &amp; 133 &amp; 221 &amp; 364
&amp; 594 \\
$f_{n}^{\left( 3\right) }$ &amp; 1 &amp; 4 &amp; 11 &amp; 25 &amp; 51 &amp; 97 &amp; 179 &amp; 309 &amp; 530 &amp;
894 &amp; 1490
\end{tabular}
\end{center}
\caption{Some values of $f_{n}^{\left( r\right)}$}
\end{table}
\begin{theorem}
For $n\geq 0$, and $r\geq 1$, we have
\begin{equation}
f_{n}^{\left( r\right) }=\sum_{k=r-1}^{\left \lfloor n/2\right \rfloor
+r-1}\left( n+2r-k-1\right) f_{n}^{\left( r-1\right) }.  \label{EQ5}
\end{equation}
\end{theorem}

\begin{proof}
The number of ways to tile a board of length $n+2r-2$ with at least $r-1$
dominoes is $f_{n}^{\left( r-1\right) }$. Now, to obtain an $\left(
n+2r\right)$-tilings with at least $r$ dominoes from an $\left(
n+2r-2\right) $-tilings with at least $r-1$ dominoes, it suffices to add a
domino. Let $k$ $\left( r-1\leq k\leq \left \lfloor n/2\right \rfloor +r-1\right)$ be the number
of dominos in an $\left( n+2r-2\right)$-tilings,
then it contains $n+2r-2k-2$ squares, so there are $\ n+2r-k-2$ tiles in
the $(n+2r-2)$-tilings. The number of ways to place a domino in an $(n+2r-2)$
-tiling with $k$ $\left( r-1\leq k\leq \left \lfloor n/2\right \rfloor +r-1\right) $ dominoes is $n+2r-k-1$.
\end{proof}

The hyperfibonacci numbers $f_{n}^{\left( r\right) }$ can be expressed as a
sum of a product of binomial coefficients and Fibonacci numbers.

\begin{theorem}
For $n\geq 0$, and $r\geq 1$, we have
\begin{equation}
f_{n}^{\left( r\right) }=\sum_{k=0}^{n}{n+r-k-1 \choose r-1}f_{k}.
\label{EQ6}
\end{equation}
\end{theorem}

\begin{proof}
Let $k+1$,$k+2$ $\left( 0\leq k\leq n\right) $ be the position of the $r$-th
(from the right) domino, then there are $f_{k}$ ways to tile the
first $k$ cells, and there are ${n+r-k-1 \choose r-1}$ ways to tile cells
from $k+3$ to $n+2r$ with exactly $r-1$ dominoes. Thus, there are ${n+r-k-1\choose r-1}$ $f_{k}$ $\left( n+2r\right)$-tilings
with the $r$-th
domino covering cells $k+1$,$k+2$. Summing over $k$, we get relation \eqref{EQ6}.
\end{proof}

From the relation \eqref{EQ6}, the following convolution is
derived, the hyperfibonacci numbers are obtained as a convolution between
the anti-diagonal terms of Pascal's triangle and the Fibonacci numbers.

\begin{corollary}
For $n\geq 0$, and $r\geq 1$, we have
\begin{equation}
f_{n}^{\left( r\right) }=\sum_{k=0}^{n}{r-1+k \choose k}f_{n-k}.  \label{EQ7}
\end{equation}
\end{corollary}


\section{Closed form for hyperfibonacci numbers}

The following theorem gives an explicit expression of $f_{n}^{\left(r\right) }$ in terms of binomial coefficients.
\begin{theorem}
For $n\geq 0$, and $r\geq 1$, we have
\begin{equation}
f_{n}^{\left( r\right) }=\sum_{k=r}^{\left \lfloor n/2\right \rfloor +r}{n+2r-k \choose k}.  \label{EQ8}
\end{equation}
\end{theorem}

\begin{proof}
An $\left( n+2r\right)$-tiling with at least $r$ dominoes can contains $k$
dominoes where $k=r,r+1,\ldots ,\left \lfloor n/2\right \rfloor +r$. Using
Lemma \ref{lemma:1a}, the number of $\left( n+2r\right) $-tilings with exactly $k$
dominoes is ${n+2r-k \choose k}$. Summing over $k$ we get \eqref{EQ8}.
\end{proof}

The relation \eqref{EQ8} is a truncated diagonal sum of Pascal's Triangle. This allow us to state the following:

\begin{theorem}
For $n\geq 0$, and $r\geq 1$, we have
\begin{equation}
f_{n}^{\left( r\right) }=f_{n+2r}-\sum_{k=0}^{r-1}{n+2r-k \choose k}.
\label{9}
\end{equation}
\end{theorem}

\begin{remark}
For $n\geq 0$, we have some special cases
\begin{equation}
f_{n}^{\left( 1\right) }=\sum_{k=0}^{n}f_{k}=f_{n+2}-1.
\end{equation}
\begin{equation}
f_{n}^{\left( 2\right) }=\sum_{k=0}^{n}\left( k+1\right) f_{n-k}=f_{n+4}-n-4.
\end{equation}
\end{remark}

\section{Relationships between the hyperfibonacci and incomplete Fibonacci
numbers}
We give a combinatorial interpretation for the
incomplete Fibonacci numbers. This allow us to obtain a relationship involving the
Fibonacci, hyperfibonacci, and incomplete Fibonacci numbers.


Filipponi \cite{Filip} defined the incomplete Fibonacci numbers $F_{n}\left( k\right)$ by the following relation for $n \geq 0$
\begin{equation}
F_{n+1}\left( k\right) =\sum_{j=0}^{k}{n-j \choose j}\text{ \ }\left(0\leq k\leq \left \lfloor \tfrac{n+1}{2}\right \rfloor \right) . \label{EQ12}
\end{equation}

\begin{theorem}
Let $f_{n}\left( k\right) $ counts the number of ways to tile an $n$-board
with at most $k$ dominoes. Then
\begin{equation}
f_{n}\left( k\right) =\sum_{j=0}^{k}{n-j \choose j}\text{ \ }\left( 0\leq
k\leq \left \lfloor \tfrac{n}{2}\right \rfloor \right) .  \label{14}
\end{equation}
\end{theorem}
\begin{proof}
It follows from Lemma \ref{lemma:1a}, by summing over $j$.
\end{proof}
Note that, if we take $k=\left \lfloor \tfrac{n}{2} \right \rfloor $, then the $f_{n}\left( k\right) $
is reduced to the Fibonacci number $f_{n}$.
\begin{theorem}
For $n\geq 0$, we have
\begin{equation}
f_{n}\left( k\right) =f_{n-1}\left( k\right) +f_{n-2}\left( k-1\right),
\label{EQ13}
\end{equation}
with $f_{n}\left( 0\right) =f_{0}\left( k\right) =1$.
\end{theorem}

\begin{proof}
An $n$-tilings with at most $k$ dominoes either ends with a square or a domino.
If it ends with a square, there are $f_{n-1}\left( k\right)$ ways to tile the
first $n-1$ cells with at most $k$ dominoes and if it ends with a domino,
there are $f_{n-2}\left( k-1\right)$ ways to tile the first $n-2$ cells
with at most $k-1$ dominoes.
\end{proof}

The following theorem gives a combinatorial interpretation for incomplete
Fibonacci numbers.
\begin{theorem}
For $n$,$k\geq 0$ with $0\leq k\leq \left \lfloor n/2\right \rfloor$, we have
$F_{n+1}\left( k\right) =f_{n}\left( k\right)$. That is, $F_{n+1}\left( k\right)$ counts the number of ways
to tile an $n$-board with at most $k$ dominoes.
\end{theorem}

From relations \eqref{EQ12} and \eqref{EQ13}, we obtain the following non-homogenous second order recurrence relation as
stated by Filipponi \cite{Filip}.

For $n\geq 0$, we have
\begin{equation}
f_{n}\left( k\right) =f_{n-1}\left( k\right) +f_{n-2}\left( k\right) - {n-k \choose k}.
\end{equation}
Using the approach of Benjamin et al., we recover Filipponi's formula \cite{Filip}.

\begin{theorem}
For $n\geq 0$, we have
\begin{equation}
f_{n+2h}\left( k+h\right) =\sum_{j=0}^{h}{h \choose j}f_{n+j}\left(
k+j\right) \text{ \ }\left( 0\leq k\leq \frac{n-h}{2}\right) .
\end{equation}
\end{theorem}

\begin{proof}
The left hand side counts the number of ways to tile an $(n+2h)$-board with at
most $k+h$ dominoes. Now, we show that the right hand side counts the same
tilings by conditioning on the number of dominoes that appear among the
first $h$ tiles. There are ${h \choose j}$\ ways to select $j$ positions
for the dominoes among the first $h$ tiles and $f_{n+h-j}\left( k+h-j\right)$ ways
to tile remaining $n+h-j$\ cells with at most $k+h-j$ dominoes.
\end{proof}

Using \eqref{9} and \eqref{14}, we give a relation between Fibonacci numbers, incomplete Fibonacci numbers and hyperfibonacci numbers.

\begin{corollary}
For integers $n$,$r\geq 0$, we have
\begin{equation}
f_{n+2r}=f_{n}^{\left( r\right) }+f_{n+2r}\left( r-1\right) .
\end{equation}
\end{corollary}

This states that, for given nonnegative integers $n$ and $r$, every Fibonacci
number can be written as a combination of an incomplete Fibonacci number
and an hyperfibonacci number.

\section{Acknowledgments}
The authors thank the anonymous referee for the throughout
reading of the manuscript and valuable comments.

\begin{thebibliography}{9}
\bibliographystyle{plain}

\bibitem{Bel} H. Belbachir and A. Belkhir. Identities related to generalized
Fibonacci numbers via tiling approach, submitted.

\bibitem{bel2} H. Belbachir and A. Belkhir. Tiling approach to obtain
identities for generalized Fibonacci and Lucas numbers, \emph{Ann.
Math. Inform.}, \textbf{41} (2013), 13--17.

\bibitem{bqs} A. T. Benjamin, J. J. Quinn, and F. E. Su. Phased tilings
and generalized Fibonacci identities. \emph{Fibonacci Quart}.
\textbf{38} (2000), 282--288.

\bibitem{Benj} A. T. Benjamin and J. J. Quinn. \emph{Proofs That Really
Count: The Art of Combinatorial Proof}, Mathematical Association of
America, 2003.

\bibitem{Mezo} A. Dil and I. Mez\H{o}. A symmetric algorithm for
hyperharmonic and Fibonacci numbers, \emph{Appl. Math. Comput.} \textbf{206}
(2008), 942--951.

\bibitem{Filip} P. Filipponi. Incomplete Fibonacci and Lucas numbers,
\emph{Rend.  Circ. Mat. Palermo} \textbf{45} (1996) 37--56.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:  Primary 11B39; Secondary 05B45; 05A19; 11B37.

\noindent {\it Keywords}: Fibonacci number, hyperfibonacci number, tiling, bijective proofs, incomplete Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000071}, and
\seqnum{A136431}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 2 2013;
revised version received January 22 2014.  
Published in {\it Journal of Integer Sequences}, February 16 2014.


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