Hyperfibonacci Sequences and Polytopic Numbers

Ligia L. Cristea Karl-Franzens-Universität Graz Institute for Mathematics and Scientific Computing Heinrichstrasse 36 A-8010 Graz Austria

                 strublistea@gmail.com

Ivica Martinjak University of Zagreb Faculty of Science Bijenička 32 HR-10000 Zagreb Croatia

                   imartinjak@phy.hr

Igor Urbiha

Zagreb University of Applied Sciences (former Polytechnic of Zagreb)

Vrbik 8 HR-10000 Zagreb Croatia

                  igor.urbiha@tvz.hr

Abstract

We prove that the difference between the nth hyperfibonacci number of the rth generation and its two consecutive predecessors is the nth regular (r − 1)-topic number. Using this fact, we provide an equivalent recursive definition of the hyperfibonacci sequences, and derive an extension of the Binet formula. We also prove further identities involving both hyperfibonacci and hyperlucas sequences, in full generality.

1 Introduction

The hyperfibonacci sequence of the rth generation, denoted by (F_{n}^{(r)})_{n≥0}, is defined by the recurrence relation

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

where r ∈ ℕ and F_{n} is the nth term of the Fibonacci sequence. In the same manner one can define hyperlucas sequences. The hyperlucas sequence of the rth generation (L_{n}^{(r)})_{n≥0} is defined by means of the recurrence relation

L_{n}^{(r)} = ∑_{k=0}^{n} L_{k}^{(r−1)}, L_{n}^{(0)} = L_{n}, L_{0}^{(r)} = 2, L_{1}^{(r)} = 2r + 1,

where r ∈ ℕ and L_{n} is the nth Lucas number. Table (1) shows the starting terms of the first two generations of the hyperfibonacci and hyperlucas sequences.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ F_{n}^{(1)} & 0 & 1 & 2 & 4 & 7 & 12 & 20 & 33 & 54 & 88 & 143 \\ F_{n}^{(2)} & 0 & 1 & 3 & 7 & 14 & 26 & 46 & 79 & 133 & 221 & 364 \\ L_{n}^{(1)} & 2 & 3 & 6 & 10 & 17 & 28 & 46 & 75 & 122 & 198 & 321 \\ L_{n}^{(2)} & 2 & 5 & 11 & 21 & 38 & 66 & 112 & 187 & 309 & 507 & 828 \end{matrix}

Table 1: The starting terms of the first two generations of the hyperfibonacci and hyperlucas sequences.

Dil and Mező recently introduced these sequences in a study of a symmetric algorithm for hyperharmonic, Fibonacci and some other integer sequences [1]. The same authors provide further refinements on this subject [2]. On the other hand, hyperfibonacci sequences occur naturally as the number of board tilings with squares and dominoes. Let f_{m}^{(r)} denote the number of ways to tile an m-board with at least r dominoes. Then, for n, r ≥ 0 the relation

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

holds, with f_{0}^{(r)} := 1 [3]. Thus, the (n + 1)st hyperfibonacci number of the rth generation is equal to the number of (n + 2r)-board tilings with at least r dominoes. Equivalently, hyperfibonacci sequences represent the number of decompositions of an integer into summands 1 and 2, with the constraint on the number of 2s. This follows immediately from the fact that one can code squares and dominoes with 1 and 2, respectively. For example, when n = 3 and r = 1 we have f_{5}^{(1)} = F_{4}^{(1)} = 7, which is the number of decompositions of 5,

5 = 2 + 2 + 1 = 2 + 1 + 2 = 1 + 2 + 2 = 2 + 1 + 1 + 1
= 1 + 2 + 1 + 1 + 1 = 1 + 1 + 2 + 1 = 1 + 1 + 1 + 2.

Figure 1: Combinatorial interpretation of the hyperfibonacci number F_{4}^{(1)}.

Figure (1) shows the related 5-board tilings.

It is worth mentioning that several interesting number theoretical and combinatorial properties of these sequences have already been proven [5, 6, 9]. In the following we use these facts in order to establish further identities for the hyperfibonacci sequences.

