<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{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}

\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Pk}{{\mathbb P}}
\newcommand{\T}{{\mathcal T}}
\newcommand{\Pell}{{\mathcal P}}
\newcommand{\A}{{\mathcal A}}

\def\AA{\mathbb{A}}
\def\F{\mathbb{F}}

\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  Combinatorial Interpretation of Generalized Pell Numbers\\
\vskip 1cm}
\large
Jhon J. Bravo\footnote{Corresponding author.} and Jose L. Herrera \\ 
Departamento de Matem\'aticas\\ 
Universidad del Cauca\\ 
Popay\'an\\ 
Colombia\\
\href{mailto:jbravo@unicauca.edu.co}{\tt jbravo@unicauca.edu.co}\\
\href{joseherrera@unicauca.edu.co}{\tt joseherrera@unicauca.edu.co}\\
\ \\
Jos\'e L. Ram\'{\i}rez\\
Departamento de Matem\'aticas\\
 Universidad Nacional de Colombia\\
Bogot\'a\\
Colombia\\
\href{mailto:jlramirezr@unal.edu.co}{\tt jlramirezr@unal.edu.co}
\end{center}

\vskip .2 in

\begin{abstract}
In this note we give combinatorial interpretations for the generalized Pell sequence of order $k$ by means of lattice paths and  generalized bi-colored  compositions. We also derive some basic relations and identities by using Riordan arrays. 
\end{abstract}

\section{Introduction}
There are many integer sequences that are used in many fields of modern science. For instance, the Fibonacci sequence $F=(F_n)_{n=0}^{\infty}$ is one of the most famous and curious numerical sequences in mathematics, and has been widely studied in the literature. The  Fibonacci  numbers  can  be  interpreted  combinatorially  as  the  number  of ways to tile a board of length $n$ and height 1 using only squares (length 1, height 1) and dominoes (length 2, height 1).  They also count the number of binary sequences with no consecutive zeros, the number of sequences of 1's and 2's that sum to a given number, and the number of independent sets of a path graph, among others.

The Fibonacci sequence has been generalized in many ways, some
by preserving the initial conditions, and others by preserving the
recurrence relation. Cooper and Howard \cite{CoHo} and Dresden and Du
\cite{D-Du} investigated a generalization of the Fibonacci sequence
given by a recurrence relation of a higher order. They considered, for
an integer $k\geq 2$, the $k$-generalized Fibonacci sequence, which is
like the Fibonacci sequence but starts with the terms $0,0,\ldots, 0,1$ (a total
of $k$ terms), and each term afterwards is the sum of the $k$ preceding
terms. These numbers can  also be  interpreted  combinatorially  as the
number of ways to tile a board of length $n$ and height 1 using tiles
of length at most $k$. This combinatorial interpretation has been used
to provide simple and intuitive proofs of several identities involving
$k$-generalized Fibonacci numbers (see \cite{Heberle-thesis}). Other
generalizations of the Fibonacci sequence have also been studied (see,
for example, \cite{Brent,Kilic,Muskat,RAM3}).

Also, there is the Pell sequence, which is as important as the Fibonacci sequence. The Pell sequence $P=(P_n)_{n=0}^{\infty}$ is defined by the recurrence $P_n=2P_{n-1}+P_{n-2}$ for all $n\geq 2$ with $P_0=0$ and $P_1=1$ as initial conditions. For the beauty and rich applications of these numbers and their relatives one can see Koshy's books \cite{Kos01, koshy2}. The Pell sequence appears in OEIS as  \seqnum{A000129}. The first few terms of this sequence are 
\[
0, \, 1, \, 2, \, 5, \, 12, \, 29, \, 70, \, 169, \, 408, \, 985, \, 2378, \, 5741, \dots
\]
This sequence has many interesting combinatorial and arithmetical properties;  see, e.g., \cite{koshy2}. For example, it is possible to prove  that $P_{n+1}$ counts the number of bi-colored compositions of a positive integer $n$. By a \emph{bi-colored composition} of a positive integer $n$ we mean a sequence of positive integers $\sigma=(\sigma_1, \sigma_2,\dots, \sigma_\ell)$ such that $\sigma_1+\sigma_2+\cdots + \sigma_\ell=n$,  $\sigma_i \in \{ \texttt{1}, \texttt{2}\}$, and the summand  $\texttt{1}$ can come in one of $2$ different colors.  The colors of the summand $\texttt{1}$ are denoted by subscripts $\texttt{1}_1$ and $\texttt{1}_2$. For example, the bi-colored compositions of $3$ are
\begin{align*}
&amp;\texttt{2} + \texttt{1}_1, \quad \texttt{2} + \texttt{1}_2, \quad \texttt{1}_1 + 2,  \quad \texttt{1}_2 + 2, \quad \texttt{1}_1 + \texttt{1}_1 + \texttt{1}_1, \quad  \texttt{1}_2 + \texttt{1}_1 + \texttt{1}_1, \quad  \texttt{1}_1 + \texttt{1}_2 + \texttt{1}_1, \, \\
&amp; \texttt{1}_1 + \texttt{1}_1 + \texttt{1}_2, \quad  \texttt{1}_1 + \texttt{1}_2 + \texttt{1}_2,  \quad  \texttt{1}_2 + \texttt{1}_1 + \texttt{1}_2,  \quad \texttt{1}_2 + \texttt{1}_2 + \texttt{1}_1, \quad   \texttt{1}_2 + \texttt{1}_2 + \texttt{1}_2.
\end{align*}
This combinatorial interpretation can be translated into the language of tilings. As mentioned before, it is well-known that the Fibonacci  number $F_{n+1}$  can be interpreted as the number of tilings of a board of length $n$  with cells labeled 1 to $n$ from left to right with only squares and dominoes \cite{Benja}. If we use white and black squares  and non-colored dominoes we obtain a different combinatorial interpretation for  the Pell numbers.  For example,  Figure \ref{tile}  shows the different ways to tiling a $3$-board. 

