Combinatorial Expressions Involving Fibonacci, Hyperfibonacci, and Incomplete

Fibonacci Numbers

Hacène Belbachir and Amine Belkhir USTHB, Faculty of Mathematics RECITS Laboratory, DG-RSDT

BP 32, El Alia 16111 Bab Ezzouar, Algiers

Algeria

hbelbachir@usthb.dz
hacenebelbachir@gmail.com
 abelkhir@usthb.dz
ambelkhir@gmail.com

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.

1 Introduction

The hyperfibonacci numbers F_{n}^{(r)} introduced recently by Dil and Mező [5]. There are defined by the relation

F_{n}^{(r)} = ∑_{k=0}^{n} F_{k}^{(r−1)}, with F_{n}^{(0)} = F_{n} and F_{0}^{(r)} = 0, F_{1}^{(r)} = 1,  (1)

where r is a positive integer and F_{n} is the n-th Fibonacci number defined recursively by

F_{n} = F_{n−1} + F_{n−2}, for n ≥ 2, and F_{0} = 0, F_{1} = 1.

The double recurrence relation for the hyperfibonacci numbers is given by

F_{n}^{(r)} = F_{n−1}^{(r)} + F_{n}^{(r−1)}.  (2)

The Fibonacci number F_{n+1} counts the number of tilings of a (1 × n)-board with cells labeled 1, 2, …, n using (1 × 1)-squares and (1 × 2)-dominoes. We follow the notation introduced by Benjamin and Quinn [4] and define f_{n} = F_{n+1} and get f_{n} = f_{n−1} + f_{n−2} with f_{0} = f_{1} = 1.

Figure 1: Tilings of length 1, 2 and 3 using squares and dominoes.

The following lemma will be used to establish our results.

Lemma 1. [4] The number of n-tilings using exactly k dominoes is

\binom{n − k}{k}, (k = 0, 1, …, ⌊n/2⌋) ,  (3)

where ⌊n⌋ is the integer part of n.

From Lemma 1, Benjamin and Quinn [4] 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

f_{n} = ∑_{k=0}^{⌊n/2⌋} \binom{n − k}{k}.  (4)

Our aim is to investigate, as the authors do for generalized Fibonacci and Lucas sequences [1, 2], 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.

2 Combinatorial interpretation

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

Theorem 2. Let f_{n}^{(r)} counts the number of ways to tile an (n + 2r)-board with at least r dominoes. Then f_{0}^{(r)} = 1, f_{n}^{(0)} = f_{n}, and for n ≥ 2,

f_{n}^{(r)} = f_{n−1}^{(r)} + f_{n}^{(r−1)}.  (5)

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 ≥ 2, an (n + 2r)-board can either end with a square or with a domino. If it ends with a square, then the remaining (n + 2r − 1)- board can be tiled with at least r dominoes in f_{n−1}^{(r)} ways. If it ends with a domino, then the remaining (n + 2r − 2)-board can be tiled with at least r − 1 dominoes in f_{n}^{(r−1)} ways.

As f_{0}^{(r)} = F_{1}^{(r)} = 1 and f_{n}^{(0)} = F_{n+1}^{(0)} = F_{n+1}, it seen that for n ≥ 0, we have f_{n}^{(r)} = F_{n+1}^{(r)}. Letting f_{−1}^{(r)} = 0, because there is not (2r − 1)-tiling with at least r dominoes. Now, we have a combinatorial interpretation for the hyperfibonacci numbers.

Theorem 3. For n,r ≥ 0, F_{n+1}^{(r)} = f_{n}^{(r)} counts the number of ways to tile an (n + 2r)-board with at least r dominoes.

The first few values of f_{n}^{(r)} are as follows:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ f_{n}^{(0)} & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 \\ f_{n}^{(1)} & 1 & 2 & 4 & 7 & 12 & 20 & 33 & 54 & 88 & 143 & 232 \\ f_{n}^{(2)} & 1 & 3 & 7 & 14 & 26 & 46 & 79 & 133 & 221 & 364 & 594 \\ f_{n}^{(3)} & 1 & 4 & 11 & 25 & 51 & 97 & 179 & 309 & 530 & 894 & 1490 \end{matrix}

Table 1: Some values of f_{n}^{(r)}

Theorem 4. For n ≥ 0, and r ≥ 1, we have

f_{n}^{(r)} = ∑_{k=r−1}^{⌊n/2⌋+r−1} (n + 2r − k − 1) f_{n}^{(r−1)}.  (6)

Proof. The number of ways to tile a board of length n + 2r − 2 with at least r − 1 dominoes is f_{n}^{(r−1)}. Now, to obtain an (n + 2r)-tilings with at least r dominoes from an (n + 2r − 2)-tilings with at least r − 1 dominoes, it suffices to add a domino. Let k (r − 1 ≤ k ≤ ⌊n/2⌋ + r − 1) be the number of dominos in an (n + 2r − 2)-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 (r − 1 ≤ k ≤ ⌊n/2⌋ + r − 1) dominoes is n + 2r − k − 1.

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

Theorem 5. For n ≥ 0, and r ≥ 1, we have

f_{n}^{(r)} = ∑_{k=0}^{n} \binom{n + r − k − 1}{r − 1}f_{k}.  (7)

Proof. Let k + 1,k + 2 (0 ≤ k ≤ n) 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 \binom{n+r−k−1}{r−1} ways to tile cells from k + 3 to n + 2r with exactly r − 1 dominoes. Thus, there are \binom{n+r−k−1}{r−1} f_{k} (n + 2r)-tilings with the r-th domino covering cells k + 1,k + 2. Summing over k, we get relation (7).

