Combinatorial Interpretation of Generalized Pell Numbers

Jhon J. Bravo^{1} and Jose L. Herrera

Departamento de Matemáticas

Universidad del Cauca Popayán Colombia

  jbravo@unicauca.edu.co
joseherrera@unicauca.edu.co

José L. Ramírez Departamento de Matemáticas

Universidad Nacional de Colombia Bogotá Colombia

  jlramirezr@unal.edu.co

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.

1 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}^{∞} 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.

1Corresponding author.

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 [3] and Dresden and Du [5] investigated a generalization of the Fibonacci sequence given by a recurrence relation of a higher order. They considered, for an integer k ≥ 2, the kgeneralized Fibonacci sequence, which is like the Fibonacci sequence but starts with the terms 0, 0, …, 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 [7]). Other generalizations of the Fibonacci sequence have also been studied (see, for example, [2, 8, 14, 17]).

Also, there is the Pell sequence, which is as important as the Fibonacci sequence. The Pell sequence P = (P_{n})_{n=0}^{∞} is defined by the recurrence P_{n} = 2P_{n−1} + P_{n−2} for all n ≥ 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 [10, 11]. The Pell sequence appears in OEIS as \underline{A000129}. The first few terms of this sequence are

0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, …

This sequence has many interesting combinatorial and arithmetical properties; see, e.g., [11]. 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 bi-colored composition of a positive integer n we mean a sequence of positive integers σ = (σ_{1}, σ_{2}, …, σ_{ℓ}) such that σ_{1} + σ_{2} + ⋯ + σ_{ℓ} = n, σ_{i} ∈ {1, 2}, and the summand 1 can come in one of 2 different colors. The colors of the summand 1 are denoted by subscripts 1_{1} and 1_{2}. For example, the bi-colored compositions of 3 are

2 + 1_{1}, 2 + 1_{2}, 1_{1} + 2, 1_{2} + 2, 1_{1} + 1_{1} + 1_{1}, 1_{2} + 1_{1} + 1_{1}, 1_{1} + 1_{2} + 1_{1},
1_{1} + 1_{1} + 1_{2}, 1_{1} + 1_{2} + 1_{2}, 1_{2} + 1_{1} + 1_{2}, 1_{2} + 1_{2} + 1_{1}, 1_{2} + 1_{2} + 1_{2}.

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 [1]. If we use white and black squares and non-colored dominoes we obtain a different combinatorial interpretation for the Pell numbers. For example, Figure 1 shows the different ways to tiling a 3-board.

Figure 1: Different ways to tile 3-boards.

In this paper, we are interested in a generalization of the Pell sequence called the kgeneralized Pell sequence or, for simplicity, the k-Pell sequence P^{(k)} = (P_{n}^{(k)})_{n=−(k−2)}^{∞} defined by the recurrence

P_{n}^{(k)} = 2P_{n−1}^{(k)} + P_{n−2}^{(k)} + ⋯ + P_{n−k}^{(k)} for all n ≥ 2,

with the initial values P_{−(k−2)}^{(k)} = P_{−(k−3)}^{(k)} = ⋯ = P_{0}^{(k)} = 0 and P_{1}^{(k)} = 1. We refer to P_{n}^{(k)} as the nth 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.

2 A combinatorial interpretation: lattice paths

Let S be a fixed subset of ℤ × ℤ. A lattice path Γ of length ℓ with steps in S is a ℓtuple of directed steps of S. That is Γ = (s_{1}, …, s_{ℓ}) where s_{i} ∈ S for 1 ≤ i ≤ ℓ. 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 := [a(n − m, m)]_{n,m≥0} = [\binom{n}{m}]_{n,m≥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 \underline{A000045}, i.e., for n ≥ 1

F_{n} = ∑_{i=0}^{⌊ \frac{n−1}{2} ⌋} \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, …, ⌊(n − 1)/2⌋. For example, Figure 2 shows the paths for n = 5, i.e., the paths counted by the Fibonacci number F_{5} = 5.

Figure 2: Lattices paths counted by the Fibonacci number F_{5}.

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

Let ℙ_{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), …, D_{k} = (1, k)}.

In Figure 3, we show all lattice paths of the set ℙ_{2}(1, 3).

Figure 3: Lattices paths in ℙ_{2}(1, 3).