2 Alternative definition of hyperfibonacci sequences

One can immediately see that the relation

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

follows from the definition of hyperfibonacci numbers (1). Now we present a recurrence relation for the nth hyperfibonacci number that involves its two predecessors of the same generation. Lemma 1 gives such a relation for r = 1.

Lemma 1. The elements of the sequence (F_{n}^{(1)})_{n≥0} of the first generation of hyperfibonacci numbers satisfy the following recurrence:

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

Proof. According to (2) there are F_{n+2}^{(1)} (n + 3)-board tilings with at least one domino. We consider the last tile in a tiling, which can be either a square or a domino. Tilings that end with a square are obviously equinumerous to tilings of an (n + 2)-board having at least one domino. The number of such tilings is F_{n+1}^{(1)}.

However, the number of tilings ending with a domino is not equal to F_{n}^{(1)} since, when fixing the last domino, here we have one (n + 1)-tiling with all squares. This tiling does not meet the condition on the minimal number of dominoes in a tiling, so we have to add 1 in order to establish the equality.

With similar arguments one can prove that in the case r = 2, the relation

F_{n+2}^{(2)} = F_{n+1}^{(2)} + F_{n}^{(2)} + n + 2

holds. We generalize these recurrences in Lemma 2. We recall that polytopic numbers are a generalization of square and triangular numbers. These numbers can be represented by a regular geometric arrangement of equally spaced points. The nth regular r-topic number P_{n}^{(r)} is equal to

P_{n}^{(r)} = \binom{n + r − 1}{r}.

Lemma 2. The difference between the nth r-generation hyperfibonacci number and the sum of its two consecutive predecessors is the nth regular (r − 1)-topic number,

F_{n+2}^{(r)} = F_{n+1}^{(r)} + F_{n}^{(r)} + \binom{n + r}{r − 1}, n ≥ 0.

Proof. Again we use arguments on the last tile in board tilings. First we observe that tilings of an (n + 2r + 1)-board with at least r dominoes, ending with a square are equinumerous to tilings of an (n + 2r)-board with the same restriction. The latter set has F_{n+1}^{(r)} elements.

We separate the tilings ending with a domino into two disjoint sets A and B. The set A consists of tilings that have exactly r dominoes and the set B contains the rest of tilings, i.e., the tilings having at least r + 1 dominoes. Having in mind that one domino is fixed, the tilings in the set B are equinumerous to the tilings of an (n + 2r − 1)-board with the same restriction, i.e.,

|B| = F_{n}^{(r)}.

Now we use the fact that the number of tilings of an m-board with M dominoes and m−2M squares is equal to the number of (m − M)-combinations over a set of M elements.

A tiling in the set A has n + r tiles,

(n + 2r + 1) − 2 − (r − 1) = n + r,

which means

|A| = \binom{n + r}{r − 1}.

The fact that

F_{n+2}^{(r)} = F_{n+1}^{(r)} + |A| + |B|

completes the proof.

Figure 2 illustrates this proof in the case n = 5 and r = 2.

Note that Lemma 2 provides an equivalent definition of the hyperfibonacci sequences. For n ≥ 0 and r ≥ 0 we define the sequence (F_{n}^{(r)})_{n≥0} by the recurrence relation

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

and the initial values F_{0}^{(r)} = 0, F_{1}^{(r)} = 1, where

P_{n+2}^{(r−1)} = \binom{n + r}{r − 1}.

Figure 2: Tilings in the sets A (left) and B (right) among the F_{4}^{(2)} 7-board tilings.

3 Identities for the rth generation of hyperfibonacci numbers

In this section we present some identities that hold for every generation of hyperfibonacci numbers.

Theorem 3. For the rth generation hyperfibonacci numbers we have

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

Proof. According to (2), the r.h.s. of the relation above is equal to f_{n+2r}^{(r)}. We use the fact that the number of (n + 2r)-tilings with k dominoes is equal to \binom{n+2r−k}{k}. Having in mind that f_{n+2r}^{(r)} represents the number of (n + 2r)-tilings with at least r dominoes we sum up the numbers of (n + 2r)-tilings with r, r + 1, …, ⌊(n + 2r)/2⌋ dominoes.

