On Multiple Sums of Products of Lucas Numbers

Jaroslav Seibert and Pavel Trojovský University Hradec Králové Department of Mathematics Rokitanského 62 500 03 Hradec Králové Czech Republic

                    pavel.trojovsky@uhk.cz

Abstract

This paper studies some sums of products of the Lucas numbers. They are a generalization of the sums of the Lucas numbers, which were studied another authors. These sums are related to the denominator of the generating function of the k-th powers of the Fibonacci numbers. We considered a special case for an even positive integer k in the previous paper and now we generalize this result to an arbitrary positive integer k. These sums are expressed as the sum of the binomial and Fibonomial coefficients. The proofs of the main theorems are based on special inverse formulas.

1 Introduction

Generating functions are very helpful in finding of relations for sequences of integers. Some authors found miscellaneous identities for the Fibonacci numbers F_{n}, defined by recurrence relation F_{n+2} = F_{n} + F_{n+1}, with F_{0} = 0, F_{1} = 1, and the Lucas numbers L_{n}, defined by the same recurrence but with the initial conditions L_{0} = 2, L_{1} = 1, by manipulation with their generating functions. Our approach is rather different in this paper.

In 1718 DeMoivre found the generating function of the Fibonacci numbers F_{n} and used it for deriving the closed form F_{n} = \frac{1}{\sqrt{5}}(α^{n} − β^{n}), with α = \frac{1}{2}(1 + \sqrt{5}) and β = \frac{1}{2}(1 − \sqrt{5}) (similarly the formula L_{n} = α^{n} + β^{n} holds for the Lucas numbers). In 1957 S. W. Golomb [2] found the generating function for the square of F_{n} and this result started the effort to find a recurrence or a closed form for the generating function f_{k}(x) = ∑_{n=0}^{∞} F_{n}^{k}x^{n} of the k-th powers of the Fibonacci numbers. Riordan [7] found a general recurrence for f_{k}(x). Carlitz [1], Horadam [4] and Mansour [6] presented some generalizations of Riordan’s results and found similar recurrences for the generating functions of powers of any second–order recurrence sequences.

Horadam gave some closed forms for the numerator and the denominator of this generating function. From his results follows, for example

f_{k}(x) = \frac{∑_{i=0}^{k} ∑_{j=0}^{i}(−1)^{\frac{j(j+1)}{2}} \left[{k+1 \atop j}\right] F_{i−j}^{k} x^{i}}{∑_{i=0}^{k+1}(−1)^{\frac{i(i+1)}{2}} \left[{k+1 \atop i}\right] x^{i}} ,  (1)

where \left[{n \atop k}\right] are the Fibonomial coefficients defined for any nonnegative integers n and k by

\left[{n \atop k}\right] = ∏_{i=0}^{k−1} \frac{F_{n−i}}{F_{i+1}} = \frac{F_{n}F_{n−1} ⋯ F_{n−k+1}}{F_{1}F_{2} ⋯ F_{k}} ,

with \left[{n \atop 0}\right] = 1 and \left[{n \atop k}\right] = 0 for n < k.

Using Carlitz’ method, Shannon [11] obtained some special results for the numerator and the denominator in the expression of the generating function f_{k}(x). For example, he used the q–analog of the terminating binomial theorem (firstly published by Rothe [9], but from Gauss’s posthumous papers it is known that he had found it around 1808, see [5]) and obtained the relation

∏_{i=0}^{k}(1 − q^{i} x) = ∑_{i=0}^{k+1}(−1)^{i}q^{\frac{i}{2} (i−1)} \left\{{k + 1 \atop i}\right\} x^{i} .

Q–binomial coefficients are defined \left\{{k+1 \atop i}\right\} = \frac{(q^{k+1}−1)(q^{k}−1)···(q^{k−i+2}−1)}{(q−1)(q^{2}−1)···(q^{i}−1)} for i ≥ 1 and any complex numbers q, x and any positive integer k, where \left\{{k+1 \atop 0}\right\} = 1. Replacing q by β/α and x by α^{k} x he got

∏_{i=0}^{k}(1 − α^{k−i}β^{i} x) = ∑_{i=0}^{k+1}(−1)^{\frac{i}{2} (i+1)}\left[{k + 1 \atop i}\right] x^{i} .  (2)

We paid attention [10] to a generalization of a type of the well–known formulas for the Fibonacci and Lucas numbers, see [12, pp. 179–183], for example

∑_{i=0}^{n}(−1)^{i}L_{n−2i} = 2F_{n+1} .

In this paper we concentrate on the sums

∑_{i_{n}=0}^{⌊ \frac{k−1}{2} ⌋} ∑_{i_{n−1}=i_{n}+1}^{⌊ \frac{k−1}{2} ⌋} ⋯ ∑_{i_{n−2}=i_{n−1}+1}^{⌊ \frac{k−1}{2} ⌋}(−1)^{i_{1}+i_{2}+···+i_{n}} ∏_{j=1}^{n} L_{k−2 i_{j}} ,  (3)

where k is an arbitrary positive integer. The special case of (3) for an odd k was solved up in [10]. Here we use analogous method to find formulas for an even integer k.

Throughout the paper we adopt the conventions that the sum and the product over an empty set is 0 and 1, respectively, ⌊x⌋ represents the greatest integer less than or equal to x, the relation f(x) ∼ g(x) means that f(x) is asymptotic to g(x) and Iverson’s notation (see, e. g., [3]) that