\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{tiling2.eps}
\caption{Different ways to tile $3$-boards.}
\label{tile}
\end{figure}

In this paper, we are interested in a generalization of the Pell sequence called the $k$-generalized Pell sequence  or, for simplicity, the $k$-Pell sequence $P^{(k)}=(P_n^{(k)})_{n=-(k-2)}^{\infty}$ defined by the recurrence  
\[
P_n^{(k)}=2P_{n-1}^{(k)} + P_{n-2}^{(k)} + \cdots + P_{n-k}^{(k)} \quad  \text{ for all $n\geq 2$,}
\]
with the initial values $P_{-(k-2)}^{(k)}=P_{-(k-3)}^{(k)}=\cdots = P_{0}^{(k)}=0$ and $P_{1}^{(k)}=1$. We refer to $P_n^{(k)}$ as the $n$th $k$-Pell number. In particular, we introduce  new combinatorial interpretations for the $k$-Pell sequence by means of lattice paths and generalized  bi-colored compositions.  We also use Riordan arrays to derive possibly new combinatorial identities and relations for the $k$-Pell numbers. 


\section{A combinatorial interpretation: lattice paths}
Let $S$ be a fixed subset of $\Z\times \Z$. A \emph{lattice path} $\Gamma$ of length $\ell$ with steps in $S$ is a $\ell$-tuple of directed steps of $S$. That is $\Gamma=(s_1,\dots, s_\ell)$ where $s_i\in S$ for $1\leq i \leq \ell$.   Let $a(n, m)$ be the number of lattice paths from the point $(0,0)$ to the point $(n,m)$ with step set $S=\{H=(1,0), V=(0,1)\}$. It is clear that $a(n, m)=\binom{n+m}{n}$.  Let $\A$ be the infinite lower triangular matrix defined by $\A:=\left[a(n-m,m)\right]_{n, m\geq 0}=\left[\binom{n}{m}\right]_{n, m\geq 0}$. The matrix $\A$  coincides with the Pascal matrix. Among the many properties of the Pascal matrix, it is known that the sum of the elements on the rising diagonal is the Fibonacci sequence \seqnum{A000045}, i.e., for $n\geq 1$
\[
F_n=\sum_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-i-1}{i}.
\]
 From this combinatorial interpretation, we conclude that $F_n$ counts the number of lattice paths from $(0,0)$ to $(n-2i-1,i)$ for $i=0, 1, \dots,  \lfloor(n-1)/2\rfloor$. For example,  Figure \ref{fig1} shows the paths for $n=5$, i.e., the paths counted by the Fibonacci number $F_5=5$. 
        \begin{figure}[H]
        \centering
   \includegraphics[scale=0.7]{Fibo.eps}
      \caption{Lattices paths counted by the Fibonacci number $F_5$.}
      \label{fig1}
       \end{figure}

The goal of this section is to generalize the above results for the $k$-Pell numbers. In particular, we introduce a family of matrices $\Pell_k$ from a family of generalized paths. These matrices satisfy that the row sum coincides with the $k$-Pell numbers; see Corollary \ref{coroteo2}.  

Let $\Pk_k(n,m)$ denote the set of lattice paths from the point $(0,0)$ to the point $(n,m)$ with step set 
\[
S_k:=\{ H=(1,0), \, V=(0,1), \, D_1=(1,1), \, D_2=(1,2), \, \dots, \, D_k=(1,k) \}. 
\]
In Figure \ref{fig2}, we show all lattice paths of the set $\Pk_2(1,3)$.  
        \begin{figure}[H]
        \centering
   \includegraphics[scale=0.7]{Paths.eps}
      \caption{Lattices paths in $\Pk_2(1,3)$.}
      \label{fig2}
       \end{figure}

Let $p_k(n,m)$ be the number of lattice paths of $\Pk_k(n,m)$, i.e., $p_k(n,m):=|\Pk_k(n,m)|$.  Since the last step on any path from  $\Pk_k(n,m)$  is one of $S_k$, we obtain the recurrence relation:
\begin{multline}\label{rec1}
p_k(n,m)=p_k(n-1,m) + p_k(n,m-1) + p_k(n-1,m-1)  \\
+ p_k(n-1,m-2) + \cdots + p_k(n-1,m-k),
\end{multline}
with $n\geq 1, m\geq k$, and  the initial conditions $p_k(0,m)=1=p_k(n,0)$. For example, for $k=2$ the first few values of the sequence $p_2(n,m)$ are
\begin{figure}[H]
\centering
\includegraphics[scale=1.1]{Triangle.eps}
\label{fig3}
\end{figure}