One of the basic properties of the hyperfibonacci sequence in the case r = 1 is expressed by the relation

F_{n}^{(1)} = F_{n+2} − 1,  (4)

which is an immediate consequence of the elementary Fibonacci relation

1 + ∑_{k=0}^{n} F_{k} = F_{n+2}.  (5)

Consequently, an extension of the Binet formula to the first generation of hyperfibonacci numbers is

F_{n}^{(1)} = \frac{ϕ^{n+2} − ϕ̄^{n+2}}{\sqrt{5}} − 1  (6)

where ϕ and ϕ̄ are the golden ratio and its conjugate, respectively:

ϕ = \frac{1 + \sqrt{5}}{2}, ϕ̄ = \frac{1 − \sqrt{5}}{2}.

Lemma 4 is an extension of the relation (5) to the hyperfibonacci sequence for r = 1.

Lemma 4. The sum of the first n + 1 hyperfibonacci numbers of the first generation is equal to the difference between the (n + 4)th Fibonacci number and (n + 3):

3 + n + ∑_{k=0}^{n} F_{n}^{(1)} = F_{n+4}, n ≥ 0.

Proof. Using (4) we obtain

F_{0}^{(1)} + F_{1}^{(1)} + ⋯ + F_{n}^{(1)} = F_{2} − 1 + F_{3} − 1 + ⋯ + F_{n+2} − 1
= ∑_{k=2}^{n+2} F_{k} − n − 1

= ∑_{k=0}^{n+2} F_{k} − n − 2
= F_{n+4} − n − 3.

Taking into account the definition of the hyperfibonacci numbers (1), Lemma 4 gives

F_{n}^{(2)} = F_{n+4} − n − 3,

which can also be written as

F_{n}^{(2)} = \frac{ϕ^{n+4} − ϕ̄^{n+4}}{\sqrt{5}} − n − 3.

Furthermore, we are going to show that the nth hyperfibonacci number of the rth generation F_{n}^{(r)} is equal to the (n + 2r)th Fibonacci number diminished by the sum of r binomial coefficients. This is expressed in Theorem 5 and provides an extension of the Binet formula to hyperfibonacci sequences. The proof uses the known Fibonacci relation

F_{n} = ∑_{k=0}^{⌊ \frac{n−1}{2} ⌋} \binom{n − k − 1}{k},  (7)

that also follows from Theorem 3 for r = 0.

Theorem 5. The nth hyperfibonacci number of the rth generation is equal to the difference between the (n + 2r)th Fibonacci number and the sum of r binomial coefficients,

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

Proof. We give a proof by induction on m = n + r. The induction base is as follows:

F_{n}^{(1)} = F_{n+2} − 1 = F_{n+2·1} − ∑_{k=0}^{0} \binom{n + 1 − k}{k} (for all n),

F_{n}^{(2)} = F_{n+4} − (n + 3) = F_{n+2·2} − ∑_{k=0}^{1} \binom{n + 3 − k}{k} (for all n)

Since by (7) we have

F_{2r} = ∑_{k=0}^{r−1} \binom{r + k}{r − 1 − k},

F_{2r+1} = 1 + ∑_{k=0}^{r−1} \binom{r + 1 + k}{r − 1 − k},

we also have (for all r)

F_{0}^{(r)} = 0 = F_{2r} − ∑_{k=0}^{r−1} \binom{r + k}{r − 1 − k},

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

The induction step is as follows:

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

= F_{n+2r+1} − \binom{n + 2r − 1}{0} − ∑_{k=0}^{r−2} [\binom{n + r + k}{r − 1 − k} + \binom{n + r + k}{r − 2 − k}]

= F_{n+1+2r} − \binom{n + 2r}{0} − ∑_{k=0}^{r−2} \binom{n + 1 + r + k}{r − 1 − k}

= F_{n+1+2r} − ∑_{k=0}^{r−1} \binom{n + 1 + r + k}{r − 1 − k}.