Let p_{k}(n, m) be the number of lattice paths of ℙ_{k}(n, m), i.e., p_{k}(n, m) := |ℙ_{k}(n, m)|. Since the last step on any path from ℙ_{k}(n, m) is one of S_{k}, we obtain the recurrence relation:

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) + ⋯ + p_{k}(n − 1, m − k), (1)

with n ≥ 1, m ≥ 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

Let P_{n}^{(k)}(x) be the ordinary generating function of the sequence {p_{k}(n, m)}_{m}. That is,

P_{n}^{(k)}(x) = ∑_{i≥0} p_{k}(n, i)x^{i}.

In Theorem 1 we find an expression for the generating function P_{n}^{(k)}(x).

Theorem 1. We have

P_{n}^{(k)}(x) = \frac{(1 + x + x^{2} + ⋯ + x^{k})^{n}}{(1 − x)^{n+1}} .

Proof. From equation (1), we obtain the relation

P_{n}^{(k)}(x) = P_{n−1}^{(k)}(x) + xP_{n}^{(k)}(x) + xP_{n−1}^{(k)}(x) + x^{2}P_{n−1}^{(k)}(x) + ⋯ + x^{k}P_{n−1}^{(k)}(x). Thus

P_{n}^{(k)}(x) = \frac{1 + x + x^{2} + ⋯ + x^{k}}{1 − x} P_{n−1}^{(k)}(x).

Since P_{0} = 1/(1 − x), we obtain the desired result. Corollary 2. The number of lattice paths p_{k}(n, m) is given by

p_{k}(n, m) = ∑_{ℓ_{0}+ℓ_{1}+···+ℓ_{k}=n} \binom{n}{ℓ_{0}, ℓ_{1}, …, ℓ_{k}}\binom{n + m − t}{n},

where t = ∑_{s=0}^{k} sℓ_{s} and

\binom{n}{n_{1}, …, n_{m}} = \frac{n!}{n_{1}! ⋯ n_{m}!}

is the multinomial coefficient. Proof. From the multinomial theorem, the generating function

\frac{1}{(1 − x)^{n+1}} = ∑_{i≥0} \binom{n + i}{i}x^{i},

and Theorem 1, we have that

p_{k}(n, m) = [x^{m}]P_{n}^{(k)}(x) = [x^{m}]\frac{(1 + x + x^{2} + ⋯ + x^{k})^{n}}{(1 − x)^{n+1}}

= [x^{m}] ∑_{ℓ_{0}+ℓ_{1}+···+ℓ_{k}=n} \binom{n}{ℓ_{0}, ℓ_{1}, …, ℓ_{k}} ∏_{s=0}^{k} x^{sℓ_{s}} ∑_{i≥0} \binom{n + i}{i}x^{i}

= [x^{m}] ∑_{ℓ_{0}+ℓ_{1}+···+ℓ_{k}=n} ∑_{i≥0} \binom{n}{ℓ_{0}, ℓ_{1}, …, ℓ_{k}}\binom{n + i}{i}x^{t+i},

where t = ∑_{s=0}^{k} sℓ_{s}. By comparing the m-th coefficient we obtain the desired result.

For example,

p_{2}(1, 3) = ∑_{ℓ_{0}+ℓ_{1}+ℓ_{2}=1} \binom{1}{ℓ_{0}, ℓ_{1}, ℓ_{2}}\binom{1 + 3 − (ℓ_{1} + 2ℓ_{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.

In Figure 3, we show the corresponding lattice paths.

Let P_{k} := [q_{k}(n, m)]_{n,m≥0} be the array defined by

q_{k}(n, m) = \begin{cases}p_{k}(m, n − m), & if n ≥ m; \\ 0, & if n < m. \end{cases}

For example, the first few rows of the array P_{2} are as follows (see also \underline{A102036}).

P_{2} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 6 & 5 & 1 & 0 & 0 & 0 & 0 \\ 1 & 9 & 15 & 7 & 1 & 0 & 0 & 0 \\ 1 & 12 & 33 & 28 & 9 & 1 & 0 & 0 \\ 1 & 15 & 60 & 81 & 45 & 11 & 1 & 0 \\ 1 & 18 & 96 & 189 & 161 & 66 & 13 & 1 \\ ⋮ & & & ⋮ & & & & ⋮ \end{matrix} )

This new family of matrices P_{k} are an example of a Riordan array. Remember that an infinite lower triangular matrix is called a Riordan array [18] if its kth column satisfies the generating function g(x) (f(x))^{k} for k ≥ 0, where g(x) and f(x) are formal power series with g(0) ≠ 0, f(0) = 0 and f′(0) ≠ 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}, …)^{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)) = (g(x)h (f(x)) , l (f(x))) .