Let $P_n^{(k)}(x)$ be the ordinary generating function of the sequence $\{p_k(n,m)\}_m$. That is,
\[
P_n^{(k)}(x)=\sum_{i\geq 0}p_k(n,i)x^i.
\]
In Theorem \ref{teo1}  we find an expression for the generating function $P_n^{(k)}(x)$. 
\begin{theorem}\label{teo1}
We have 
$$P_n^{(k)}(x)=\frac{(1+x+x^2+\cdots + x^k)^n}{(1-x)^{n+1}}.$$
\end{theorem}
\begin{proof}
 From equation \eqref{rec1}, we obtain the relation
$$P_n^{(k)}(x)= P_{n-1}^{(k)}(x) + xP_n^{(k)}(x) + xP_{n-1}^{(k)}(x) + x^2P_{n-1}^{(k)}(x)  + \cdots + x^kP_{n-1}^{(k)}(x).$$ 
Thus
\begin{align*}
P_n^{(k)}(x)= \frac{1+x+x^2+\cdots + x^k}{1-x}P_{n-1}^{(k)}(x).
\end{align*}
Since $P_0=1/(1-x)$, we obtain the desired result. 
\end{proof}


\begin{corollary}\label{coro1teo1}
The number of lattice paths   $p_k(n,m)$ is given by
$$p_k(n,m)=\sum_{\ell_0+\ell_1+\cdots+\ell_k=n}\binom{n}{\ell_0, \ell_1, \dots, \ell_k}\binom{n+m-t}{n},$$
where $t=\sum_{s=0}^k s\ell_s$ and 
$$
\binom{n}{n_1,\ldots,n_m}=\dfrac{n!}{n_1! \ \cdots \ n_m!}
$$
is the multinomial coefficient.
\end{corollary}
\begin{proof}
 From the multinomial theorem, the generating function
$$\frac{1}{(1-x)^{n+1}}=\sum_{i\geq 0} \binom{n+i}{i}x^i,$$
and Theorem \ref{teo1}, we have that
\begin{align*}
p_k(n,m)&amp;=[x^m]P_n^{(k)}(x)=[x^m]\frac{(1+x+x^2+\cdots + x^k)^n}{(1-x)^{n+1}}\\
&amp;=[x^m] \sum_{\ell_0+\ell_1+\cdots+\ell_k=n}\binom{n}{\ell_0, \ell_1, \dots, \ell_k} \prod_{s=0}^{k}x^{s\ell_s} \sum_{i\geq 0} \binom{n+i}{i}x^i\\
&amp;=[x^m] \sum_{\ell_0+\ell_1+\cdots+\ell_k=n} \sum_{i\geq 0} \binom{n}{\ell_0, \ell_1, \dots, \ell_k} \binom{n+i}{i} x^{t + i},
\end{align*} 
where $t=\sum_{s=0}^k s\ell_s$.  By comparing the $m$-th coefficient we obtain the desired result.  
\end{proof}

For example, 
\begin{align*}p_2(1,3)&amp;=\sum_{\ell_0+\ell_1+\ell_2=1}\binom{1}{\ell_0, \ell_1, \ell_2}\binom{1+3-(\ell_1 + 2\ell_2)}{1}\\
&amp;=\binom{1}{1, 0, 0}\binom{4}{1} + \binom{1}{0, 1, 0}\binom{3}{1} + \binom{1}{0, 0, 1}\binom{2}{1}=4+3+2=9.
\end{align*}
In Figure \ref{fig2}, we show the corresponding lattice paths. 

Let $\Pell_k:=\left[q_k(n,m)\right]_{n, m\geq 0 }$ be the array defined by 
\[ 
q_k(n,m)=\begin{cases}
p_k(m,n-m),&amp; \text{ if } n\geq m;\\
0,&amp; \text{ if } n&lt;m. \\
\end{cases}
\]
For example, the first few rows of the  array $\Pell_2$ are as follows  (see also \seqnum{A102036}).
\[
\Pell_2=\left(
\begin{array}{cccccccc}
 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
 1 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
 1 &amp; 6 &amp; 5 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
 1 &amp; 9 &amp; 15 &amp; 7 &amp; 1 &amp; 0 &amp; 0 &amp; 0  \\
 1 &amp; 12 &amp; 33 &amp; 28 &amp; 9 &amp; 1 &amp; 0 &amp; 0  \\
 1 &amp; 15 &amp; 60 &amp; 81 &amp; 45 &amp; 11 &amp; 1 &amp; 0 \\
 1 &amp; 18 &amp; 96 &amp; 189 &amp; 161 &amp; 66 &amp; 13 &amp; 1 \\
  \vdots &amp;  &amp;  &amp;   \vdots &amp;  &amp;  &amp;  &amp;   \vdots \\
\end{array}
\right)
\]

This new family of matrices $\Pell_k$ are an example of a Riordan array. Remember  that an infinite lower triangular matrix  is called a \emph{Riordan array} \cite{Riordan2} if its $k$th column satisfies the generating function  $g(x)\left(f(x)\right)^k$ for $k \ge 0$, where  $g(x)$ and $f(x)$
are formal  power series with $g(0) \neq 0$, $f(0)=0$ and $f'(0)\neq 0$.  The matrix corresponding to
the pair  $f(x), g(x)$ is denoted by  $(g(x),f(x))$.  If we multiply $(g, f)$ by a column vector $(c_0, c_1, \dots)^T$
with the generating function  $h(x)$, then the resulting column vector has generating function $g(x)h(f(x))$.
This property is  known as the fundamental theorem of Riordan arrays or summation property.