The following result immediately follows from the relation (7). Corollary 6.

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

Proof.

F_{n+1}^{(r)} = F_{n+1+2r} − ∑_{k=0}^{r−1} \binom{n + 1 + r + k}{r − 1 − k} =
= \begin{aligned}⌊ & \frac{n+1+2r−1}{2} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \binom{n + 1 + 2r − k − 1}{k} − ∑_{k=0}^{r−1} \binom{n + 2r − k}{k} =
= ∑_{k=0}^{⌊ \frac{n}{2} ⌋+r} \binom{n + 2r − k}{k} − ∑_{k=0}^{r−1} \binom{n + 2r − k}{k} =
= ∑_{k=r}^{⌊ \frac{n}{2} ⌋+r} \binom{n + 2r − k}{k} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n + r − k}{r + k}.

Proposition 7. For any r ≥ 0 the hyperfibonacci numbers of the rth generation satisfy

lim_{n→∞} \frac{F_{n+1}^{(r)}}{F_{n}^{(r)}} = ϕ.

Proof. For the case r = 0 we have the known property of Fibonacci numbers

lim_{n→∞} \frac{F_{n+1}}{F_{n}} = ϕ.  (9)

In the case r = 1, one can prove the above relation as follows. By the formula (4) we have

\frac{F_{n+1}^{(1)}}{F_{n}^{(1)}} = \frac{F_{n+3} − 1}{F_{n+2} − 1} = \frac{\frac{F_{n+3}}{F_{n+2}} − \frac{1}{F_{n+2}}}{1 − \frac{1}{F_{n+2}}} ,

and thus, since lim_{n→∞} \frac{1}{F_{n}} = 0, by using (9) we obtain lim_{n→∞} \frac{F_{n+1}^{(1)}}{F_{n}^{(1)}} = ϕ. For r ≥ 2 it is convenient to apply Theorem 5. One can immediately see that the sum ∑_{k=0}^{r−1} \binom{n+r+k}{r−1−k} occurring there is in fact the sum of r polynomials in the variable n, of which \binom{n+r}{r−1} = \frac{(n+r)(n+r+1)...(n+2)}{(r−1)!} has the highest degree, namely r − 1. Analogously, by writing the formula

in Theorem 5 for F_{n+1}^{(r)}, we obtain

\frac{F_{n+1}^{(r)}}{F_{n}^{(r)}} = \frac{\frac{F_{n+1+2r}}{F_{n+2r}} − \frac{Q_{r−1}(n)}{F_{n+2r}}}{1 − \frac{R_{r−1}(n)}{F_{n+2r}}} ,

where Q_{r−1}(n) and R_{r−1}(n) are polynomials (with rational coefficients) of degree r −1 in the variable n. By using the Binet formula for Fibonacci numbers, we have, for any polynomial Q_{r−1}(n) of degree r − 1 in n (with r ≥ 1 arbitrarily fixed),

\frac{Q_{r−1}(n)}{F_{n+2r}} = \frac{Q_{r−1}(n)}{\frac{1}{\sqrt{5}}(ϕ^{n+2r} − ϕ̄^{n+2r})} = \frac{\sqrt{5}}{\frac{ϕ^{n+2r}}{Q_{r−1}(n)} − \frac{ϕ̄^{n+2r}}{Q_{r−1}(n)}} .

Since |ϕ| > 1 and |ϕ̄| < 1, by basic mathematical analysis facts lim_{n→∞} \frac{ϕ^{n+2r}}{Q_{r−1}(n)} = ∞,

lim_{n→∞} \frac{ϕ̄^{n+2r}}{Q_{r−1}(n)} = 0, and we finally get lim_{n→∞} \frac{Q_{r−1}(n)}{F_{n+2r}} = 0. This holds for both polynomials

of degree r − 1 that occur in the formula above and thus lim_{n→∞} \frac{F_{n+1}^{(r)}}{F_{n}^{(r)}} = ϕ.