We recall that the set of all Riordan matrices is a group under the operator “ ∗ ” [18]. The identity element is I = (1, x), and the inverse of (g(x), f(x)) is

(g(x), f(x))^{−1} = (1/ (g ∘ \overline{f}) (x), \overline{f}(x)) ,

where \overline{f}(x) is the compositional inverse of f(x). For example, the Pascal matrix is given by the Riordan array

(\frac{1}{1 − x}, \frac{x}{1 − x}) .

Several authors have used Riordan arrays to study lattice paths; see for example [4, 6, 13, 15, 16, 19, 20, 21, 22, 23].

From the definition of Riordan array and Theorem 1 we obtain the following theorem.

Theorem 3. The matrix P_{k} is a Riordan array given by

P_{k} = (\frac{1}{1 − x}, x\frac{1 + x + x^{2} + ⋯ + x^{k}}{1 − x} ) .

Proof. The (n, m)-th entry of the Riordan array is given by

[x^{n}]\frac{1}{1 − x} (x\frac{1 + x + x^{2} + ⋯ + x^{k}}{1 − x} )^{m} = [x^{n−m}]\frac{(1 + x + x^{2} + ⋯ + x^{k})^{m}}{(1 − x)^{m+1}}
= [x^{n−m}]P_{m}^{(k)}(x)
= p_{k}(m, n − m) = q_{k}(n, m).

Hence the matrices are the same.

Let R_{k}(x) be the generating function for the rows sums of the matrix P_{k}. In Theorem 4 we give an expression for this generating function.

Theorem 4. The generating function R_{k}(x) is given by

R_{k}(x) = \frac{1}{1 − 2x − x^{2} − ⋯ − x^{k+1}} .

Proof. From the summation property for the Riordan arrays we have

R_{k}(x) = P_{k} (\frac{1}{1 − x}) = \frac{1}{1 − x} (\frac{1}{1 − x\frac{1+x+x^{2}+···+x^{k}}{1−x}} ) = \frac{1}{1 − 2x − x^{2} − ⋯ − x^{k+1}} .

By using standard methods, it is possible to prove that the ordinary generating function of the k-Pell sequence is

∑_{n≥0} P_{n}^{(k)}x^{n} = \frac{1}{1 − 2x − x^{2} − ⋯ − x^{k}} .

Thus we have the following corollary.

Corollary 5. The k-Pell numbers P_{n}^{(k)} coincide with the row sum of the matrix P_{k−1}.

For example, the row sum of the matrix P_{2} coincides with the 3-Pell numbers \underline{A077939}:

1, 2, 5, 13, 33, 84, 214, 545, 1388, 3535, 9003, ⋯

In Corollary 6 we deduce a possibly new combinatorial identity for the k-Pell numbers.

Corollary 6. The k-Pell numbers P_{n}^{(k)} are given by the combinatorial identity

P_{n}^{(k)} = ∑_{i=0}^{n} ∑_{ℓ_{0}+ℓ_{1}+···+ℓ_{k−1}=i} \binom{i}{ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}}\binom{n − t}{i},

where t = ∑_{j=0}^{k−1} jℓ_{j}.

Proof. From Corollaries 2 and 5 we have

P_{n}^{(k)} = ∑_{i=0}^{n} q_{k−1}(n, i) = ∑_{i=0}^{n} p_{k−1}(i, n − i) = ∑_{i=0}^{n} ∑_{ℓ_{0}+ℓ_{1}+···+ℓ_{k−1}=i} \binom{i}{ℓ_{0}, ℓ_{1}, …, ℓ_{k−1}}\binom{n − t}{i}.

Finally, from the relation P_{n}^{(k)} = ∑_{i=0}^{n} p_{k−1}(i, n−i) we deduce the following combinatorial interpretation.

Theorem 7. 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, …, n, with step set

S_{k} = {H = (1, 0), V = (0, 1), D_{1} = (1, 1), D_{2} = (1, 2), …, D_{k} = (1, k)}.