The product of two Riordan arrays $(g(x),f(x))$ and $(h(x),l(x))$ is defined by
\[
(g(x),f(x))*(h(x),l(x))=\left(g(x)h\left(f(x)\right), l\left(f(x)\right)\right).
\]
We recall that the set of all Riordan matrices is a group  under the operator $``*"$ \cite{Riordan2}.  The identity element is $I=(1,x)$, and the inverse of $(g(x),f(x))$ is
\[
 (g(x), f(x))^{-1}=\left(1/\left(g\circ \overline{f}\right)(x), \overline{f}(x)\right),
\]
where $\overline{f}(x)$ is the compositional inverse of $f(x)$. For example, the Pascal matrix is given by the Riordan array
\[
\left(\frac{1}{1-x}, \frac{x}{1-x}\right).
\]
Several authors have used Riordan arrays to study lattice paths; see for example \cite{FLORAM2, FLORAM, Sprugnoli2,   RAM, RAM2, Sprugnoli, Yang, Yang2,  Yang3, Yang4}.

 From the definition of Riordan array and Theorem  \ref{teo1} we obtain the following theorem.
\begin{theorem}\label{Riordan}
The matrix $\Pell_k$ is a Riordan array given by
$$\Pell_k=\left(\frac{1}{1-x}, x\frac{1+x+x^2+\cdots + x^k}{1-x}\right).$$
\end{theorem}
\begin{proof}
The $(n,m)$-th entry of the Riordan array is given by
\begin{align*}
[x^n]\frac{1}{1-x}\left(x\frac{1+x+x^2+\cdots + x^k}{1-x}\right)^m&amp;=[x^{n-m}]\frac{(1+x+x^2+\cdots + x^k)^m}{(1-x)^{m+1}}\\
&amp;=[x^{n-m}]P_{m}^{(k)}(x)\\
&amp;=p_k(m,n-m)=q_k(n,m).
\end{align*}
Hence the matrices are the same. 
\end{proof}

Let $R_k(x)$ be the generating function for the rows sums of the matrix $\Pell_k$. In Theorem \ref{teo2} we give an expression for this generating function.
\begin{theorem}\label{teo2}
The generating function $R_k(x)$ is given by
$$R_k(x)=\frac{1}{1-2x - x^2 -\cdots - x^{k+1}}.$$
\end{theorem}
\begin{proof}
 From the summation property for the Riordan arrays we have
$$R_k(x)=\Pell_k \left(\frac{1}{1-x}\right)=\frac{1}{1-x}\left(\frac{1}{1-x\frac{1+x+x^2+\cdots + x^k}{1-x}}\right)=\frac{1}{1-2x - x^2 -\cdots - x^{k+1}}.$$
\end{proof}

By using standard methods, it is possible to prove that the ordinary generating function of the $k$-Pell sequence is
$$\sum_{n\geq 0}P_n^{(k)}x^n=\frac{1}{1-2x - x^2 -\cdots - x^k}.$$
Thus we have the following corollary.  
\begin{corollary}\label{coroteo2}
The $k$-Pell numbers $P_n^{(k)}$ coincide with the row sum of the matrix $\Pell_{k-1}$.
\end{corollary}

For example,  the row sum of the matrix $\Pell_2$ coincides with the $3$-Pell numbers \seqnum{A077939}:
$$1, \, 2, \, 5, \, 13, \, 33, \, 84, \, 214, \, 545, \, 1388, \, 3535, \, 9003, \cdots$$

In Corollary \ref{coro2} we deduce a possibly new combinatorial identity for the $k$-Pell numbers. 
\begin{corollary}\label{coro2}
The $k$-Pell numbers $P_n^{(k)}$ are given by the combinatorial identity
$$P_n^{(k)}=\sum_{i=0}^n \sum_{\ell_0+\ell_1+\cdots+\ell_{k-1}=i}\binom{i}{\ell_0, \ell_1, \dots, \ell_{k-1}}\binom{n-t}{i},$$
where $t=\sum_{j=0}^{k-1} j\ell_j$. 
\end{corollary}
\begin{proof}
 From Corollaries \ref{coro1teo1} and \ref{coroteo2} we have
\begin{align*}
P_n^{(k)}=\sum_{i=0}^nq_{k-1}(n,i)=\sum_{i=0}^np_{k-1}(i,n-i)=\sum_{i=0}^n\sum_{\ell_0+\ell_1+\cdots+\ell_{k-1}=i}\binom{i}{\ell_0, \ell_1, \dots, \ell_{k-1}}\binom{n-t}{i}. 
\end{align*}
\end{proof}

Finally, from the relation $P_n^{(k)}=\sum_{i=0}^np_{k-1}(i,n-i)$ we deduce the following combinatorial interpretation. 

\begin{theorem}
The $k$-Pell number $P_{n+1}^{(k)}$ counts the number of lattice paths from the point  $(0,0)$ to $(n-i,i)$ for $i=0, 1, \dots, n$, with step set 
$$S_k=\{ H=(1,0), \, V=(0,1), \, D_1=(1,1), \, D_2=(1,2), \, \dots, \, D_k=(1,k) \}. $$   
\end{theorem}