Let l_{m}^{(r)} denote the number of m-bracelet tilings with squares and with at least r dominoes. An m-bracelet tiling is formed from an m-board tiling by gluing together the cells 1 and n. A bracelet is said to be in phase if it ends with a square or a domino. Otherwise, if a domino covers the cells n and 1, the bracelet is out of phase. In Lemma 8 we prove a relationship between bracelet tilings with constraint on the minimal number of dominoes and hyperlucas numbers.

Lemma 8. Let n, r ∈ ℕ_{0}. Then the number of (n+2r)-bracelet tilings with squares and with at least r dominoes is equal to the nth hyperlucas number of the rth generation,

l_{n+2r}^{(r)} = L_{n}^{(r)}.

Proof. In the first step of the proof we show that the sequence of numbers l_{n}^{(r)} obeys the same recurrence relation (3) as the hyperfibonacci numbers,

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

We consider the last tile in an (n + 2r)-bracelet tiling. If the (n + 2r)-bracelet ends with a square, then the remaining (n + 2r − 1)-bracelet can be tiled in l_{n+2r−1}^{(r)} ways. Otherwise, if it ends with a domino there are l_{n+2r−2}^{(r−1)} possible tilings of the remaining (n+2r −2)-bracelet. Thus, bracelet tilings satisfy the same recurrence relation (3) as hyperfibonacci numbers.

Now we are testing the initial condition. For n = 0, there are two 2r-bracelet tilings, one in phase and another one out of phase, with at least r dominoes, thus l_{0}^{(r)} = 2 and consequently l_{0}^{(r)} = L_{0}^{(r)}. For r = 0 there is no constraint on the number of dominoes and clearly we have l_{n}^{(0)} = l_{n} = L_{n}. This reasoning completes the proof.

Theorem 9 gives an analogue of the most elementary relation involving both Fibonacci and Lucas numbers, that is,

L_{n} = F_{n−1} + F_{n+1}.  (10)

When proving it, we use the combinatorial interpretation of hyperfibonacci numbers as the number of board tilings and the interpretation of hyperlucas numbers as the number of bracelet tilings.

Theorem 9. The elements of the hyperfibonacci and the hyperlucas sequences satisfy the following formula:

L_{n}^{(r)} = F_{n−1}^{(r)} + F_{n+1}^{(r)} + \binom{n + r − 1}{r − 1}.

Proof. Obviously, there is a one-to-one correspondence between the number of (n+2r)-board tilings and in phase bracelets of the same length. Let us separate the out of phase (n + 2r)- bracelet tilings into two disjoint sets, such that the set A contains tilings with exactly r dominoes and the set B contains tilings with at least r − 1 dominoes. Having in mind that one domino is fixed, the tilings in B correspond to (n + 2r − 2)-board tilings with at least r dominoes, thus

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

Since the tilings in A consist of a number of (n + 2r − 2) − (r − 1) = n + r − 1 tiles, r of them being dominoes (one of them is a fixed domino), we have

|A| = \binom{n + r − 1}{r − 1}.

The fact that

L_{n}^{(r)} = F_{n+1}^{(r)} + |A| + |B|

completes the proof.

Possibly Theorem 9 can be used to prove further hyperfibonacci-hyperlucas identities.

4 Some identities for the first generation

In this section we demonstrate that there are Cassini-like formulas for the first generation of hyperfibonacci sequences. We were able to prove both Theorem 10 and Theorem 11 using the extension (6) of the Binet formula to the hyperfibonacci sequence in the case r = 1. We also provide elegant proofs employing the Cassini identity [8, 10] for the Fibonacci sequence,

F_{n−1}F_{n+1} − F_{n}^{2} = (−1)^{n}, n ≥ 0  (11)

and its generalization

F_{n}^{2} − F_{n−r}F_{n+r} = (−1)^{n−r}F_{r}^{2}, n ≥ 0, r ∈ ℕ_{0},  (12)

known as the Catalan identity.

In particular, we are going to show that for even n the difference of the square of the nth hyperfibonacci number F_{n}^{(1)} and the product of its two neighbors is equal to F_{n−3}^{(1)},

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

Otherwise, when n is odd the relation

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