From the relation (7), 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.

Corollary 6. For n ≥ 0, and r ≥ 1, we have

f_{n}^{(r)} = ∑_{k=0}^{n} \binom{r − 1 + k}{k}f_{n−k}.  (8)

3 Closed form for hyperfibonacci numbers

The following theorem gives an explicit expression of f_{n}^{(r)} in terms of binomial coefficients.

Theorem 7. For n ≥ 0, and r ≥ 1, we have

f_{n}^{(r)} = ∑_{k=r}^{⌊n/2⌋+r} \binom{n + 2r − k}{k}.  (9)

Proof. An (n + 2r)-tiling with at least r dominoes can contains k dominoes where k = r, r+1, …, ⌊n/2⌋+r. Using Lemma 1, the number of (n + 2r)-tilings with exactly k dominoes is \binom{n+2r−k}{k}. Summing over k we get (9).

The relation (9) is a truncated diagonal sum of Pascal’s Triangle. This allow us to state the following:

Theorem 8. For n ≥ 0, and r ≥ 1, we have

f_{n}^{(r)} = f_{n+2r} − ∑_{k=0}^{r−1} \binom{n + 2r − k}{k}.  (10)

Remark 9. For n ≥ 0, we have some special cases

f_{n}^{(1)} = ∑_{k=0}^{n} f_{k} = f_{n+2} − 1.  (11)

f_{n}^{(2)} = ∑_{k=0}^{n} (k + 1) f_{n−k} = f_{n+4} − n − 4.  (12)

4 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 [6] defined the incomplete Fibonacci numbers F_{n} (k) by the following relation for n ≥ 0

F_{n+1} (k) = ∑_{j=0}^{k} \binom{n − j}{j} (0 ≤ k ≤ ⌊\frac{n+1}{2}⌋) .  (13)

Theorem 10. Let f_{n} (k) counts the number of ways to tile an n-board with at most k dominoes. Then

f_{n} (k) = ∑_{j=0}^{k} \binom{n − j}{j} (0 ≤ k ≤ ⌊\frac{n}{2}⌋) .  (14)

Proof. It follows from Lemma 1, by summing over j.

Note that, if we take k = ⌊\frac{n}{2}⌋, then the f_{n} (k) is reduced to the Fibonacci number f_{n}.

Theorem 11. For n ≥ 0, we have

f_{n} (k) = f_{n−1} (k) + f_{n−2} (k − 1) ,  (15)

with f_{n} (0) = f_{0} (k) = 1.

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} (k) 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} (k − 1) ways to tile the first n − 2 cells with at most k − 1 dominoes.

The following theorem gives a combinatorial interpretation for incomplete Fibonacci numbers.

Theorem 12. For n,k ≥ 0 with 0 ≤ k ≤ ⌊n/2⌋, we have F_{n+1} (k) = f_{n} (k). That is, F_{n+1} (k) counts the number of ways to tile an n-board with at most k dominoes.

From relations (13) and (15), we obtain the following non-homogenous second order recurrence relation as stated by Filipponi [6].

For n ≥ 0, we have

f_{n} (k) = f_{n−1} (k) + f_{n−2} (k) − \binom{n − k}{k}.  (16)

Using the approach of Benjamin et al., we recover Filipponi’s formula [6].

Theorem 13. For n ≥ 0, we have

f_{n+2h} (k + h) = ∑_{j=0}^{h} \binom{h}{j}f_{n+j} (k + j) (0 ≤ k ≤ \frac{n − h}{2}) .  (17)

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 \binom{h}{j} ways to select j positions for the dominoes among the first h tiles and f_{n+h−j} (k + h − j) ways to tile remaining n + h − j cells with at most k + h − j dominoes.

Using (10) and (14), we give a relation between Fibonacci numbers, incomplete Fibonacci numbers and hyperfibonacci numbers.

Corollary 14. For integers n,r ≥ 0, we have

f_{n+2r} = f_{n}^{(r)} + f_{n+2r} (r − 1) .  (18)

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.

5 Acknowledgments

The authors thank the anonymous referee for the throughout reading of the manuscript and valuable comments.

References

[1] H. Belbachir and A. Belkhir. Identities related to generalized Fibonacci numbers via tiling approach, submitted.

[2] H. Belbachir and A. Belkhir. Tiling approach to obtain identities for generalized Fibonacci and Lucas numbers, Ann. Math. Inform., 41 (2013), 13–17.

[3] A. T. Benjamin, J. J. Quinn, and F. E. Su. Phased tilings and generalized Fibonacci identities. Fibonacci Quart. 38 (2000), 282–288.

[4] A. T. Benjamin and J. J. Quinn. Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[5] A. Dil and I. Mező. A symmetric algorithm for hyperharmonic and Fibonacci numbers, Appl. Math. Comput. 206 (2008), 942–951.

[6] P. Filipponi. Incomplete Fibonacci and Lucas numbers, Rend. Circ. Mat. Palermo 45 (1996) 37–56.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 05B45; 05A19; 11B37. Keywords: Fibonacci number, hyperfibonacci number, tiling, bijective proofs, incomplete Fibonacci number.

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

Received October 2 2013; revised version received January 22 2014. Published in Journal of Integer Sequences, February 16 2014.

Return to Journal of Integer Sequences home page.