For example, the $3$-Pell number $P_4^{(3)}=13$ counts the  paths of Figure \ref{lattice3}.
        \begin{figure}[H]
        \centering
   \includegraphics[scale=0.6]{lattice3.eps}
      \caption{Lattices paths counted by $P_4^{(3)}$.}
      \label{lattice3}
       \end{figure}
       
We recall that the Fibonacci numbers are equal to  the sum on the rising diagonal in the Pascal matrix. In Theorem \ref{teo3}    we give an analogue of this result for the $k$-Pell sequence. 

 \begin{theorem}\label{teo3}
The $k$-Pell numbers $P_n^{(k)}$ coincide with the sum of the elements on rising diagonal lines in the Riordan array
$$Q_k:=\left(\frac{1}{1-2x}, x\frac{1+x+x^2+\cdots + x^{k-2}}{1-2x}\right).$$
\end{theorem}
\begin{proof}
The generating function of the sum of the elements on rising diagonal lines  in the above Riordan array is
\begin{align*}
\frac{1}{1-2x}\left(\frac{1}{1-x^2 \left(\frac{1+x+x^2+\cdots + x^{k-2}}{1-2x}\right)}\right)=&amp;\frac{1}{1-2x - x^2 -\cdots - x^{k}}=\sum_{n\geq 0}P_n^{(k)}x^n.
\end{align*}
\end{proof}

For example, the diagonal sum of the  Riordan array  $Q_2$ (see also \seqnum{A038207}) coincides with the  classical Pell numbers
$$Q_2=\left(\frac{1}{1-2x}, \frac{x}{1-2x}\right)=\left(
\begin{array}{cccccccc}
 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 4 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 8 &amp; 12 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 16 &amp; 32 &amp; 24 &amp; 8 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
 32 &amp; 80 &amp; 80 &amp; 40 &amp; 10 &amp; 1 &amp; 0 &amp; 0 \\
 64 &amp; 192 &amp; 240 &amp; 160 &amp; 60 &amp; 12 &amp; 1 &amp; 0 \\
 128 &amp; 448 &amp; 672 &amp; 560 &amp; 280 &amp; 84 &amp; 14 &amp; 1 \\
   \vdots &amp;  &amp;  &amp; &amp; \vdots   &amp;  &amp;  &amp;  \vdots\\
\end{array}
\right).$$
The diagonal sum of the  Riordan array  $Q_3$ coincides with the  3-Pell numbers
$$Q_3=\left(\frac{1}{1-2x}, x\frac{1+x}{1-2x}\right)=\left(\begin{array}{cccccccc}
 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 4 &amp; 5 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 8 &amp; 16 &amp; 8 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 16 &amp; 44 &amp; 37 &amp; 11 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
 32 &amp; 112 &amp; 134 &amp; 67 &amp; 14 &amp; 1 &amp; 0 &amp; 0 \\
 64 &amp; 272 &amp; 424 &amp; 305 &amp; 106 &amp; 17 &amp; 1 &amp; 0 \\
 128 &amp; 640 &amp; 1232 &amp; 1168 &amp; 584 &amp; 154 &amp; 20 &amp; 1 \\
  \vdots &amp;  &amp;  &amp; \vdots   &amp;  &amp;  &amp;  &amp;  \vdots
\end{array}
\right).$$
 
\begin{figure}[H]
  \centering
 \includegraphics[scale=0.8]{Fractal1.eps}
 \caption{Matrix $\Pell_2 \pmod 2$.}
   \label{fractal}
\end{figure}

The Riordan arrays obtained in this section  show interesting patterns if you evaluated their entries mod 2. In Figure \ref{fractal} we show the \emph{fractal} structure of the matrix $\Pell_2$.  Notice that Merlini and Nocentini \cite{MN} have studied some relations between Riordan arrays and fractal patterns. In a forthcoming paper we will study the $p$-adic valuation for the $k$-Pell sequence.  
     
\section{The generalized  bi-colored compositions}
The goal of this section is to consider a generalization of the concept of a bi-colored composition in order to give another combinatorial interpretation of the $k$-Pell numbers. Here and below, $n$ denotes a positive integer. In fact, we defined a \emph{generalized bi-colored composition} of $n$ as a sequence of positive integers $\sigma = \left(\sigma_{1}, \sigma_{2}, \ldots,\sigma_{\ell}\right)$ such that $\sigma_{1}+\sigma_{2}+\cdots+\sigma_{\ell}=n$, and the summand $\texttt{1}$ can take two colors. The colors of the summand $\texttt{1}$ are denoted by subscripts $\texttt{1}_\texttt{1}$ and $\texttt{1}_\texttt{2}$. Further, the positive integers $\sigma_{i}$ are called \textit{parts} of the composition. We let $\AA_{n}$ denote the set of all generalized bi-colored compositions of $n$ and let $C(n)$ denote the number of elements in $\AA_{n}$, i.e., $C(n):=|\AA_{n}|$. We also use $C_{k}(n)$ to denote the number of generalized  bi-colored compositions of $n$ with parts in the set $\{\texttt{1},\texttt{2},\ldots,\texttt{k}\}$. 