For example, the 3-Pell number P_{4}^{(3)} = 13 counts the paths of Figure 4.

Figure 4: Lattices paths counted by P_{4}^{(3)}.

We recall that the Fibonacci numbers are equal to the sum on the rising diagonal in the Pascal matrix. In Theorem 8 we give an analogue of this result for the k-Pell sequence.

Theorem 8. The k-Pell numbers P_{n}^{(k)} coincide with the sum of the elements on rising diagonal lines in the Riordan array

Q_{k} := (\frac{1}{1 − 2x}, x\frac{1 + x + x^{2} + ⋯ + x^{k−2}}{1 − 2x} ) .

Proof. The generating function of the sum of the elements on rising diagonal lines in the above Riordan array is

\frac{1}{1 − 2x} (\frac{1}{1 − x^{2} (\frac{1+x+x^{2}+···+x^{k−2}}{1−2x} )}) =\frac{1}{1 − 2x − x^{2} − ⋯ − x^{k}} = ∑_{n≥0} P_{n}^{(k)}x^{n}.

For example, the diagonal sum of the Riordan array Q_{2} (see also \underline{A038207}) coincides with the classical Pell numbers

Q_{2} = (\frac{1}{1 − 2x}, \frac{x}{1 − 2x}) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 8 & 12 & 6 & 1 & 0 & 0 & 0 & 0 \\ 16 & 32 & 24 & 8 & 1 & 0 & 0 & 0 \\ 32 & 80 & 80 & 40 & 10 & 1 & 0 & 0 \\ 64 & 192 & 240 & 160 & 60 & 12 & 1 & 0 \\ 128 & 448 & 672 & 560 & 280 & 84 & 14 & 1 \\ ⋮ & & & & ⋮ & & & ⋮ \end{matrix} ) .

The diagonal sum of the Riordan array Q_{3} coincides with the 3-Pell numbers

Q_{3} = (\frac{1}{1 − 2x}, x\frac{1 + x}{1 − 2x}) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 5 & 1 & 0 & 0 & 0 & 0 & 0 \\ 8 & 16 & 8 & 1 & 0 & 0 & 0 & 0 \\ 16 & 44 & 37 & 11 & 1 & 0 & 0 & 0 \\ 32 & 112 & 134 & 67 & 14 & 1 & 0 & 0 \\ 64 & 272 & 424 & 305 & 106 & 17 & 1 & 0 \\ 128 & 640 & 1232 & 1168 & 584 & 154 & 20 & 1 \\ ⋮ & & & ⋮ & & & & ⋮ \end{matrix} ) .

Figure 5: Matrix P_{2} (mod 2).

The Riordan arrays obtained in this section show interesting patterns if you evaluated their entries mod 2. In Figure 5 we show the fractal structure of the matrix P_{2}. Notice that Merlini and Nocentini [12] 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.

3 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 generalized bi-colored composition of n as a sequence of positive integers σ = (σ_{1}, σ_{2}, …, σ_{ℓ}) such that σ_{1} + σ_{2} + ⋯ + σ_{ℓ} = n, and the summand 1 can take two colors. The colors of the summand 1 are denoted by subscripts 1_{1} and 1_{2}. Further, the positive integers σ_{i} are called parts of the composition. We let 𝔸_{n} denote the set of all generalized bi-colored compositions of n and let C(n) denote the number of elements in 𝔸_{n}, i.e., C(n) := |𝔸_{n}|. We also use C_{k}(n) to denote the number of generalized bi-colored compositions of n with parts in the set {1, 2, …, k}.

For example,

  𝔸_{3} = {3, 2 + 1_{1}, 2 + 1_{2}, 1_{1} + 2, 1_{2} + 2, 1_{1} + 1_{1} + 1_{1}, 1_{1} + 1_{1} + 1_{2}, 1_{1} + 1_{2} + 1_{1},
                   1_{1} + 1_{2} + 1_{2}, 1_{2} + 1_{1} + 1_{1}, 1_{2} + 1_{1} + 1_{2}, 1_{2} + 1_{2} + 1_{1}, 1_{2} + 1_{2} + 1_{2}}.

Therefore, C(3) = 13. Finally, let 𝔽_{n} denote the set of classical compositions of n with parts in {1, 2}. It is well-know that

|𝔽_{n}| = F_{n+1} for all n ≥ 1.

With the above notation, we have the following theorem.