[P (k)] = \{ \begin{matrix}1, if statement P (k) is true ; \\ 0, if statement P (k) is false . \end{matrix}

2 The main results

Definition 1. Let k be any positive integer. We define the sequence {S_{n}(k)}_{n=0}^{∞} in the following way

S_{0}(k) = 1 , S_{1}(k) = ∑_{i_{1}=0}^{⌊ \frac{k−1}{2} ⌋}(−1)^{i_{1}}L_{k−2 i_{1}}

and

S_{n}(k) = ∑_{i_{n}=0}^{⌊ \frac{k−1}{2} ⌋} ∑_{i_{n−1}=i_{n}+1}^{⌊ \frac{k−1}{2} ⌋} ⋯ ∑_{i_{1}=i_{2}+1}^{⌊ \frac{k−1}{2} ⌋}(−1)^{i_{1}+i_{2}+···+i_{n}} ∏_{j=1}^{n} L_{k−2 i_{j}} ,  (4)

for any integer n > 1.

Let us denote

Θ(i, k, n) = \binom{⌊\frac{k+1}{2}⌋ − n + i}{i} + \binom{⌊\frac{k+1}{2}⌋ − n + i − 1}{i − 1}

for any positive integers i, k and any nonnegative integer n.

Theorem 2. Let n be any nonnegative integer and let k be any positive integer. Then

S_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{⌊ \frac{n}{2} ⌋−i} Θ(i, k, n) \left[{k + 1 \atop n − 2i}\right]  (5)

if k is odd and

S_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=0}^{n−2i}(−1)^{i+n( \frac{k}{2} +1)+ \frac{j}{2} (j+k+1)} Θ(i, k, n) \left[{k + 1 \atop j}\right]  (6)

if k is even.

Corollary 3. Let n be any nonnegative integer and let k be any positive integer. Then the asymptotic formula

S_{n}(k) ∼ ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{⌊ \frac{n}{2} ⌋+i k} Θ(i, k, n) \left[{k + 1 \atop n − 2i}\right]  (7)

holds as k → ∞.

Theorem 4. Let m be any integer and let k be any even positive integer. Then

∑_{j=0}^{m}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] = (−1)^{\frac{m}{2} (m+k+1)} \frac{1}{F_{\frac{k}{2} +1}} ∑_{i=0}^{⌊ \frac{m}{2} ⌋}(−1)^{i}\left[{k + 2 \atop m − 2i}\right] F_{\frac{k+2}{2} −m+2i} .

Corollary 5. Let n be any nonnegative integer and let k be any even positive integer. Then

S_{n}(k) = \frac{(−1)^{⌊ \frac{n}{2} ⌋}}{F_{\frac{k}{2} +1}} ∑_{i=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=i}^{⌊ \frac{n}{2} ⌋} (−1)^{i+j} Θ(i, k, n) \left[{k + 2 \atop n − j}\right] F_{\frac{k+2}{2} −n+2j} .  (8)

Theorem 6. Let m be any integer. Then

∑_{j=0}^{m}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] = \frac{(−1)^{\frac{m}{2} (m+k+1)}}{F_{\frac{k}{2} +1}F_{k+3}F_{k+4}} ∑_{i=0}^{⌊ \frac{m}{4} ⌋} \left[{k + 4 \atop m − 4i}\right]×

× (F_{\frac{k}{2} +1−(m−4i)} L_{\frac{k}{2} +2−(m−4i)} F_{k+3} − F_{m−4i} F_{m−4i−1}) .

Corollary 7. Let n be any nonnegative integer. Then

∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{i} (\binom{\frac{k+1}{2} − n + i}{i} + \binom{\frac{k−1}{2} − n + i}{i − 1}) \left[{k + 1 \atop n − 2i}\right] = 0  (9)

if k is an odd positive integer, k < 2n − 1, and

∑_{i=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=0}^{n−2i}(−1)^{i+ \frac{j}{2} (j+k+1)} (\binom{\frac{k}{2} − n + i}{i} + \binom{\frac{k−2}{2} − n + i}{i − 1}) \left[{k + 1 \atop j}\right] = 0  (10)

if k is an even integer, k < 2n. Corollary 8. Let k be any even positive integer. Then

∑_{i=0}^{\frac{k−2}{2}}(−1)^{i} L_{k−2i} = F_{k+1} − (−1)^{\frac{k}{2}} ,
∑_{i_{2}=0}^{\frac{k−2}{2}} ∑_{i_{1}=i_{2}+1}^{\frac{k−2}{2}}(−1)^{i_{1}+i_{2}+1} L_{k−2i_{1}} L_{k−2i_{2}} = \frac{k − 2}{2} + (−1)^{\frac{k}{2}} F_{k+1} + F_{k} F_{k+1}

and

∑_{i_{3}=0}^{\frac{k−2}{2}} ∑_{i_{2}=i_{3}+1}^{\frac{k−2}{2}} ∑_{i_{1}=i_{2}+1}^{\frac{k−2}{2}}(−1)^{i_{1}+i_{2}+i_{3}} L_{k−2i_{1}} L_{k−2i_{2}} L_{k−2i_{3}}

= \frac{k − 4}{2} ((−1)^{\frac{k}{2}} − F_{k+1}) + F_{k} F_{k+1} ((−1)^{\frac{k}{2}} − \frac{1}{2}F_{k−1}) .

3 The preliminary results

Lemma 9. Let k be any positive integer. Then S_{n}(k) = 0 for each positive integer n > ⌊\frac{k+1}{2}⌋. Proof. After rewriting relation (4) from Definition 1 into the form

S_{n}(k) = ∑_{\begin{matrix}i_{1},i_{2},...,i_{n} \\ 0≤i_{n}<i_{n−1}<···<i_{1}≤⌊\frac{k−1}{2}⌋ \end{matrix}}(−1)^{i_{1}+i_{2}+···+i_{n}} ∏_{j=1}^{n} L_{k−2 i_{j}}

the assertion easily follows from the condition

0 ≤ i_{n} < i_{n−1} < ⋯ < i_{1} ≤ ⌊\frac{k − 1}{2}⌋