For example, 
\begin{multline*}
\AA_{3}=\{\texttt{3}, \texttt{2}+\texttt{1}_\texttt{1}, \texttt{2}+\texttt{1}_\texttt{2}, \texttt{1}_\texttt{1}+\texttt{2}, \texttt{1}_\texttt{2}+\texttt{2}, \texttt{1}_\texttt{1}+\texttt{1}_\texttt{1}+\texttt{1}_\texttt{1}, \texttt{1}_\texttt{1}+\texttt{1}_\texttt{1}+\texttt{1}_\texttt{2}, \texttt{1}_\texttt{1}+\texttt{1}_\texttt{2}+\texttt{1}_\texttt{1}, \\  \texttt{1}_\texttt{1}+\texttt{1}_\texttt{2}+\texttt{1}_\texttt{2}, \texttt{1}_\texttt{2}+\texttt{1}_\texttt{1}+\texttt{1}_\texttt{1}, \texttt{1}_\texttt{2}+\texttt{1}_\texttt{1}+\texttt{1}_\texttt{2},  \texttt{1}_\texttt{2}+\texttt{1}_\texttt{2}+\texttt{1}_\texttt{1}, \texttt{1}_\texttt{2}+\texttt{1}_\texttt{2}+\texttt{1}_\texttt{2}\}.
\end{multline*}
Therefore, $C(3)=13$.  Finally, let $\F_{n}$ denote the set of classical compositions of $n$ with parts in $\{\texttt{1}, \texttt{2}\}$. It is well-know that
\[
|\F_{n}| = F_{n+1} \quad \text{for all} \quad n\geq 1. 
\]

With the above notation, we have the following theorem.

\begin{theorem}\label{TheoremA}
There is a bijection from $\AA_{n}$ to $\F_{2n}$. So
\[
|\AA_{n}| = |\F_{2n}| = F_{2n+1} \quad \text{for all}\quad  n\geq 1.
\]
\end{theorem}

\begin{proof}
The result clearly holds for $n=1$, so we assume that $n\geq 2$. We shall define the map $\varphi$ from $\AA_{n}$ to $\F_{2n}$ as follows:
\[
(\texttt{1}_{\texttt{1}})\longmapsto (\texttt{1},\texttt{1}), \qquad\qquad  (\texttt{1}_{\texttt{2}})\longmapsto (\texttt{2}),
\]
\[
(\texttt{2})\longmapsto (\texttt{1},\texttt{2},\texttt{1}), \qquad (3)\longmapsto (\texttt{1},\texttt{2},\texttt{2},\texttt{1}), \qquad \ldots \qquad ,(n)\longmapsto (\texttt{1},\underbrace{\texttt{2},\ldots, \texttt{2}}_{(n-1)\text{-times}},\texttt{1})
\]
For every composition $\sigma=(\sigma_1, \sigma_2, \ldots, \sigma_\ell)$ in  $\AA_n$, we define
\[
\varphi(\sigma) =(\varphi(\sigma_1), \varphi(\sigma_2), \ldots, \varphi(\sigma_\ell)) .
\]
For example, 
\[
\varphi(\texttt{3},\texttt{1}_\texttt{2},\texttt{2},\texttt{2},\texttt{1}_\texttt{1},\texttt{4})=(\texttt{1},\texttt{2},\texttt{2},\texttt{1},\texttt{2},\texttt{1},\texttt{2},\texttt{1},\texttt{1},\texttt{2},\texttt{1},\texttt{1},\texttt{1},\texttt{1},\texttt{2},\texttt{2},\texttt{2},\texttt{1}).
\] 
Note that if $\sigma \in\AA_n$, then $\varphi(\sigma)$ is a composition of $2n$ with parts in $\{\texttt{1},\texttt{2}\}$, i.e., $\varphi(\sigma)\in \F_{2n}$ for all $\sigma \in \AA_{n}$. Thus $\varphi$ is well defined.  

Let $(\alpha_1, \ldots , \alpha_{m}), (\beta_1 , \ldots , \beta_s)\in \AA_{n}$ and suppose that $\varphi(\alpha_1 , \ldots , \alpha_{m}) = \varphi(\beta_1 , \ldots , \beta_s)$. By definition, we get that $m=s$ and $\varphi(\alpha_i) =\varphi(\beta_i)$ for all $i\in \{1,2,\ldots,m\}$.  Hence $\alpha_i = \beta_i$ for all $\left\{1,2,\ldots,m\right\}$ and so $(\alpha_1 , \ldots , \alpha_{m}) = (\beta_1 , \ldots , \beta_s)$. Thus $\varphi$ is injective. 

It remains to prove that $\varphi$ is surjective. In order to do so, let $\beta =( \beta_{1}, \ldots ,\beta_{\ell})\in\F_{2n}$. Notice that $\beta_1 = \texttt{1}$ or $\beta_1 = \texttt{2}$. Suppose first that $\beta_1=\texttt{1}$. In this case, since $\beta\in\F_{2n}$, we have that $\beta_i=\texttt{1}$ for some $i\in \{2,\ldots,\ell\}$. Let $j\in\{2,\ldots,\ell\}$ be the lowest index such that $\beta_{j}=\texttt{1}$. If $j=\ell$, then $\beta=\varphi(\ell-1)$. If $j=2$, then we get that $\beta = (\varphi(\texttt{1}_\texttt{1}),\beta^{\prime})$ for some $\beta^{\prime}\in\F_{2n-2}$. Now, if $2&lt;j&lt;\ell$, then $\beta = (\varphi(j-1),\beta^{\prime})$ for some $\beta^{\prime}\in\F_{2n-2j+2}$. If, on the contrary, $\beta_1 = \texttt{2}$, then we have that $\beta = (\varphi(\texttt{1}_\texttt{2}),\beta^{\prime})$ for some $\beta^{\prime}\in\F_{2n-2}$.

