Sum Relations for Lucas Sequences^{1}

Yuan He and Wenpeng Zhang Department of Mathematics Northwest University Xi’an 710069 P. R. China

                      hyyhe@yahoo.com.cn
                      wpzhang@nwu.edu.cn

Abstract In this paper, we establish four sum relations for Lucas sequences. As applications, we derive some combinatorial identities involving Lucas sequences that extend some known results.

1 Introduction

Given two integer parameters P and Q, the Lucas sequences of the first kind U_{n} = U_{n}(P, Q) (n ∈ ℕ) and of the second kind V_{n} = V_{n}(P, Q) (n ∈ ℕ) are defined by the recurrence relations

U_{0} = 0, U_{1} = 1, and U_{n} = P U_{n−1} − QU_{n−2} (n ≥ 2),  (1)
V_{0} = 2, V_{1} = p, and V_{n} = P V_{n−1} − QV_{n−2} (n ≥ 2).  (2)

The characteristic equation x^{2} − P x + Q = 0 of the sequences U_{n} and V_{n} has two roots α = (P + \sqrt{D})/2 and β = (P − \sqrt{D})/2 with the discriminant D = P^{2} − 4Q. Note that D^{1/2} = α−β. Furthermore, D = 0 means x^{2}−P x+Q = 0 has the repeated root α = β = P/2. It is well known that for any n ∈ ℕ (see [4, pp. 41–44]),

P U_{n} + V_{n} = 2U_{n+1}, (α − β)U_{n} = α^{n} − β^{n}, V_{n} = α^{n} + β^{n}.  (3)

The Lucas sequences U_{n} and V_{n} can be regarded as the generalization of many integer sequences, for example, F_{n}, L_{n}, P_{n}, Q_{n}, J_{n}, and j_{n}, known as the Fibonacci, Lucas, Pell, Pell-Lucas, Jacobsthal, and Jacobsthal-Lucas numbers, according to whether P = 1, Q = −1, P = 2, Q = −1, or P = 1, Q = −2; see [5] for a good introduction. These numbers play important roles in many different areas of mathematics, so their numerous elegant properties have been studied by many authors, see for example, [3, 4].

1Supported by the National Natural Science Foundation of China (No. 10671155).

The idea of the present paper stems from the familiar combinatorial theorem about sets called the principle of cross-classification. We establish four sum relations for the Lucas sequences as follows.

Theorem 1. Let n be a positive integer, and let s_{1}, s_{2}, …, s_{n} be any non-negative integers. Then

− ∑_{1≤i≤n} \frac{U_{s_{i}}}{α^{s_{i}}} + ∑_{1≤i<j≤n} \frac{U_{s_{i}+s_{j}}}{α^{s_{i}+s_{j}}} − ∑_{1≤i<j<k≤n} \frac{U_{s_{i}+s_{j}+s_{k}}}{α^{s_{i}+s_{j}+s_{k}}} + ⋯ + (−1)^{n} \frac{U_{s_{1}+s_{2}+···+s_{n}}}{α^{s_{1}+s_{2}+···+s_{n}}}

= −D^{\frac{n−1}{2}} \frac{U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}}{α^{s_{1}+s_{2}+···+s_{n}}} ,  (4)

− ∑_{1≤i≤n} \frac{U_{s_{i}}}{β^{s_{i}}} + ∑_{1≤i<j≤n} \frac{U_{s_{i}+s_{j}}}{β^{s_{i}+s_{j}}} − ∑_{1≤i<j<k≤n} \frac{U_{s_{i}+s_{j}+s_{k}}}{β^{s_{i}+s_{j}+s_{k}}} + ⋯ + (−1)^{n} \frac{U_{s_{1}+s_{2}+···+s_{n}}}{β^{s_{1}+s_{2}+···+s_{n}}}

= (−1)^{n}D^{\frac{n−1}{2}} \frac{U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}}{β^{s_{1}+s_{2}+···+s_{n}}} ,  (5)