which does not hold for any values i_{1}, i_{2}, …, i_{n} if ⌊\frac{k−1}{2}⌋ < n − 1. Lemma 10. Let k be any even positive integer and let n be any positive integer. Then

(i)  ∑_{i=0}^{n} \binom{\frac{k}{2} − 2i}{n − i}S_{2i}(k) = 0 for n ≥ \frac{k}{2} + 1
(ii)  ∑_{i=0}^{n} \binom{\frac{k}{2} − (2i + 1)}{n − i}S_{2i+1}(k) = 0 for n ≥ \frac{k}{2} .

Proof. We show the proof of (i). Case (ii) can be proved analogously. Each positive integer n ≥ \frac{k}{2} + 1 can be written in the form n = \frac{k}{2} + l, where l is any positive integer. We will show that just one of factors in the product \binom{\frac{k}{2} −2i}{n−i}S_{2i}(k) is equal to zero. Concretely, the first one equals zero for i ≤ ⌊\frac{k}{4}⌋ and the second one equals zero for i > ⌊\frac{k}{4}⌋. For the sum in (i) the following holds:

∑_{i=0}^{\frac{k}{2} +l} \binom{\frac{k}{2} − 2i}{\frac{k}{2} + l − i}S_{2i}(k) = Q_{1}(k, l) + Q_{2}(k, l) ,

where

Q_{1}(k, l) = ∑_{i=0}^{⌊ \frac{k}{4} ⌋} \binom{\frac{k}{2} − 2i}{\frac{k}{2} + l − i}S_{2i}(k)

and

Q_{2}(k, l) = ∑_{i=⌊ \frac{k}{4} ⌋+1}^{\frac{k}{2} +l} \binom{\frac{k}{2} − 2i}{\frac{k}{2} + l − i}S_{2i}(k) = ∑_{p=1}^{\frac{k}{2} −⌊ \frac{k}{4} ⌋+l} \binom{\frac{k}{2} − 2⌊\frac{k}{4}⌋ − 2p}{\frac{k}{2} − ⌊\frac{k}{4}⌋ + l − p}S_{2⌊ \frac{k}{4} ⌋+2p}(k) .

It is obvious that \binom{\frac{k}{2} −2i}{\frac{k}{2} +l−i} = 0 if i ≤ ⌊\frac{k}{4}⌋ and therefore Q_{1}(k, l) = 0 for any k and l. Since the equality S_{2⌊ \frac{k}{4} ⌋+2p}(k) = 0 is implied by Lemma 9 for any nonnegative integer p, it follows that Q_{2}(k, l) = 0.

Lemma 11. Let n be any positive integer and let q be any integer. Then the following inverse formula holds:

a_{n} = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n}\binom{q − n + 2i}{i}b_{n−2i}

if and only if

b_{n} = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n+i} (\binom{q − n + i}{i} + \binom{q − n + i − 1}{i − 1}) a_{n−2i} .  (11)

Proof. Riordan [8, p. 243] gave the following inverse formula:

a_{n} = ∑_{i=0}^{n} \binom{q − 2i}{n − i}b_{i}

if and only if

b_{n} = ∑_{i=0}^{n}(−1)^{n+i} (\binom{q − n − i}{n − i} + \binom{q − n − i − 1}{n − i − 1}) a_{i} .

To get Lemma 11 from this formula first we substitute \{a_{n}\} by \{a_{2n}\}, \{b_{i}\} by \{b_{2i}\}, n by \frac{n}{2} and i by \frac{n}{2} − i and then \{a_{n}\} by \{a_{2n+1}\}, \{b_{i}\} by \{−b_{2i+1}\}, n by \frac{n−1}{2}, i by \frac{n−1}{2} − i and q by q − 1. This leads to the proved formula.

Lemma 12. Let n, k, l be any positive integers, l < n < k. Let c_{i}, i = 1, 2, …, n, be any real numbers, c_{n} ≠ 0. Then

(i) lim_{k→∞} \left[{k \atop l}\right]\left[{k \atop n}\right]^{−1} = 0 , (ii) ∑_{i=l}^{n} c_{i} \left[{k \atop i}\right] ∼ c_{n} \left[{k \atop n}\right] as k → ∞ .

Proof. Relation (i) follows from the definition of the Fibonomial coefficients and the obvious fact that lim_{k→∞} F_{k} = ∞. Thus,

lim_{k→∞} \left[{k \atop l}\right]\left[{k \atop n}\right]^{−1} = lim_{k→∞} \frac{F_{k}F_{k−1} ⋯ F_{k−l+1}}{F_{1}F_{2} ⋯ F_{l}} · \frac{F_{1}F_{2} ⋯ F_{n}}{F_{k}F_{k−1} ⋯ F_{k−n+1}} =

= \frac{F_{1}F_{2} ⋯ F_{n}}{F_{1}F_{2} ⋯ F_{l}} lim_{k→∞} \frac{F_{k}F_{k−1} ⋯ F_{k−l+1}}{F_{k}F_{k−1} ⋯ F_{k−n+1}} =

= ∏_{i=l+1}^{n} F_{i} · lim_{k→∞} \frac{1}{F_{k−l} ⋯ F_{k−n+1}} = 0 .

Asymptotic formula (ii) is implied by (i).

Lemma 13. Let {a_{n}}, {b_{n}} be any sequences of real numbers, with b_{−1} = 0, and let h be any integer. Then for an arbitrary positive integer n

a_{n} = b_{n} − (−1)^{h} b_{n−1}  (12)

if and only if

b_{n} = ∑_{i=0}^{n}(−1)^{h(n+i)} a_{i} .  (13)

Proof. Let us show that identity (12) implies identity (13). We have