We conclude from the previous analysis that $\beta =\varphi(\ell-1)$ or $\beta = (\varphi(\alpha_1),\beta^{\prime})$ for some $\alpha_1\in\{\texttt{1}_\texttt{1},\texttt{1}_\texttt{2},\texttt{j-1}\}$ and $\beta^{\prime}\in\F_{2n-2\alpha_1}$. If $\beta =\varphi(\ell-1)$, then we are through. Otherwise, we repeat the argument given above with $\beta$ replaced by $\beta^{\prime}$. Repeating the above argument, as many times as needed, we finally obtain that $\beta = \varphi(\alpha_1 , \ldots , \alpha_m)$ for some $m\geq 2$ and $\alpha_{i}\in \{\texttt{1}_\texttt{1},\texttt{1}_\texttt{2}, \texttt{2},\ldots,\ell-1\}$ for all $i\in\{1,\ldots,m\}$. Thus $\varphi$ is surjective, and so the proof of Theorem \ref{TheoremA} is complete. For example,  if $\beta=(\texttt{2},\texttt{1},\texttt{2},\texttt{1},\texttt{1},\texttt{1},\texttt{1},\texttt{2}, \texttt{2}, \texttt{1},\texttt{2})$, then 
\[
\beta=(\varphi(\texttt{1}_\texttt{2}), \varphi(\texttt{2}), \varphi(\texttt{1}_\texttt{1}), \varphi(\texttt{3}), \varphi(\texttt{1}_\texttt{2})). 
\]
\end{proof}

By using the above theorem and taking into account that the compositions of $n$ use parts at most $n$, we have the following corollary.

\begin{corollary}\label{CorollaryA}
Let $k\geq 2$ an integer. Then
\[
C_{k}(n) = |\AA_n| = F_{2n+1} \quad\text{holds for all $n$,}\quad 1\leq n \leq k.
\]
\end{corollary}

The following result establishes a relationship between compositions with parts in the set $\{\texttt{1}_\texttt{1},\texttt{1}_\texttt{2},\texttt{2},\ldots,\texttt{k}\}$ and the $k$-generalized Pell numbers.

\begin{theorem}
The generalized Pell number $P_{n+1}^{(k)}$ counts the number of  compositions of $n$ with parts in the set $\{\texttt{1},\texttt{2},\ldots,\texttt{k}\}$ such that the summand $\texttt{1}$ can take two colors. Namely,  
\begin{equation}\label{Equation1}
C_{k}(n) = P_{n+1}^{(k)}, \quad \quad \text{for all}\quad n\geq 1.
\end{equation}
\end{theorem}

\begin{proof}
Let $\sigma$ be a  generalized bi-colored  composition of $n$ with parts in the set $\{\texttt{1},\texttt{2},\ldots,\texttt{k}\}$. If $\sigma$ starts with $\texttt{1}$, then it must be followed by a bi-colored generalized composition of $n-1$ with parts in the set $\{\texttt{1},\texttt{2},\ldots,\texttt{k}\}$. Since the summand $\texttt{1}$ can take two colors, we have $2C_{k}(n-1)$ possibilities for $\sigma$ in this case. Now, if $\sigma$ starts with $\sigma_{1}\in\left\{\texttt{2},\texttt{3},\ldots, \texttt{k} \right\}$, then $\sigma$ must be followed by a composition of $n-\sigma_{1}$. Thus, by the addition principle, the number of generalized  bi-colored compositions of $n$ with parts in the set $\{\texttt{1},\texttt{2},\ldots,\texttt{k}\}$ is given by $C_{k}(n) = 2C_{k}(n-1)+C_{k}(n-2)+\cdots+C_{k}(n-k)$. Finally, note that $C_{k}(n)$ satisfies the $k-$generalized Pell recurrence with $C_{k}(1)=2=P_{2}^{(k)}$ and $C_{k}(2)=5=P_{3}^{(k)}$. This proves \eqref{Equation1}.
\end{proof}

Finally, from Corollary \ref{CorollaryA} we deduce the following
statement, which was also proved by Kili\c{c} \cite{Kilic02} by using
arithmetic arguments.

\begin{corollary}\label{CorollaryB}
Let $k\geq 2$ be an integer. Then
\[
P_{n+1}^{(k)} =  F_{2n+1}\quad \text{holds for all}\quad 1\leq n \leq k.
\]
\end{corollary}


\section{Acknowledgment}
We thank the reviewer for his/her thorough review and highly appreciate
the comments and suggestions, which significantly contributed to
improving the quality of the publication. J.~J.~B. was partially
supported by Projects VRI ID 4689 (Universidad del Cauca) and Colciencias
110371250560. J.~L.~H. thanks the Universidad del Cauca for support during
his Ph.D. studies.  J.~L.~R. was partially supported by Universidad
Nacional de Colombia, Project No.~46240. The third author thanks an
invitation from the Department of Mathematics of Universidad del Cauca,
Popay\'an,   Colombia, where the presented work was initiated.

\begin{thebibliography}{99}

\bibitem{Benja} A.~Benjamin and  J.~Quinn, \emph{Proofs that Really Count: The Art of Combinatorial Proof}, Dolciani Mathematical Expositions \textbf{27}, Mathematical Association of America, 2003.