Theorem 9. There is a bijection from 𝔸_{n} to 𝔽_{2n}. So

|𝔸_{n}| = |𝔽_{2n}| = F_{2n+1} for all n ≥ 1.

Proof. The result clearly holds for n = 1, so we assume that n ≥ 2. We shall define the map φ from 𝔸_{n} to 𝔽_{2n} as follows:

(1_{1}) ⟼ (1, 1), (1_{2}) ⟼ (2),
(2) ⟼ (1, 2, 1),  (3) ⟼ (1, 2, 2, 1),  …  , (n) ⟼ (1, \underbrace{2, …, 2}_{(n−1)-times}, 1)

For every composition σ = (σ_{1}, σ_{2}, …, σ_{ℓ}) in 𝔸_{n}, we define

φ(σ) = (φ(σ_{1}), φ(σ_{2}), …, φ(σ_{ℓ})).

For example,

φ(3, 1_{2}, 2, 2, 1_{1}, 4) = (1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1).

Note that if σ ∈ 𝔸_{n}, then φ(σ) is a composition of 2n with parts in {1, 2}, i.e., φ(σ) ∈ 𝔽_{2n} for all σ ∈ 𝔸_{n}. Thus φ is well defined.

Let (α_{1}, …, α_{m}), (β_{1}, …, β_{s}) ∈ 𝔸_{n} and suppose that φ(α_{1}, …, α_{m}) = φ(β_{1}, …, β_{s}). By definition, we get that m = s and φ(α_{i}) = φ(β_{i}) for all i ∈ {1, 2, …, m}. Hence α_{i} = β_{i} for all {1, 2, …, m} and so (α_{1}, …, α_{m}) = (β_{1}, …, β_{s}). Thus φ is injective.

It remains to prove that φ is surjective. In order to do so, let β = (β_{1}, …, β_{ℓ}) ∈ 𝔽_{2n}. Notice that β_{1} = 1 or β_{1} = 2. Suppose first that β_{1} = 1. In this case, since β ∈ 𝔽_{2n}, we have that β_{i} = 1 for some i ∈ {2, …, ℓ}. Let j ∈ {2, …, ℓ} be the lowest index such that β_{j} = 1. If j = ℓ, then β = φ(ℓ − 1). If j = 2, then we get that β = (φ(1_{1}), β′) for some β′ ∈ 𝔽_{2n−2}. Now, if 2 < j < ℓ, then β = (φ(j −1), β′) for some β′ ∈ 𝔽_{2n−2j+2}. If, on the contrary, β_{1} = 2, then we have that β = (φ(1_{2}), β′) for some β′ ∈ 𝔽_{2n−2}.

We conclude from the previous analysis that β = φ(ℓ − 1) or β = (φ(α_{1}), β′) for some α_{1} ∈ {1_{1}, 1_{2}, j-1} and β′ ∈ 𝔽_{2n−2α_{1}}. If β = φ(ℓ − 1), then we are through. Otherwise, we repeat the argument given above with β replaced by β′. Repeating the above argument, as many times as needed, we finally obtain that β = φ(α_{1}, …, α_{m}) for some m ≥ 2 and α_{i} ∈ {1_{1}, 1_{2}, 2, …, ℓ − 1} for all i ∈ {1, …, m}. Thus φ is surjective, and so the proof of Theorem 9 is complete. For example, if β = (2, 1, 2, 1, 1, 1, 1, 2, 2, 1, 2), then

β = (φ(1_{2}), φ(2), φ(1_{1}), φ(3), φ(1_{2})).

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

Corollary 10. Let k ≥ 2 an integer. Then

C_{k}(n) = |𝔸_{n}| = F_{2n+1} holds for all n, 1 ≤ n ≤ k.

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

Theorem 11. The generalized Pell number P_{n+1}^{(k)} counts the number of compositions of n with parts in the set {1, 2, …, k} such that the summand 1 can take two colors. Namely,

C_{k}(n) = P_{n+1}^{(k)},  for all n ≥ 1.  (2)