∑_{i=0}^{n}(−1)^{h(n+i)} a_{i} = ∑_{i=0}^{n}(−1)^{h(n+i)} (b_{i} − (−1)^{h} b_{i−1})

= ∑_{i=0}^{n}(−1)^{h(n+i)} b_{i} − ∑_{i=1}^{n}(−1)^{h(n−1+i)} b_{i−1} − (−1)^{h(n−1)} b_{−1}

= ∑_{i=0}^{n}(−1)^{h(n+i)} b_{i} − ∑_{j=0}^{n−1}(−1)^{h(n+j)} b_{j} = b_{n} .

Thus, this part of the assertion is true and similarly we can prove the reversed implication. Lemma 14. Let k be any even positive integer and let a be any positive integer. Then

\left[{k + 1 \atop a}\right] + (−1)^{\frac{k}{2} +a} \left[{k + 1 \atop a − 1}\right] = \frac{F_{\frac{k}{2} +1−a}}{F_{\frac{k}{2} +1}} \left[{k + 2 \atop a}\right].

Proof. Using the definition of the Fibonomial coefficients we get the relation

F_{\frac{k}{2} −a+1} F_{k+2} = F_{\frac{k}{2} +1} (F_{k−a+2} + (−1)^{\frac{k}{2} +a} F_{a}) ,

which can be written in the form

F_{\frac{k}{2} −a+1} L_{\frac{k}{2} +1} = F_{k−a+2} + (−1)^{\frac{k}{2} +a} F_{a}

as F_{2n} = F_{n} L_{n} ([12, p. 176]). We get the previous relation by setting l = \frac{k}{2} − a + 1 and n = \frac{k}{2} + 1 into the identity ( [12, p. 177])

F_{l+n} = F_{l} L_{n} + (−1)^{n+1}F_{l−n} ,  (14)

which holds for any integers l, n. The assertion follows at once.

The following form of Θ(i, k, n) is more effective for the computation of the sums S_{n}(k): Lemma 15. Let i, n be any integers and let k be any even positive integer. Then

Θ(i, k, n) = \{ \begin{matrix}0, & i < 0 ; \\ 1, & i = 0 ; \\ \frac{k−2(n−2i)}{2i} ∏_{j=1}^{i−1} \frac{k−2(n+j−i)}{2(i−j)} , & i > 0 . \end{matrix}

Proof. The cases for i ≤ 0 are clear. For i > 0 we can write:

Θ(i, k, n) = \binom{\frac{k}{2} − n + i}{i} + \binom{\frac{k}{2} − n + i − 1}{i − 1}

= \frac{k − 2(n − 2i)}{2i} \binom{\frac{k}{2} − n + i − 1}{i − 1} = \frac{k − 2(n − 2i)}{2i} ∏_{j=1}^{i−1} \frac{\frac{k}{2} − n + i − j}{i − j}

and the proof is over.

4 Additional properties of the inner sum

Now we will investigate properties of the inner sum involved in (6). Let us denote

σ_{k}(m) = σ(m) := ∑_{j=0}^{k−m}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] ,  (15)

where k is any even positive integer and m is any integer.

Lemma 16. Let k be any even positive integer and let m be any integer. Then

(i)

σ(m) = 0 , for m ≤ −1 or m ≥ k + 1 ,

(ii)

σ(k − m) = σ(m) ,

(iii)

σ(0) = 1 ,  σ(1) = 1 + (−1)^{\frac{k−2}{2}} F_{k+1} ,
σ(2) = 1 − L_{\frac{k+2}{2}} F_{k+1}F_{\frac{k−2}{2}} , σ(3) = 1 − \frac{1}{2}(−1)^{\frac{k}{2}} F_{k+1} (2 − F_{k} F_{\frac{k−4}{2}} L_{\frac{k+2}{2}} ) .

Proof. (i) First we prove the case for m = −1:

σ(−1) = ∑_{j=0}^{k+1}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right]

= ∑_{j=0}^{\frac{k}{2}}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] + ∑_{j= \frac{k}{2} +1}^{k+1}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right]

= ∑_{j=0}^{\frac{k}{2}}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] + ∑_{i=0}^{\frac{k}{2}}(−1)^{\frac{k+1−i}{2} (2k+2−i)}\left[{k + 1 \atop k + 1 − i}\right]

= ∑_{j=0}^{\frac{k}{2}}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] + ∑_{i=0}^{\frac{k}{2}}(−1)^{−1}(−1)^{\frac{i}{2} (i+k+1)}\left[{k + 1 \atop i}\right] = 0 .

For m ≥ k + 1 the assertion is obvious, according to defining formula (15). The case for m < −1 follows from σ(−1) = 0 and \left[{k+1 \atop i}\right] = 0, for i > k + 1, with respect to the definition of the Fibonomial coefficients.

(ii) We can write successively

σ(k − m) = ∑_{j=0}^{m}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] = ∑_{i=k−m+1}^{k+1}(−1)^{\frac{k+1−i}{2} (2k+2−i)}\left[{k + 1 \atop k + 1 − i}\right]

= ∑_{i=k−m+1}^{k+1}(−1)^{1}(−1)^{\frac{i}{2} (i+k+1)}\left[{k + 1 \atop i}\right]

= ∑_{i=0}^{k+1}(−1)^{1}(−1)^{\frac{i}{2} (i+k+1)}\left[{k + 1 \atop i}\right] − ∑_{i=0}^{k−m}(−1)^{1}(−1)^{\frac{i}{2} (i+k+1)}\left[{k + 1 \atop i}\right]

= −σ(−1) + ∑_{i=0}^{k−m}(−1)^{\frac{i}{2} (i+k+1)}\left[{k + 1 \atop i}\right] = σ(m) .

(iii) Identities for σ(0) and σ(1) are directly implied by σ(−1) = 0. Using case (ii) and identity (14) we have