∑_{1≤i≤n} \frac{V_{s_{i}}}{α^{s_{i}}} + ∑_{1≤i<j≤n} \frac{V_{s_{i}+s_{j}}}{α^{s_{i}+s_{j}}} + ∑_{1≤i<j<k≤n} \frac{V_{s_{i}+s_{j}+s_{k}}}{α^{s_{i}+s_{j}+s_{k}}} + ⋯ + \frac{V_{s_{1}+s_{2}+···+s_{n}}}{α^{s_{1}+s_{2}+···+s_{n}}}

= 2^{n} − 2 + \frac{V_{s_{1}}V_{s_{2}} ⋯ V_{s_{n}}}{α^{s_{1}+s_{2}+···+s_{n}}} ,  (6)

∑_{1≤i≤n} \frac{V_{s_{i}}}{β^{s_{i}}} + ∑_{1≤i<j≤n} \frac{V_{s_{i}+s_{j}}}{β^{s_{i}+s_{j}}} + ∑_{1≤i<j<k≤n} \frac{V_{s_{i}+s_{j}+s_{k}}}{β^{s_{i}+s_{j}+s_{k}}} + ⋯ + \frac{V_{s_{1}+s_{2}+···+s_{n}}}{β^{s_{1}+s_{2}+···+s_{n}}}

= 2^{n} − 2 + \frac{V_{s_{1}}V_{s_{2}} ⋯ V_{s_{n}}}{β^{s_{1}+s_{2}+···+s_{n}}} .  (7)

Theorem 1 has some applications and can be deduced as the generalization of some known results. In section 2, we shall make use of Theorem 1 to illustrate its effectiveness. In section 3, we shall give the proof of Theorem 1.

2 Some applications of Theorem 1

Theorem 2. Let n be a positive integer, and let C_{n} = U_{n}/Q^{n}, D_{n} = V_{n}/Q^{n}, E_{n} = U_{n}^{2}/Q^{n}, F_{n} = U_{n}V_{n}/Q^{n}, G_{n} = V_{n}^{2}/Q^{n}. Suppose that the discriminant D is not equal to 0. Then, for non-negative integers s_{1}, s_{2}, …, s_{n},

− ∑_{1≤i≤n} E_{s_{i}} + ∑_{1≤i<j≤n} E_{s_{i}+s_{j}} − ∑_{1≤i<j<k≤n} E_{s_{i}+s_{j}+s_{k}} + ⋯ + (−1)^{n}E_{s_{1}+s_{2}+···+s_{n}}

= \begin{cases}D^{\frac{n−2}{2}} D_{s_{1}+s_{2}+···+s_{n}}U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}, & 2 | n, \\ −D^{\frac{n−1}{2}} C_{s_{1}+s_{2}+···+s_{n}}U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}, & 2 ∤ n, \end{cases}  (8)

− ∑_{1≤i≤n} F_{s_{i}} + ∑_{1≤i<j≤n} F_{s_{i}+s_{j}} − ∑_{1≤i<j<k≤n} F_{s_{i}+s_{j}+s_{k}} + ⋯ + (−1)^{n}F_{s_{1}+s_{2}+···+s_{n}}

= \begin{cases}D^{\frac{n}{2}} C_{s_{1}+s_{2}+···+s_{n}}U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}, & 2 | n, \\ −D^{\frac{n−1}{2}} D_{s_{1}+s_{2}+···+s_{n}}U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}, & 2 ∤ n, \end{cases}  (9)

∑_{1≤i≤n} F_{s_{i}} + ∑_{1≤i<j≤n} F_{s_{i}+s_{j}} + ∑_{1≤i<j<k≤n} F_{s_{i}+s_{j}+s_{k}} + ⋯ + F_{s_{1}+s_{2}+···+s_{n}}

= C_{s_{1}+s_{2}+···+s_{n}}V_{s_{1}}V_{s_{2}} ⋯ V_{s_{n}},  (10)