Proof. Let σ be a generalized bi-colored composition of n with parts in the set {1, 2, …, k}. If σ starts with 1, then it must be followed by a bi-colored generalized composition of n − 1 with parts in the set {1, 2, …, k}. Since the summand 1 can take two colors, we have 2C_{k}(n − 1) possibilities for σ in this case. Now, if σ starts with σ_{1} ∈ {2, 3, …, k}, then σ must be followed by a composition of n − σ_{1}. Thus, by the addition principle, the number of generalized bi-colored compositions of n with parts in the set {1, 2, …, k} is given by C_{k}(n) = 2C_{k}(n − 1) + C_{k}(n − 2) + ⋯ + 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 (2).

Finally, from Corollary 10 we deduce the following statement, which was also proved by Kiliç [9] by using arithmetic arguments.

Corollary 12. Let k ≥ 2 be an integer. Then

P_{n+1}^{(k)} = F_{2n+1} holds for all 1 ≤ n ≤ k.

4 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án, Colombia, where the presented work was initiated.

References

[1] A. Benjamin and J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Dolciani Mathematical Expositions 27, Mathematical Association of America, 2003.

[2] R. P. Brent, On the periods of generalized Fibonacci recurrences, Math. Comp. 63 (1994), 389–401.

[3] C. Cooper and F. T. Howard, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), 231–243.

[4] É. Czabarka, R. Flórez, L. Junes, and J. L. Ramírez, Enumerations of peaks and valleys on non-decreasing Dyck paths, Discrete Math. 341 (2018), 2789–2807.

[5] G. P. Dresden and Z. Du, A simplified Binet formula for k-generalized Fibonacci numbers, J. Integer Sequences 17 (2014), Article 14.4.7.

[6] R. Flórez, L. Junes, and J. L. Ramírez, Further results on paths in an n-dimensional cubic lattice, J. Integer Sequences 21 (2018), Article 18.1.2.

[7] C. Heberle, A combinatorial approach to r-Fibonacci numbers. HMC Senior Thesis, Harvey Mudd College, 2012.

[8] E. Kiliç, The Binet formula, sums and representations of generalized Fibonacci p−numbers, European J. Combin. 29 (2008), 701–711.

[9] E. Kiliç, On the usual Fibonacci and generalized order-k Pell number, Ars. Comb. 109 (2013), 391–403.

[10] T. Koshy, Fibonacci and Lucas Number with Applications, A Wiley-Interscience Publications, 2001.

[11] T. Koshy, Pell and Pell-Lucas Numbers with Applications, Springer-Verlag, 2014.

[12] D. Merlini and M. Nocentini, Patterns in Riordan arrays, in Second International Symposium on Riordan Arrays and Related Topics, Lecco, Italy, 2015, pp. 22.

[13] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math. 91 (1999) 197–213.

[14] J. B. Muskat, Generalized Fibonacci and Lucas sequences and rootfinding methods, Math. Comp. 61 (1993), 365–372.

[15] J. L. Ramírez and V. F. Sirvent, A generalization of the k-bonacci sequence from Riordan arrays, Electron. J. Combin. 22 (2015) Paper #P1.38.

[16] J. L. Ramírez and V. F. Sirvent, Generalized Schröder matrix and its combinatorial interpretation, Linear Multilinear Algebra 66.2 (2018) 418–433.

[17] J. L. Ramírez and V. F. Sirvent, A q-analogue of the biperiodic Fibonacci sequence, J. Integer Sequences 19 (2016), Article 16.4.6.

[18] L. W. Shapiro, S. Getu, W. Woan, and L. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991) 229–239.

[19] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994) 267– 290.

[20] S.-L. Yang, Y.-N. Dong, and T.-X. He, Some matrix identities on colored Motzkin paths, Discrete Math. 340 (2017) 3081–3091.

[21] S.-L. Yang, Y.-N. Dong, T.-X. He, and Y.-X. Xu, A unified approach for the Catalan matrices by using Riordan arrays, Linear Algebra Appl. 558 (2018), 25–43.

[22] S.-L. Yang, Y.-N. Dong, L. Yang, and J. Yin, Half of a Riordan array and restricted lattice paths, Linear Algebra Appl. 537 (2018) 1–11.

[23] S.-L. Yang and Y.-Y. Gao, The Pascal rhombus and Riordan arrays, Fibonacci Quart. 56 (2018), 337–347.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 05A19. Keywords: Pell number, generalized Pell number, generating function, Riordan array.

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

Received July 13 2019; revised version received October 2 2019; October 4 2019. Published in Journal of Integer Sequences, December 31 2019.

Return to Journal of Integer Sequences home page.