holds. We prove these facts in Theorem 10 by means of the Cassini identity.

Theorem 10. For the first generation of hyperfibonacci numbers and n ≥ 3 the following identity holds:

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

Proof. Using (4) and (11) we have

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

There is also regularity in the difference between the square of a hyperfibonacci number of the first generation and the product of its two second neighbors. Namely, according to the closed formula for the first generation hyperfibonacci numbers (6) we get

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

(\frac{ϕ^{n+2} − ϕ̄^{n+2}}{\sqrt{5}} − 1)^{2} − (\frac{ϕ^{n} − ϕ̄^{n}}{\sqrt{5}} − 1)(\frac{ϕ^{n+4} − ϕ̄^{n+4}}{\sqrt{5}} − 1)

= \frac{(ϕ^{n+2} − ϕ̄^{n+2})^{2}}{5} − \frac{2(ϕ^{n+2} − ϕ̄^{n+2})}{\sqrt{5}} + 1 − \frac{1}{5}[ϕ^{2n+4} + ϕ̄^{2n+4} − (−1)^{n}(ϕ^{4} + ϕ̄^{4})

−\sqrt{5}(ϕ^{n+4} − ϕ̄^{n+4}) − \sqrt{5}(ϕ^{n} − ϕ̄^{n}) + 5]

= (−1)^{n} + \frac{ϕ^{n+4} − ϕ̄^{n+4}}{\sqrt{5}} + \frac{ϕ^{n} − ϕ̄^{n}}{\sqrt{5}} − 2\frac{ϕ^{n+2} − ϕ̄^{n+2}}{\sqrt{5}} ,

which is equal to

(−1)^{n} + F_{n+3} + F_{n+2} + F_{n} − 2(F_{n+1} + F_{n})

and finally to

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

This result is expressed in Theorem 11. We also provide a proof by means of the Catalan identity.

Theorem 11. For the first generation of hyperfibonacci numbers and n ≥ 2,

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

Proof. Using (4) and (12) we have

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

5 Acknowledgments

We thank the referees for valuable comments that helped us improve the quality of the paper.

Ligia L. Cristea is founded by the Austrian Science and Research Fund FWF, Project P27050-N26.

References

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

[2] M. Bahsi, I. Mező, and S. Solak, A symmetric algorithm for hyper-Fibonacci and hyper-Lucas numbers, Ann. Math. Inform. 43 (2014), 19–27.

[3] H. Belbachir and A. Belkhir, Combinatorial expressions involving Fibonacci, Hyperfibonacci, and incomplete Fibonacci numbers, J. Integer Seq. 17 (2014), Article 14.4.3.

[4] A. T. Benjamin and J. J. Quinn, Proofs that Really Count, The Mathematical Association of America, 2003.

[5] N. N. Cao and F. Z. Zhao, Some properties of Hyperfibonacci and Hyperlucas Numbers, J. Integer Seq. 13 (2010), Article 10.8.8.

[6] R. Liu and F. Zhao, On the sums of reciprocal Hyperfibonacci numbers and Hyperlucas numbers, J. Integer Seq. 15 (2012), Article 12.4.5.

[7] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section, John Wiley & Sons, 1989.

[8] N. G. Voll, The Cassini identity and its relatives, Fibonacci Quart. 48 (2010), 197–201.

[9] L. Zheng, R. Liu, and F. Zhao, On the log-concavity of the hyperfibonacci numbers and the hyperlucas numbers, J. Integer Seq. 17 (2014), Article 14.1.4.

[10] M. Werman and D. Zeilberger, A bijective proof of Cassini’s Fibonacci identity, Discrete Math. 58 (1986), 109.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 11P84. Keywords: Fibonacci sequence, hyperfibonacci sequence, hyperlucas sequence, Binet formula, polytopic number.

(Concerned with sequences \underline{A000045}, \underline{A000071}, \underline{A001924}, \underline{A014162}, and \underline{A014166}.)

Received July 25 2015; revised versions received May 11 2016; September 1 2016. Published in Journal of Integer Sequences, September 7 2016.

Return to Journal of Integer Sequences home page.