σ(2) = ∑_{j=0}^{k−2}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] = 1 + (−1)^{\frac{k−2}{2}} F_{k+1} − F_{k+1}F_{k}

= 1 − F_{k+1} (F_{k} + (−1)^{\frac{k}{2}} ) = 1 − F_{k+1} L_{\frac{k}{2} +1} F_{\frac{k}{2} −1} ,

σ(3) = σ(2) − \frac{1}{2}(−1)^{\frac{k−2}{2}} F_{k+1}F_{k}F_{k−1}

= 1 − F_{k+1}F_{k} − (−1)^{\frac{k}{2}} F_{k+1} + \frac{1}{2}(−1)^{\frac{k}{2}} F_{k+1}F_{k}F_{k−1}

= 1 − \frac{1}{2}(−1)^{\frac{k}{2}} F_{k+1} (2 − F_{k} (F_{k−1} − 2(−1)^{\frac{k}{2}} ))

= 1 − \frac{1}{2}(−1)^{\frac{k}{2}} F_{k+1} (2 − F_{k} F_{\frac{k}{2} −2} L_{\frac{k}{2} +1}) .

This finishes the proof.

The sum σ(m) can be simplified by the following lemma.

Lemma 17. Let k be any even positive integer and let m be any integer. Then

σ(m) − σ(m − 2) = (−1)^{\frac{m}{2} (m+k+1)}\left[{k + 2 \atop m}\right]\frac{F_{\frac{k}{2} +1−m}}{F_{\frac{k}{2} +1}} .

Proof. For m < 2 the assertion follows from the definition of the Fibonomial coefficients and Lemma 16. For m ≥ 2 we have, with respect to Lemma 16,

σ(m) − σ(m − 2) = σ(k − m) − σ(k − m + 2)

= ∑_{j=0}^{m}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right] − ∑_{j=0}^{m−2}(−1)^{\frac{j}{2} (j+k+1)}\left[{k + 1 \atop j}\right]

= (−1)^{\frac{m}{2} (m+k+1)}\left[{k + 1 \atop m}\right] + (−1)^{\frac{m−1}{2} ((m−1)+k+1)}\left[{k + 1 \atop m − 1}\right]

= (−1)^{\frac{m}{2} (m+k+1)} (\left[{k + 1 \atop m}\right] + (−1)^{\frac{k}{2} +m}\left[{k + 1 \atop m − 1}\right]) ,

which, by Lemma 14, implies the assertion. Lemma 18. Let k be any even positive integer and let m be any integer. Then

σ(m) − σ(m − 4) = (−1)^{\frac{m}{2} (m+k+1)}\left[{k + 4 \atop m}\right]\frac{F_{\frac{k}{2} +2−m}}{F_{\frac{k}{2} +1}F_{k+3}F_{k+4}} ω(m, k) ,  (16)

where

ω(m, k) = F_{\frac{k}{2} +1−m} L_{\frac{k}{2} +2−m} F_{k+3} − F_{m} F_{m−1} .

Proof. With respect to Lemma 17 we have for any integer m

σ(m) − σ(m − 4) = (σ(m) − σ(m − 2)) + (σ(m − 2) − σ(m − 4)) =

= (−1)^{\frac{m}{2} (m+k+1)} \frac{1}{F_{\frac{k}{2} +1}} (F_{\frac{k}{2} +1−m}\left[{k + 2 \atop m}\right] − F_{\frac{k}{2} +3−m}\left[{k + 2 \atop m − 2}\right]) .

The bracket term can be rewritten as

F_{\frac{k}{2} +1−m}\left[{k + 2 \atop m}\right] − F_{\frac{k}{2} +3−m}\left[{k + 2 \atop m − 2}\right] =

= \left[{k + 4 \atop m}\right]\frac{1}{F_{k+3}F_{k+4}} (F_{\frac{k}{2} +1−m} F_{k+3−m} F_{k+4−m} − F_{\frac{k}{2} +3−m} F_{m} F_{m−1} .)

The identity

F_{k+3−m} F_{k+4−m} = F_{k+4−2m} F_{k+3} + F_{m} F_{m−1}

follows from the identity ([12, p. 177])

F_{n+h} F_{n+l} − F_{n} F_{n+h+l} = (−1)^{n}F_{h} F_{l} ,

with any integers h, n, l. Hence, we obtain

F_{\frac{k}{2} +1−m}\left[{k + 2 \atop m}\right] − F_{\frac{k}{2} +3−m}\left[{k + 2 \atop m − 2}\right]

= \left[{k+4 \atop m}\right]\frac{1}{F_{k+3}F_{k+4}} (F_{\frac{k+2}{2} −m} (F_{k+4−2m} F_{k+3}−F_{m} F_{m−1}) − F_{\frac{k+6}{2} −m} F_{m} F_{m−1})

= \left[{k+4 \atop m}\right]\frac{1}{F_{k+3}F_{k+4}} (F_{\frac{k}{2} +1−m} F_{k+4−2m} F_{k+3} − (F_{\frac{k}{2} +3−m} − F_{\frac{k}{2} +1−m}) F_{m} F_{m−1})

= \left[{k+4 \atop m}\right]\frac{F_{\frac{k}{2} +2−m}}{F_{k+3}F_{k+4}} (F_{\frac{k}{2} +1−m} L_{\frac{k}{2} +2−m} F_{k+3} − F_{m} F_{m−1})

and the assertion follows.

Lemma 19. Let m ≥ 5 be any integer and let k be any positive even integer in one of the following forms

(i) k = m − 4 + [2 ∤ m] , (ii) k = 2(m − 3) , (iii) k = 2(m − 1) .

Then ω(m, k) can be factored into a product of the Fibonacci or Lucas numbers.