∑_{1≤i≤n} G_{s_{i}} + ∑_{1≤i<j≤n} G_{s_{i}+s_{j}} + ∑_{1≤i<j<k≤n} G_{s_{i}+s_{j}+s_{k}} + ⋯ + G_{s_{1}+s_{2}+···+s_{n}}

= 2^{n+1} − 4 + D_{s_{1}+s_{2}+···+s_{n}}V_{s_{1}}V_{s_{2}} ⋯ V_{s_{n}}.  (11)

Proof. Adding and subtracting (4) and (5), and (6) and (7), respectively, we are done by applying the last two identities of (3).

Corollary 3. Let n be a positive integer, and let k be a non-negative integer. Suppose that the discriminant D is not equal to 0. Then

∑_{i=0}^{n} \binom{n}{i}Q^{(n−i)k}U_{ik}V_{ik} = U_{kn}V_{k}^{n},  (12)

∑_{i=0}^{n} \binom{n}{i}Q^{(n−i)k}V_{ik}^{2} = 2^{n+1}Q^{nk} + V_{kn}V_{k}^{n},  (13)

∑_{i=0}^{n} \binom{n}{i}(−1)^{i}Q^{(n−i)k}U_{ik}^{2} = \begin{cases}D^{\frac{n−2}{2}} V_{kn}U_{k}^{n}, & 2 | n, \\ −D^{\frac{n−1}{2}} U_{kn}U_{k}^{n}, & 2 ∤ n, \end{cases}  (14)

∑_{i=0}^{n} \binom{n}{i}(−1)^{i}Q^{(n−i)k}U_{ik}V_{ik} = \begin{cases}D^{\frac{n}{2}} U_{kn}U_{k}^{n}, & 2 | n, \\ −D^{\frac{n−1}{2}} V_{kn}U_{k}^{n}, & 2 ∤ n. \end{cases}  (15)

Proof. Setting s_{1} = s_{2} = ⋯ = s_{n} = k in Theorem 2, the desired results follow.

Remark 4. By the last two identities of (3), one can easily check that if the discriminant D ≠ 0 then U_{n}V_{n} = U_{2n}, V_{n}^{2} = V_{2n} + 2Q^{n}, U_{n}^{2} = (V_{2n} − 2Q^{n})/D, which together with Corollary 3 deduce some interesting results. The case k being an even number in (12) gives a sophisticated identity for Fibonacci and Lucas numbers which was asked by Hoggatt as an advanced problem in [1]. The case k = 1 in (14) and (15) give the familiar combinatorial identities for Fibonacci and Lucas numbers, see for example, [2, 6].

Theorem 5. Let n be a positive integer, let s_{1}, s_{2}, …, s_{n} be any non-negative integers such that s_{1} + s_{2} + ⋯ + s_{n} = s, and let C_{m,n} = U_{m}U_{n−m}, D_{m,n} = U_{m}V_{n−m}, E_{m,n} = V_{m}U_{n−m}, F_{m,n} = V_{m}V_{n−m}. Suppose that the discriminant D is not equal to 0. Then

− ∑_{1≤i≤n} C_{s_{i},s} + ∑_{1≤i<j≤n} C_{s_{i}+s_{j},s} − ∑_{1≤i<j<k≤n} C_{s_{i}+s_{j}+s_{k},s} + ⋯ + (−1)^{n}C_{s,s}

= \begin{cases}−2D^{\frac{n−2}{2}} U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}, & 2 | n, \\ 0, & 2 ∤ n, \end{cases}  (16)

− ∑_{1≤i≤n} D_{s_{i},s} + ∑_{1≤i<j≤n} D_{s_{i}+s_{j},s} − ∑_{1≤i<j<k≤n} D_{s_{i}+s_{j}+s_{k},s} + ⋯ + (−1)^{n}D_{s,s}