\bibitem{Brent} R.~P.~Brent, On the periods of generalized Fibonacci recurrences, \emph{Math. Comp.} \textbf{63} (1994), 389--401.

\bibitem{CoHo} C.~Cooper and F.~T.~Howard, Some identities for $r$-Fibonacci numbers, \emph{Fibonacci Quart.} {\bf 49} (2011), 231--243.

\bibitem{FLORAM2} \'E.~Czabarka, R.~Fl\'orez, L.~Junes,  and J.~L.~Ram\'irez, Enumerations of peaks and valleys on non-decreasing Dyck paths,  \emph{Discrete Math.} \textbf{341} (2018), 2789--2807.

\bibitem{D-Du} G.~P. ~Dresden and Z.~Du, A simplified Binet formula for $k$-generalized Fibonacci numbers, \emph{J. Integer Sequences}  {\bf 17} (2014), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Dresden/dresden6.html}{Article 14.4.7}.

\bibitem{FLORAM} R.~Fl\'orez, L.~Junes,  and J.~L.~Ram\'irez,  Further results on paths in an $n$-dimensional cubic lattice,  \emph{J. Integer Sequences} \textbf{21} (2018),  \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Florez/florez4.html}{Article 18.1.2}.

\bibitem{Heberle-thesis} C.~Heberle,  \emph{A combinatorial approach to $r$-Fibonacci numbers}. HMC Senior Thesis, Harvey Mudd College, 2012.

\bibitem{Kilic} E.~Kili\c{c}, The Binet formula, sums and representations of generalized Fibonacci $p-$numbers, \emph{European J. Combin.} \textbf{29} (2008), 701--711.

\bibitem{Kilic02} E.~Kili\c{c}, On the usual Fibonacci and generalized order-$k$ Pell number, \emph{Ars. Comb.}  \textbf{109} (2013), 391--403.

\bibitem{Kos01} T.~Koshy, \emph{Fibonacci and Lucas Number with Applications}, A Wiley-Interscience Publications, 2001. 

\bibitem{koshy2} T.~Koshy, \emph{Pell and Pell-Lucas Numbers with Applications}, Springer-Verlag,  2014.

\bibitem{MN}  D.~Merlini and M.~Nocentini, Patterns in Riordan arrays, in \emph{Second International Symposium on Riordan Arrays and Related Topics},  Lecco, Italy, 2015, pp.\ 22.

\bibitem{Sprugnoli2} D.~Merlini, D.~G.~Rogers, R.~Sprugnoli, and M.~C.~Verri, Underdiagonal lattice paths with unrestricted steps, \emph{Discrete Appl. Math.} {\bf 91} (1999) 197--213.

\bibitem{Muskat}  J.~B.~Muskat, Generalized Fibonacci and Lucas sequences and rootfinding methods, \emph{Math. Comp.} \textbf{61} (1993), 365--372.

\bibitem{RAM} J.~L.~Ram\'irez and V.~F.~Sirvent, A generalization of the
$k$-bonacci sequence from Riordan arrays, \emph{Electron. J. Combin.}
{\bf 22} (2015) Paper \#P1.38.

\bibitem{RAM2} J.~L.~Ram\'irez and V.~F.~Sirvent, Generalized Schr\"{o}der matrix and its combinatorial interpretation, \emph{Linear Multilinear Algebra} {\bf 66.2} (2018) 418--433.

\bibitem{RAM3}   J.~L.~Ram\'irez and V.~F.~Sirvent,  A $q$-analogue of the biperiodic Fibonacci sequence, \emph{J. Integer Sequences}   \textbf{19} (2016), \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Ramirez/ramirez9.html}{Article 16.4.6}.
 
\bibitem{Riordan2} L.~W.~Shapiro, S.~Getu, W.~Woan, and L.~Woodson, The Riordan group, \emph{Discrete Appl. Math.} {\bf 34} (1991) 229--239.

\bibitem{Sprugnoli} R.~Sprugnoli, Riordan arrays and combinatorial sums, \emph{Discrete  Math.} {\bf 132} (1994)  267--290.

\bibitem{Yang} S.-L.~Yang, Y.-N.~Dong, and T.-X.~He, Some matrix identities on colored Motzkin paths, \emph{Discrete  Math.} {\bf 340} (2017)  3081--3091.

\bibitem{Yang2} S.-L.~Yang, Y.-N.~Dong, T.-X. He, and Y.-X.~Xu, A unified approach for the Catalan matrices by using Riordan arrays,  \emph{Linear Algebra Appl.} {\bf 558} (2018), 25--43.

\bibitem{Yang3} S.-L.~Yang, Y.-N.~Dong, L.~Yang, and J.~Yin,  Half of a Riordan array and restricted lattice paths,  \emph{Linear Algebra Appl.} {\bf 537} (2018)  1--11.

\bibitem{Yang4} S.-L.~Yang and  Y.-Y.~Gao, The Pascal rhombus and Riordan arrays, \emph{Fibonacci Quart.} {\bf 56} (2018),  337--347.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }
Pell number, generalized Pell number,  generating function, Riordan array.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000129},
\seqnum{A038207},
\seqnum{A077939}, and
\seqnum{A102036}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 13 2019; 
revised version received  October 2 2019; October 4 2019.
Published in {\it Journal of Integer Sequences}, December 31 2019.

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