Proof. Condition (i), with respect to the identities ([12, pp. 176–177]) F_{−n} = (−1)^{n+1}F_{n}, L_{−n} = (−1)^{n}L_{n} and F_{2n} = F_{n} L_{n}, leads to the relation

ω(m, m − 3) = F_{− \frac{m+1}{2}} F_{m} L_{− \frac{m−1}{2}} − F_{m} F_{m−1} = F_{m} L_{\frac{m−1}{2}} (F_{\frac{m+1}{2}} − F_{\frac{m−1}{2}} )
= F_{m} F_{\frac{m−3}{2}} L_{\frac{m−1}{2}}

if m is odd and to the relation

ω(m, m − 4) = F_{\frac{m+2}{2}} F_{m−1} L\frac{m}{2} − F_{m} F_{m−1} = F_{m−1} L\frac{m}{2} (F_{\frac{m+2}{2}} − F\frac{m}{2} )
= F_{m−1} F_{\frac{m−2}{2}} L\frac{m}{2}

if m is even.

Using the identity F_{n+1}^{2} + F_{n}^{2} = F_{2n+1} ([12, p. 177]), we have from condition (ii)

ω(m, 2(m − 3)) = F_{2m−3} − F_{m} F_{m−1} = F_{m−2}^{2} + F_{m−1}^{2} − F_{m} F_{m−1}
= F_{m−2}^{2} − F_{m−1} (F_{m} − F_{m−1}) = F_{m−2}^{2} − F_{m−1} F_{m−2}
= F_{m−2}(F_{m−2} − F_{m−1}) = −F_{m−2} F_{m−3} .

Condition (iii) gives ω(m, 2(m − 1)) = −F_{m} F_{m−1}.

Remark 20. The right–hand side of (16) can not be factored in a product of the Fibonacci or Lucas numbers for arbitrary values of k and m. The trivial factorization can be done for m = 0 and m = 1. Table 1 lists the values of m and k, 2 ≤ m ≤ 10, 2 ≤ k ≤ 170, for which ω(m, k) can be factored into a product of the Fibonacci or Lucas numbers. These values were found by computer. The computer search for 10 ≤ m ≤ 100 showed that ω(m, k) can be factored into a product of the Fibonacci or Lucas numbers only at values of m, k satisfying conditions from Lemma 20.

Table 1. The values for which ω(m, k) is factorizable.

m  k
2 2 6
3 2 4 6
4 2 4 6 8
5 2 4 8 10
6 2 6 10
7 4 6 8 12
8 4 6 8 10 14
9 2 6 10 12 16
10 2 6 14 18

5 The proofs of the main results

Proof of Theorem 2. First we prove identity (5). We showed [10] that for any positive odd integer k and any positive integer n

S_{2n−1}(k) = ∑_{i=1}^{n}(−1)^{i+1} (\binom{\frac{k+3}{2} − n − i}{n − i} + \binom{\frac{k+1}{2} − n − i}{n − i − 1}) \left[{k + 1 \atop 2i − 1}\right]  (17)

and

S_{2(n−1)}(k) = ∑_{i=1}^{n}(−1)^{i+1} (\binom{\frac{k+5}{2} − n − i}{n − i} + \binom{\frac{k+3}{2} − n − i}{n − i − 1}) \left[{k + 1 \atop 2(i − 1)}\right] .  (18)

Relation (5) can be obtained from (17) and (18). Replacing n by n + 1 and i by n + 1 − i we have for any nonnegative integer n

S_{2n+1}(k) = ∑_{i=0}^{n}(−1)^{n−i} (\binom{\frac{k+1}{2}−(2n+1)+i}{i} + \binom{\frac{k−1}{2}−(2n+1)+i}{i − 1}) \left[{k + 1 \atop 2n+1−2i}\right]

and

S_{2n}(k) = ∑_{i=0}^{n}(−1)^{n−i} (\binom{\frac{k+1}{2} − 2n + i}{i} + \binom{\frac{k−1}{2} − 2n + i}{i − 1}) \left[{k + 1 \atop 2n − 2i}\right] ,

which can be joined into the proved identity.

We begin the proof of relation (6) by defining the polynomial

P_{k}(x) = ∑_{i=0}^{k} p_{i}(k) x^{i} = ∏_{j=0}^{\frac{k}{2} −1} (1 − (−1)^{j}L_{k−2j} x + x^{2})  (19)

for an even nonnegative integer k. By direct multiplication of the factors in (19) we get the identities

p_{2i+1}(k) = − ∑_{j=0}^{i} \binom{\frac{k}{2} − (2j + 1)}{i − j} S_{2j+1}(k) ,  (20)

for i = 0, 1, 2, …, \frac{k−2}{2}, and

p_{2i}(k) = ∑_{j=0}^{i} \binom{\frac{k}{2} − 2j}{i − j} S_{2j}(k) ,  (21)

for i = 0, 1, 2, …, \frac{k}{2}. By shifting indexes of summation it is possible to join (20) and (21) into the relation

p_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n}\binom{\frac{k}{2} − n + 2i}{i} S_{n−2i}(k) ,  (22)

for n = 0, 1, 2, …, k. This identity can be extended to any positive integer n with respect to Lemma 9, as p_{n}(k) = 0 for n < 0 or n > k.

If k is an even positive integer, the denominator in (1) is a polynomial of an odd degree k + 1:

D_{k+1}(x) = ∑_{i=0}^{k+1} d_{k+1,i} x^{i} ,

where integers d_{k+1,i} = (−1)^{\frac{i(i+1)}{2}} \left[{k+1 \atop i}\right] are terms of sequence \underline{A055870}, called the “signed Fibonomial triangle” in Sloane’s On-Line Encyclopedia of Integer Sequences [13]. Identity (2) implies