= \begin{cases}0, & 2 | n, \\ −2D^{\frac{n−1}{2}} U_{s_{1}}U_{s_{2}} ⋯ U_{s_{n}}, & 2 ∤ n, \end{cases}  (17)

∑_{1≤i≤n} E_{s_{i},s} + ∑_{1≤i<j≤n} E_{s_{i}+s_{j},s} + ∑_{1≤i<j<k≤n} E_{s_{i}+s_{j}+s_{k},s} + ⋯ + E_{s,s}

= (2^{n} − 2)U_{s},  (18)

∑_{1≤i≤n} F_{s_{i},s} + ∑_{1≤i<j≤n} F_{s_{i}+s_{j},s} + ∑_{1≤i<j<k≤n} F_{s_{i}+s_{j}+s_{k},s} + ⋯ + F_{s,s}

= (2^{n} − 2)V_{s} + 2V_{s_{1}}V_{s_{2}} ⋯ V_{s_{n}}.  (19)

Proof. Multiplying α^{s} in the both sides of (4) and (6), β^{s} in the both sides of (5) and (7), and then adding and subtracting (4) and (5), and (6) and (7), respectively, the desired results immediately follow by applying the last two identities of (3).

Corollary 6. Let n be a positive integer, and let k be a non-negative integer. Suppose that the discriminant D is not equal to 0. Then

∑_{i=0}^{n} \binom{n}{i}Q^{ik}U_{(n−2i)k} = 0,  (20)

∑_{i=0}^{n} \binom{n}{i}Q^{ik}V_{(n−2i)k} = 2V_{k}^{n},  (21)

∑_{i=0}^{n} \binom{n}{i}(−1)^{i}Q^{ik}V_{(n−2i)k} = \begin{cases}2D^{\frac{n}{2}} U_{k}^{n}, & 2 | n, \\ 0, & 2 ∤ n, \end{cases}  (22)

∑_{i=0}^{n} \binom{n}{i}(−1)^{i}Q^{ik}U_{(n−2i)k} = \begin{cases}0, & 2 | n, \\ 2D^{\frac{n−1}{2}} U_{k}^{n}, & 2 ∤ n. \end{cases}  (23)

Proof. By the last two identities of (3), one can easily check that if the discriminant D ≠ 0 then V_{ik}U_{(n−i)k} = U_{kn} + Q^{ik}U_{(n−2i)k}, V_{ik}V_{(n−i)k} = V_{nk} + Q^{ik}V_{(n−2i)k}, U_{ik}U_{(n−i)k} = (V_{nk} − Q^{ik}V_{(n−2i)k})/D, U_{ik}V_{(n−i)k} = U_{nk} − Q^{ik}U_{(n−2i)k}. Thus, by setting s_{1} = s_{2} = ⋯ = s_{n} = k in Theorem 5, Corollary 6 follows immediately.

Remark 7. The equations (21)–(23) extend the powers of Fibonacci and Lucas numbers as sums, see for example, [2, 6].

3 The proof of Theorem 1

The proof of Theorem 1. Clearly, the case n = 1 in Theorem 1 is complete.

Now, we consider the case n ≥ 2. By (3), it is easy to see that if the discriminant D ≠ 0 then U_{n} = nα^{n−1} = nβ^{n−1}, V_{n} = 2α^{n} = 2β^{n} for all n ∈ ℕ. Thus, in view of the fact ∑_{i=1}^{n} \binom{n}{i} = 2^{n} − 1 and for any integer n ≥ 2,

− ∑_{1≤i≤n} s_{i} + ∑_{1≤i<j≤n}(s_{i} + s_{j}) − ∑_{1≤i<j<k≤n}(s_{i} + s_{j} + s_{k}) + ⋯ + (−1)^{n}(s_{1} + s_{2} + ⋯ + s_{n}) = 0,

Theorem 1 is complete when the discriminant D = 0. Next, we use induction on n to consider the discriminant D ≠ 0. Applying the last two identities of (3), we derive

