\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*} &\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, \, \\ & \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)&=[x^m]P_n^{(k)}(x)=[x^m]\frac{(1+x+x^2+\cdots + x^k)^n}{(1-x)^{n+1}}\\ &=[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\\ &=[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)&=\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}\\ &=\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),& \text{ if } n\geq m;\\ 0,& \text{ if } n