D_{k+1}(x) = ∏_{j=0}^{k}(1 − α^{k−j} β^{j} x) = (1 − (αβ)^{\frac{k}{2}} x) ∏_{\begin{matrix}j=0 \\ j≠ \frac{k}{2} \end{matrix}}^{k}(1 − α^{k−j} β^{j} x)

= (1 − (−1)^{\frac{k}{2}} x) ∏_{j=0}^{\frac{k}{2} −1} (1 − (−1)^{j}α^{k−2j} x) (1 − (−1)^{j}β^{k−2j} x)

= (1 − (−1)^{\frac{k}{2}} x) ∏_{j=0}^{\frac{k}{2} −1} (1 − (−1)^{j}(α^{k−2j} + β^{k−2j}) x + (αβ)^{k−2j}x^{2})

= (1 − (−1)^{\frac{k}{2}} x) ∏_{j=0}^{\frac{k}{2} −1}(1 − (−1)^{j}L_{k−2j}x + x^{2}) ,

according to the relation αβ = −1 and the formula L_{k−2j} = α^{k−2j}+β^{k−2j}. Thus, with respect to (19), D_{k+1}(x) = (1−(−1)^{\frac{k}{2}} x) P_{k}(x). By multiplying on the right–hand side and comparing coefficients of x^{i} we have the following relations between coefficients d_{k+1,i} of D_{k+1}(x) and coefficients p_{i}(k) of P_{k}(x)

d_{k+1,0} = p_{0}(k) = 1 ,
d_{k+1,i} = p_{i}(k) + (−1)^{\frac{k}{2} +1} p_{i−1}(k) , i = 1, 2, …, k ,
d_{k+1,k+1} = (−1)^{\frac{k}{2} +1}p_{k}(k) = (−1)^{\frac{k}{2} +1} .

As p_{n}(k) = 0 for n < 0 or n > k we can rewrite the previous relations in the recurrence

p_{n}(k) + (−1)^{\frac{k}{2} +1} p_{n−1}(k) = d_{k+1,n} ,

which holds for any integer n. Using Lemma 13 we have

p_{n}(k) = ∑_{j=0}^{n}(−1)^{\frac{k}{2} (n+j)}d_{k+1,j}  (23)

for any nonnegative integer n.

To complete the proof of (6) we have to invert identity (22). Setting a_{n} = p_{2n}(k), b_{n} = S_{2n}(k) and q = \frac{k}{2} in inverse formula (11) we obtain

S_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n+i} (\binom{\frac{k}{2} − n + i}{i} + \binom{\frac{k}{2} − n + i − 1}{i − 1}) p_{n−2i}(k) .  (24)

From (23) and (24) we deduce that

S_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=0}^{n−2i}(−1)^{n+i}(−1)^{\frac{k}{2} (n+j)} (\binom{\frac{k}{2} − n + i}{i} + \binom{\frac{k}{2} − n + i − 1}{i − 1}) d_{k+1,j} .

Putting d_{k+1,j} = (−1)^{\frac{j}{2} (j+1)}\left[{k+1 \atop j}\right] we obtain (6) after simplification.

Proof of Corollary 3. The assertion is obviously true with respect to (5) if k is any odd integer. For even values of k identity (6) can be written using (15) as

S_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n+i+n \frac{k}{2}} σ(n − 2i) Θ(i, k, n) .

With respect to Lemma 12 for k → ∞

σ(n − 2i) ∼ (−1)^{\frac{n−2i}{2} (n−2i+k+1)}\left[{k + 1 \atop n − 2i}\right] = (−1)^{i}(−1)^{\frac{n}{2} (n+k+1)}\left[{k + 1 \atop n − 2i}\right] .

Hence, we obtain

S_{n}(k) ∼ ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n+i+n \frac{k}{2}} (−1)^{i}(−1)^{\frac{n}{2} (n+k+1)} Θ(i, k, n) \left[{k + 1 \atop n − 2i}\right]

= ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{\frac{n}{2} (n−1)} Θ(i, k, n) \left[{k + 1 \atop n − 2i}\right]

and the assertion follows from the congruence \frac{n}{2}(n−1) ≡ ⌊\frac{n}{2}⌋ (mod 2).

Proof of Theorem 4. For any even m we have

∑_{i=0}^{\frac{m}{2}}(σ(m − 2i) − σ(m − 2(i + 1))) = σ(m) − σ(−2)

and analogously for any odd m

∑_{i=0}^{\frac{m−1}{2}}(σ(m − 2i) − σ(m − 2(i + 1))) = σ(m) − σ(−1) .

Thus, using Lemma 16 we obtain for any integer m

σ(m) = ∑_{i=0}^{⌊ \frac{m}{2} ⌋}(σ(m − 2i) − σ(m − 2(i + 1)))

and with respect to Lemma 17

σ(m) = ∑_{i=0}^{⌊ \frac{m}{2} ⌋}(−1)^{\frac{m−2i}{2} (m−2i+k+1)} \frac{1}{F_{\frac{k}{2} +1}} \left[{k + 2 \atop m − 2i}\right] F_{\frac{k}{2} +1−(m−2i)}

= (−1)^{\frac{m}{2} (m+k+1)} \frac{1}{F_{\frac{k}{2} +1}} ∑_{i=0}^{⌊ \frac{m}{2} ⌋}(−1)^{i}\left[{k + 2 \atop m − 2i}\right] F_{\frac{k+2}{2} −m+2i} .

Proof of Corollary 5. Applying Theorem 2 and Theorem 4, consecutively, we get

S_{n}(k) = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n+i+n \frac{k}{2}} σ(n − 2i) Θ(i, k, n)

= ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{n+i+n \frac{k}{2}} Θ(i, k, n) \frac{(−1)^{\frac{n}{2} (n+k+1)}}{F_{\frac{k}{2} +1}} ∑_{j=i}^{⌊ \frac{n}{2} ⌋}(−1)^{j} \left[{k + 2 \atop n − 2j}\right] F_{\frac{k+2}{2} −n+2j}

= ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{\frac{n}{2} (n−1)+i} \frac{1}{F_{\frac{k}{2} +1}} Θ(i, k, n) ∑_{j=i}^{⌊ \frac{n}{2} ⌋}(−1)^{j} \left[{k + 2 \atop n − 2j}\right] F_{\frac{k+2}{2} −n+2j}

= ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{⌊ \frac{n}{2} ⌋+i} Θ(i, k, n) \frac{1}{F_{\frac{k}{2} +1}} ∑_{j=i}^{⌊ \frac{n}{2} ⌋}(−1)^{j} \left[{k + 2 \atop n − 2j}\right] F_{\frac{k+2}{2} −n+2j}

= \frac{(−1)^{⌊ \frac{n}{2} ⌋}}{F_{\frac{k}{2} +1}} ∑_{i=0}^{⌊ \frac{n}{2} ⌋} ∑_{j=i}^{⌊ \frac{n}{2} ⌋} (−1)^{i+j} Θ(i, k, n) \left[{k + 2 \atop n − 2j}\right] F_{\frac{k+2}{2} −n+2j} .

Proof of Theorem 6. Similarly as in the proof of Theorem 4 we obtain for any integer m the relation

∑_{i=0}^{⌊ \frac{m}{4} ⌋}(σ(m − 4i) − σ(m − 4(i + 1))) = σ(m) − σ (m − 4 (⌊\frac{m}{4}⌋ + 1)) .

Thus, using Lemma 16 we obtain

σ(m) = ∑_{i=0}^{⌊ \frac{m}{4} ⌋}(σ(m − 4i) − σ(m − 4(i + 1))) .

With respect to Lemma 18 we have

σ(m) = ∑_{i=0}^{⌊ \frac{m}{4} ⌋}(−1)^{\frac{m−4i}{2} (m−4i+k+1)}\left[{k + 4 \atop m − 4i}\right]\frac{F_{\frac{k}{2} +2−(m−4i)}}{F_{\frac{k}{2} +1}F_{k+3}F_{k+4}}

· (F_{\frac{k}{2} +1−(m−4i)} L_{\frac{k}{2} +2−(m−4i)} F_{k+3} − F_{m−4i} F_{m−4i−1})

= \frac{(−1)^{\frac{m}{2} (m+k+1)}}{F_{\frac{k}{2} +1}F_{k+3}F_{k+4}} ∑_{i=0}^{⌊ \frac{m}{4} ⌋} \left[{k + 4 \atop m − 4i}\right]F_{\frac{k}{2} +2−(m−4i)}

· (F_{\frac{k}{2} +1−(m−4i)} L_{\frac{k}{2} +2−(m−4i)} F_{k+3} − F_{m−4i} F_{m−4i−1}) .

Proof of Corollary 7. Identities (9) and (10) can be obtained from identities (5) and (6) with respect to S_{n}(k) = 0 for positive integers k, n > ⌊\frac{k+1}{2}⌋ (see Lemma 9).

Proof of Corollary 8. Each of these three sums follows from identity (6) after some tedious simplification.

6 Concluding remark

It is interesting to compare the effectiveness of formulas (6) and (8) in contrast to defining formula (4) for computation of S_{n}(k). Therefore, we found the CPU time (in seconds) required for computation of sums S_{3}(k) for some values of k using the system Mathematica on a standard PC. There is the measured time in Table 2.

Table 2. CPU time for S_{3}(k)

k
100 200 300 400 500 600 700 800
(4) 0.297 2.438 8.547 21.296 43.172 77.078 130.125 203.594
(6)  0  0 0.047 0.094 0.172 0.297 0.484 0.719
(8)  0  0 0.015 0.046 0.078 0.156 0.25  0.359

References

[1] L. Carlitz, Generating functions for powers of a certain sequence of numbers, Duke Math. J., 29 (1962), 521–537.

[2] S. W. Golomb, Problem 4720, Amer. Math. Monthly, 64 (1957), 49.

[3] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics: a Foundation for Computer Science, Addison-Wesley Publishing Company, 2nd ed., 2nd Edition, 1994.

[4] A. F. Horadam, Generating functions for powers of a certain generalised sequence of numbers, Duke Math. J., 32 (1965), 437–446.

[5] V. Kac, Ch. Pokman, Quantum Calculus, Springer–Verlag, New York, 2002.

[6] T. Mansour, A formula for generating function of powers of Horadam’s sequence, Australas. J. Combin., 30 (2004), 207–212.

[7] J. Riordan, Generating functions for powers of Fibonacci numbers, Duke Math. J., 29 (1962), 5–12.

[8] J. Riordan, Combinatorial Identities, J. Wiley, New York (1968).

[9] H. Rothe, Systematisches Lehrbuch der Aritmetik, Leipzig, 1811.

[10] J. Seibert, P. Trojovský, On sums of certain products of Lucas numbers, Fibonacci Quart., 44 (2006), 172–180.

[11] A. G. Shannon, A method of Carlitz applied to the k-th power generating function for Fibonacci numbers, Fibonacci Quart., 12 (1974), 293–299.

[12] S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Holstel Press, 1989.

[13] N. J. A. Sloane, The On-Line Encylopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences/index.html.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 05A15, 05A10. Keywords: generating function, Riordan’s theorem, generalized Fibonacci numbers, Fibonomial coefficients. (Concerned with sequence \underline{A055870}.)

Received January 19 2006; revised version received May 2 2007. Published in Journal of Integer Sequences, May 2 2007.

Return to Journal of Integer Sequences home page.