U_{m}U_{n} = −\frac{U_{m+n} − α^{m}U_{n} − α^{n}U_{m}}{\sqrt{D}} ,  (24)

U_{m}U_{n} = \frac{U_{m+n} − β^{m}U_{n} − β^{n}U_{m}}{\sqrt{D}} ,  (25)
V_{m}V_{n} = V_{m+n} + α^{m}V_{n} + α^{n}V_{m} − 2α^{m+n},  (26)
V_{m}V_{n} = V_{m+n} + β^{m}V_{n} + β^{n}V_{m} − 2β^{m+n},  (27)

which imply the case n = 2 in Theorem 1 is complete. Assume that (4) holds for all 2 ≤ n = m. Then, by multiplying U_{s_{m+1}}/α^{s_{m+1}} in the both sides of (4), and applying (24), we obtain

−D^{\frac{m}{2}} \frac{U_{s_{1}}U_{s_{2}} ⋯ U_{s_{m}}U_{s_{m+1}}}{α^{s_{1}+s_{2}+···+s_{m}+s_{m+1}}}

= ∑_{1≤i≤m}(\frac{U_{s_{i}+s_{m+1}}}{α^{s_{i}+s_{m+1}}} − \frac{U_{s_{i}}}{α^{s_{i}}} − \frac{U_{s_{m+1}}}{α^{s_{m+1}}} )

− ∑_{1≤i<j≤m}(\frac{U_{s_{i}+s_{j}+s_{m+1}}}{α^{s_{i}+s_{j}+s_{m+1}}} − \frac{U_{s_{i}+s_{j}}}{α^{s_{i}+s_{j}}} − \frac{U_{s_{m+1}}}{α^{s_{m+1}}} )

+ ∑_{1≤i<j<k≤m}(\frac{U_{s_{i}+s_{j}+s_{k}+s_{m+1}}}{α^{s_{i}+s_{j}+s_{k}+s_{m+1}}} − \frac{U_{s_{i}+s_{j}+s_{k}}}{α^{s_{i}+s_{j}+s_{k}}} − \frac{U_{s_{m+1}}}{α^{s_{m+1}}} )

− ⋯ − (−1)^{m}(\frac{U_{s_{1}+s_{2}+···+s_{m}+s_{m+1}}}{α^{s_{1}+s_{2}+···+s_{m}+s_{m+1}}} − \frac{U_{s_{1}+s_{2}+···+s_{m}}}{α^{s_{1}+s_{2}+···+s_{m}}} − \frac{U_{s_{m+1}}}{α^{s_{m+1}}} ),

which together with ∑_{i=1}^{m} \binom{m}{i}(−1)^{i} = −1 means (4) holds for all n = m + 1. In a similar consideration, (5), (6) and (7) hold for all n = m + 1. This concludes the induction step. We are done. □

4 Acknowledgements

The authors would like to thank the anonymous referees for their valuable suggestions.

References

[1] V. E. Hoggatt, Advanced Problem H–88, Fibonacci Quart. 6 (1968), 253.

[2] R. Knott, Fibonacci and Golden Ratio Formulae. Available at

    http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormulae.html.

[3] P. Ribenboim, My Numbers, My Friends, Springer-Verlag, 2000.

[4] P. Ribenboim, The Book of Prime Number Records, Springer, 1989.

[5] N. J. A. Sloane, The Online Encyclopedia of Integer sequences, Available at

    http://www.research.att.com/∼njas/sequences.

[6] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Ellis Horwood Limited, 1989.

2000 Mathematics Subject Classification: Primary 05A19; Secondary 11B39. Keywords: Lucas sequence, combinatorial identity, sum relation.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000129}, \underline{A001045}, \underline{A002203}, and \underline{A014551}.)

Received March 5 2010; revised version received April 6 2010. Published in Journal of Integer Sequences, April 9 2010.

Return to Journal of Integer Sequences home page.