A Unified Treatment of Certain Classes of Combinatorial Identities

Necdet Batır and Anthony Sofo Department of Mathematics Nevşehir Hacı Bektaş Veli University 50300 Nevşehir Turkey and College of Engineering and Science Victoria University VIC 8001 Australia

                  nbatir@hotmail.com
                anthony.sofo@vu.edu.au

Abstract

We propose and prove some general combinatorics formulas. Applying these formulas, we obtain some new binomial harmonic and harmonic Fibonacci and Lucas number identities. We also recover some known identities included in the works of Frontczak and Boyadzhiev.

1 Introduction

For s ∈ ℂ and n ∈ ℕ, a generalized harmonic number H_{n}^{(s)} of order s is defined by

H_{n}^{(s)} = ∑_{k=1}^{n} \frac{1}{k^{s}} , and H_{n}^{(1)} = H_{n}, H_{0}^{(s)} = 0,

where H_{n} = 1 + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n} are the usual harmonic numbers; see [6, 12, 21]. Alternating or skew-harmonic numbers H_{n}^{−} are defined by

H_{n}^{−} = ∑_{k=1}^{n} \frac{(−1)^{k+1}}{k} ,

which is the partial sum of log 2 = ∑_{k=1}^{∞} \frac{(−1)^{k+1}}{k}; see [8, 17, 20].

In 2009, Boyadzhiev [7] studied some binomial sums involving the harmonic numbers using Euler’s transform and obtained the following identity:

∑_{k=1}^{n} \binom{n}{k}a^{k}b^{n−k}H_{k} = (a + b)^{n}H_{n} − ∑_{k=1}^{n} \frac{b^{k}}{k} (a + b)^{n−k},

which can be equivalently written, by setting a/b = x, as follows:

∑_{k=1}^{n} \binom{n}{k}H_{k}x^{k} = (x + 1)^{n}(H_{n} − ∑_{k=1}^{n} \frac{1}{k(x + 1)^{k}} ).  (1)

Batir, in a recent paper [3], offers many interesting finite sum identities with harmonic numbers, including (1). Frontczak [14, 15] obtained a complement of the identity given in (1) and derived

∑_{k=1}^{n} \binom{n}{k}H_{k}x^{k} = (x + 1)^{n}H_{n} − ∑_{k=0}^{n−1} H_{n−k}(x + 1)^{k},  (2)

which can be regarded as a complement of (1). Frontczak [15] also derived an analogue formula for the skew-harmonic numbers. Throughout this paper, we take

α = \frac{1 + \sqrt{5}}{2} and β = \frac{1 − \sqrt{5}}{2}.

The Fibonacci sequence (F_{n})_{n≥0} is given by F_{0} = 0, F_{1} = 1, and for n ≥ 2 it satisfies the recursion relation F_{n} = F_{n−1}+F_{n−2}. The Lucas sequence (L_{n})_{n≥0} satisfies the same recursion relation, that is, L_{n} = L_{n−1} + L_{n−2} with the initial values L_{0} = 2 and L_{1} = 1, where n ∈ ℕ. The Binet formulas for the Fibonacci numbers F_{n} and Lucas numbers L_{n} state that

F_{n} = \frac{α^{n} − β^{n}}{\sqrt{5}} and L_{n} = α^{n} + β^{n}.

In this article we develop a general formula which contains (1) and many others as special cases. Our results allow to establish many interesting new identities involving the harmonic numbers, Fibonacci numbers, and Lucas numbers. More precisely, for any sequence (a_{n})_{n≥1} in ℂ and x ∈ ℂ we consider the following general binomial sums:

∑_{k=1}^{n} \binom{n}{k} ∑_{j=1}^{k} a_{j}x^{k}.

To demonstrate the usefulness of our formulas we give many applications. The following simple, but useful, identities will be required in our ongoing analysis:

\binom{n + 1}{k} = \frac{n + 1}{k}\binom{n}{k − 1},  (3)

\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k − 1}.  (4)

We continue with the following two lemmas.

Lemma 1. Let (a_{n})_{n≥1} be any real or complex sequence. Then we have

∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \binom{k}{j}a_{j} = ∑_{k=1}^{n} \binom{n}{k}\frac{a_{k}}{k} .

This lemma is not new, and a generalization of it can be found in Boyadzhiev [9, Eq. 3]. As stated there, Boyadzhiev attributed this lemma to ’t Woord [24]. Also see equation (5.6) in [8]. It is worthy to note that Batır [2] rediscovered this lemma in 2017, and established many interesting combinatorial identities and series involving the harmonic numbers.

Lemma 2. Let (a_{n})_{n≥1} and (b_{n})_{n≥1} be any two sequences of real or complex numbers. Then we have

∑_{k=1}^{n} a_{k} ∑_{j=1}^{k} b_{j} = ∑_{p=0}^{n−1} ∑_{k=1}^{n−p} b_{k}a_{p+k}.

This lemma was proved in [4] and helps us to reduce some double sums to a single sum.

2 Main Results

In this section we collect our main results.

Theorem 3. Let (a_{n})_{n≥1} be any sequence in ℂ. Then we have

∑_{k=0}^{n}(−1)^{k}\binom{n}{k} ∑_{j=1}^{k} a_{j} = ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k}a_{k+1}.

Proof. By (4), we obtain

∑_{k=1}^{n}(−1)^{k}\binom{n}{k} ∑_{j=1}^{k} a_{j} = ∑_{k=1}^{n}(−1)^{k}(\binom{n − 1}{k} + \binom{n − 1}{k − 1}) ∑_{j=1}^{k} a_{j}

= ∑_{k=1}^{n−1}(−1)^{k}\binom{n − 1}{k} ∑_{j=1}^{k} a_{j} + ∑_{k=1}^{n}(−1)^{k}\binom{n − 1}{k − 1} ∑_{j=1}^{k} a_{j},  (5)

where we have used \binom{n}{n+1} = 0 and \binom{n−1}{−1} = 0. On the other hand, we have

∑_{k=1}^{n}(−1)^{k}\binom{n − 1}{k − 1} ∑_{j=1}^{k} a_{j} = ∑_{k=0}^{n−1}(−1)^{k−1}\binom{n − 1}{k} ∑_{j=1}^{k+1} a_{j}

= ∑_{k=0}^{n−1}(−1)^{k−1}\binom{n − 1}{k}(a_{k+1} + ∑_{j=1}^{k} a_{j})

= ∑_{k=0}^{n−1}(−1)^{k−1}\binom{n − 1}{k}a_{k+1} − ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k} ∑_{j=1}^{k} a_{j}.  (6)

Replacing (6) in (5), we complete the proof. Theorem 4. Let (a_{n})_{n≥1} be any sequence in ℂ, x ∈ ℂ, and A_{n} be the nth partial sum of (a_{n})_{n≥1}, that is, A_{n} = a_{1} + a_{2} + ⋯ + a_{n}. Then

∑_{k=1}^{n} \binom{n}{k}A_{k}x^{k} = (1 + x)^{n−1} ∑_{k=0}^{n−1} ( ∑_{j=0}^{k} \binom{k}{j}a_{j+1}x^{j+1})\frac{1}{(1 + x)^{k}} .  (7)

Here the sum of 0 terms is taken 0, that is, A_{0} = 0. Proof. Let us define

g_{n}(x) = ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}A_{k}x^{k}.

Clearly, we have by Theorem 3 that

g_{n}(x) = ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}A_{j}x^{j} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k} ∑_{j=1}^{k} (A_{j}x^{j} − A_{j−1}x^{j−1})

= ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k} (A_{k+1}x^{k+1} − A_{k}x^{k}) .

Using A_{k+1} = A_{k} + a_{k+1}, we obtain

g_{n}(x) = ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k} ((A_{k} + a_{k+1})x^{k+1} − A_{k}x^{k})

= ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k}A_{k}x^{k+1} + ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k}a_{k+1}x^{k+1}

− ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k}A_{k}x^{k}

= (1 − x)g_{n−1}(x) + ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k}a_{k+1}x^{k+1}.  (8)

Now we shall show the following expression by mathematical induction.

g_{n}(x) = (1 − x)^{n−1} ∑_{k=0}^{n−1} ( ∑_{j=0}^{k}(−1)^{j+1}\binom{k}{j}a_{j+1}x^{j+1})\frac{1}{(1 − x)^{k}} .  (9)

It is easy to see that (9) is true for n = 1. We assume that (9) is true for n. Then by (8) and the induction hypothesis, we have

g_{n+1}(x) = (1 − x)^{n} ∑_{k=0}^{n−1} ( ∑_{j=0}^{k}(−1)^{j+1}\binom{k}{j}a_{j+1}x^{j+1})\frac{1}{(1 − x)^{k}}

+ ∑_{k=0}^{n}(−1)^{k+1}\binom{n}{k}a_{k+1}x^{k+1}

= (1 − x)^{n} ∑_{k=0}^{n} ( ∑_{j=0}^{k}(−1)^{j+1}\binom{k}{j}a_{j+1}x^{j+1})\frac{1}{(1 − x)^{k}} ,

which shows that (9) is valid for n + 1, and the proof of (9) is complete. Replacing x by −x in (9) we prove (7). Setting x = 1 in (7), we obtain the following conclusion:

Corollary 5. Let (a_{n})_{n≥1} be any sequence of complex numbers. Then we have

∑_{k=1}^{n} \binom{n}{k}A_{k} = 2^{n−1} ∑_{k=0}^{n−1} \frac{1}{2^{k}} ∑_{j=0}^{k} \binom{k}{j}a_{j+1}.  (10)

3 Applications

In this section we present many applications of our main theorems. Our first identity recovers (1).

Identity 6. Let n ∈ ℕ and x ∈ ℂ. Then

∑_{k=1}^{n} \binom{n}{k}H_{k}x^{k} = (1 + x)^{n}(H_{n} − ∑_{k=1}^{n} \frac{1}{k(1 + x)^{k}} ).  (11)

Proof. Putting a_{k} = \frac{1}{k} in Theorem 4, we get

∑_{k=1}^{n} \binom{n}{k}H_{k}x^{k} = (1 + x)^{n−1} ∑_{k=0}^{n−1} ( ∑_{j=0}^{k} \binom{k}{j}\frac{x^{j+1}}{j + 1})\frac{1}{(1 + x)^{k}} .

From (3), it is very easy to see that ∑_{j=0}^{k} \binom{k}{j} \frac{x^{j+1}}{j+1} = \frac{(1+x)^{k+1}−1}{k+1}, so that

∑_{k=1}^{n} \binom{n}{k}H_{k}x^{k} = (1 + x)^{n} ∑_{k=1}^{n} \frac{(1 + x)^{k} − 1}{k(1 + x)^{k}},

which is equivalent to (11).

In the particular cases of x = −1 and x = 1 in (11), we get

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k} = −\frac{1}{n} and ∑_{k=1}^{n} \binom{n}{k}H_{k} = 2^{n} ∑_{k=1}^{n} \frac{2^{k} − 1}{k2^{k}}.  (12)

Remark 7. The first identity here is very old and due to Euler [13]. The second identity is also well known and recently, it has been rediscovered by many authors; (see [3, 7, 11, 16, 22]).

Identity 8. Let n ∈ ℕ and x ∈ ℂ. Then we have

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}x^{k} = (1 + x)^{n}(H_{n}^{2} − ∑_{k=1}^{n} \frac{H_{n} − 2H_{k} + H_{n−k}}{k(1 + x)^{k}} − 2 ∑_{k=1}^{n} \frac{1}{k^{2}(1 + x)^{k}} ).  (13)

Proof. Letting a_{k} = (H_{k})^{2} − (H_{k−1})^{2} in (7) and using the relation H_{k+1} = H_{k} + \frac{1}{k+1}, we get

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}x^{k} = ∑_{k=1}^{n} \binom{n}{k} ∑_{j=1}^{k}(H_{j}^{2} − H_{j−1}^{2})x^{k}

= (1 + x)^{n−1} ∑_{k=0}^{n−1} ( ∑_{j=0}^{k} \binom{k}{j}\frac{H_{j+1} + H_{j}}{j + 1} x^{j+1})(1 + x)^{−k}.  (14)

On the other hand, by (3) we have

∑_{j=0}^{k} \binom{k}{j}\frac{H_{j+1} + H_{j}}{j + 1} x^{j+1} = \frac{1}{k + 1} ∑_{j=0}^{k} \binom{k + 1}{j + 1}(2H_{j+1} − \frac{1}{j + 1})x^{j+1}

= \frac{1}{k + 1} ∑_{j=1}^{k+1} \binom{k + 1}{j}(2H_{j} − \frac{1}{j})x^{j}

= \frac{2}{k + 1} ∑_{j=1}^{k+1} \binom{k + 1}{j}H_{j}x^{j} − \frac{1}{k + 1} ∑_{j=1}^{k+1} \binom{k + 1}{j}\frac{x^{j}}{j} .  (15)

By (11), it follows that

∑_{j=1}^{k+1} \binom{k + 1}{j}H_{j}x^{j} = (1 + x)^{k+1} ∑_{j=1}^{k+1} \frac{(1 + x)^{j} − 1}{j(1 + x)^{j}}.

Using this identity, we conclude from (14) and (15), and Lemma 1

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}x^{k} = 2(1 + x)^{n} ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{(1 + x)^{j} − 1}{j(1 + x)^{j}}

− (1 + x)^{n} ∑_{k=1}^{n} \frac{1}{k(1 + x)^{k}} ∑_{j=1}^{k} \binom{k}{j}\frac{x^{j}}{j} .  (16)

Applying Lemma 1, one easily gets

∑_{j=1}^{k} \binom{k}{j}\frac{x^{j}}{j} = ∑_{j=1}^{k} \frac{(1 + x)^{j} − 1}{j}.  (17)

Substituting (17) in (16), we get, after some simplifications, that

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}x^{k} = 2(1 + x)^{n} ∑_{k=1}^{n} \frac{H_{k}}{k} − 2(1 + x)^{n} ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{1}{j(1 + x)^{j}}

− (1 + x)^{n} ∑_{k=1}^{n} \frac{1}{k(1 + x)^{k}} ∑_{j=1}^{k} \frac{(1 + x)^{j}}{j} + (1 + x)^{n} ∑_{k=1}^{n} \frac{H_{k}}{k(1 + x)^{k}} .  (18)

Setting

a_{k} = \frac{(1 + x)^{−k}}{k} and b_{k} = \frac{(1 + x)^{k}}{k}

in Lemma 2, we obtain

∑_{k=1}^{n} \frac{1}{k(1 + x)^{k}} ∑_{j=1}^{k} \frac{(1 + x)^{j}}{j} = H_{n}^{(2)} + ∑_{k=1}^{n} \frac{H_{k} + H_{n−k} − H_{n}}{k(1 + x)^{k}} .  (19)

Hassani and Rahimpour [18] proved that for any double sequence (a_{ij})_{i,j≥1} the following summation formula is valid.

∑_{j,k=1}^{n} a_{jk} = ∑_{k=1}^{n} ∑_{j=1}^{k}(a_{jk} + a_{kj}) − ∑_{k=1}^{n} a_{kk}.

Setting a_{ij} = \frac{(1+x)^{−j}}{ij} here, it follows that

∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{1}{j(1 + x)^{j}} = ∑_{k=1}^{n} \frac{H_{n} − H_{k}}{k(1 + x)^{k}} + ∑_{k=1}^{n} \frac{1}{k^{2}(1 + x)^{k}} .  (20)

Substituting (19) and (20) in (18) the proof is completed.

Identity 9. Putting x = −1 and x = 1 in (13), we obtain

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{2} = \frac{H_{n}}{n} − \frac{2}{n^{2}} ,  (21)

and

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2} = 2^{n}(H_{n}^{2} − ∑_{k=1}^{n} \frac{H_{n} − 2H_{k} + H_{n−k}}{k2^{k}} − 2 ∑_{k=1}^{n} \frac{1}{k^{2}2^{k}} ).  (22)

Remark 10. The first identity here has previously been obtained by Wang [23] by the method of Riordan arrays, and rediscovered by Boyadzhiev [9].

Identity 11. For n ∈ ℕ we have

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{3} = \frac{3H_{n}}{n^{2}} − \frac{H_{n}^{2}}{2n} + \frac{5H_{n}^{(2)}}{2n} − \frac{6}{n^{3}} .

Proof. Using H_{k} = H_{k+1} − \frac{1}{k+1}, we see that

H_{k+1}^{3} − H_{k}^{3} = \frac{3H_{k+1}^{2}}{k + 1} − \frac{3H_{k+1}}{(k + 1)^{2}} + \frac{1}{(k + 1)^{3}} .  (23)

Applying Theorem 3 with a_{k} = H_{k}^{3} − H_{k−1}^{3} and using (23) we obtain

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{3} = ∑_{k=1}^{n}(−1)^{k}\binom{n}{k} ∑_{j=1}^{k} (H_{j}^{3} − H_{j−1}^{3})

= ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k} (H_{k+1}^{3} − H_{k}^{3})

= ∑_{k=0}^{n−1}(−1)^{k+1}\binom{n − 1}{k} (\frac{3H_{k+1}^{2}}{k + 1} − \frac{3H_{k+1}}{(k + 1)^{2}} + \frac{1}{(k + 1)^{3}} ) .

Letting k + 1 = k′ and then dropping the prime, we get by (3)

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{3} = \frac{3}{n} ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{2}

− \frac{3}{n} ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}\frac{H_{k}}{k} + \frac{1}{n} ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}\frac{1}{k^{2}} .  (24)

By Lemma 1 and the first identity in (12) we have

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}\frac{H_{k}}{k} = ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k}(−1)^{j}\binom{k}{j}H_{j} = −H_{n}^{(2)}.  (25)

We also have from [9, p. 5] or [8, Eq. (9.6)] that

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}\frac{1}{k^{2}} = −\frac{H_{n}^{2} + H_{n}^{(2)}}{2} .  (26)

Replacing (25) and (26) in (24) and using (21), we obtain the desired result.

Remark 12. Using Theorem 3 it is possible to evaluate all the sums

∑_{k=1}^{n}(−1)^{k}\binom{n}{k} (H_{k})^{m} ,

for m ∈ ℕ, but it requires lengthy calculations when m is large.

Identity 6 and Identity 8 enable us to establish new identities involving the product of the harmonic numbers and Fibonacci numbers, and harmonic numbers and Lucas numbers.

Identity 13. Let n ∈ ℕ. Then

∑_{k=1}^{n} \binom{n}{k}H_{k}F_{k} = H_{n}F_{2n} − ∑_{k=1}^{n} \frac{F_{2n−2k}}{k} ,

and ∑_{k=1}^{n} \binom{n}{k}H_{k}L_{k} = H_{n}L_{2n} − ∑_{k=1}^{n} \frac{L_{2n−2k}}{k} .

Proof. Let P_{n}(x) denote the left-hand side of (11). Evaluate P_{n}(x) at x = α and x = β, where α = \frac{1+\sqrt{5}}{2} and β = \frac{1−\sqrt{5}}{2}. This gives

P_{n}(α) = α^{2n}H_{n} − ∑_{k=1}^{n} \frac{α^{2n−2k}}{k} and P_{n}(β) = β^{2n}H_{n} − ∑_{k=1}^{n} \frac{β^{2n−2k}}{k} ,

where we have used α^{2} = α + 1 and β^{2} = β + 1. Now calculate P_{n}(α) ∓ P_{n}(β), and then use the Binet formulas for F_{n} and L_{n}.

Remark 14. Identity 13 can be easily derived from [10, Eq. 10] by letting c_{k} = (−1)^{k−1}F_{k}; see also [8, Thm. 6.1]. Furthermore, it can be compared with equations (9) and (10) in [14]. If in the first part of Identity 13 we put

∑_{k=1}^{n} \frac{F_{2n−2k}}{k} = ∑_{k=1}^{n} F_{2k−1}H_{n−k},

then we obtain the result in [14]. Similarly, if in the second part of Identity 13 we put

∑_{k=1}^{n} \frac{L_{2n−2k}}{k} = 2H_{n} + ∑_{k=1}^{n} L_{2k−1}H_{n−k},

then we obtain the result in [14].

Identity 15. For n ∈ ℕ we have

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}F_{3k} = (−1)^{n}2^{n}(H_{n}F_{n} − ∑_{k=1}^{n} \frac{(−1)^{k}F_{n−k}}{k2^{k}} ),

and

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}L_{3k} = (−1)^{n}2^{n}(H_{n}L_{n} − ∑_{k=1}^{n} \frac{(−1)^{k}L_{n−k}}{k2^{k}} ).

Proof. Letting x = −α^{3} and x = −β^{3} in (11), and using 1 − α^{3} = −2α and 1 − β^{3} = −β, respectively, we get

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}α^{3} = (−1)^{n}2^{n}α^{n}H_{n} − 2^{n} ∑_{k=1}^{n} \frac{(−1)^{n−k}α^{n−k}}{k2^{k}} ,

and

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}β^{3} = (−1)^{n}2^{n}β^{n}H_{n} − 2^{n} ∑_{k=1}^{n} \frac{(−1)^{n−k}β^{n−k}}{k2^{k}} .

The combination of these two identities according to the Binet formula yields the desired results.

Identity 16. For n ∈ ℕ we have

∑_{k=1}^{n} \binom{n}{k}H_{k}F_{3k} = 2^{n}(H_{n}F_{2n} − ∑_{k=1}^{n} \frac{F_{2n−2k}}{k2^{k}} ),

and ∑_{k=1}^{n} \binom{n}{k}H_{k}L_{3k} = 2^{n}(H_{n}L_{2n} − ∑_{k=1}^{n} \frac{L_{2n−2k}}{k2^{k}} ).

Proof. First we note that 1 + α^{3} = 2α^{2} and 1 + β^{3} = 2β^{2}. Computing (11) at x = α^{3} and x = β^{3} yields

∑_{k=1}^{n} \binom{n}{k}H_{k}α^{3k} = 2^{n}α^{2n}H_{n} − ∑_{k=1}^{n} \frac{2^{n−k}α^{2n−2k}}{k}

and ∑_{k=1}^{n} \binom{n}{k}H_{k}β^{3k} = 2^{n}β^{2n}H_{n} − ∑_{k=1}^{n} \frac{2^{n−k}β^{2n−2k}}{k} .

Now the proof follows from combining these two sums according to the Binet formula for F_{n} and L_{n}.

By the same method used in the proof of Identity 15 and Identity 16 we can prove the next two results by the help of Identity 8.

Identity 17. For n ∈ ℕ we have

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

and

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}L_{k} = L_{2n}H_{n}^{2} − ∑_{k=1}^{n} \frac{(H_{n} − 2H_{k} + H_{n−k})L_{2n−2k}}{k} − 2 ∑_{k=1}^{n} \frac{L_{2n−2k}}{k^{2}} ,

where we have used here ∑_{k=1}^{n} \frac{H_{k}}{k} = \frac{H_{n}^{2}+H_{n}^{(2)}}{2} ; see [1] and [2].

Identity 18. Putting x = α^{3} in (13), and using 1+α^{3} = 2α^{2}, 1−α^{3} = −2α and 1+β^{3} = 2β^{2}, 1 − β^{3} = −2β, the evaluation of (13) yields for n ∈ ℕ

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}F_{3k}

= 2^{n}F_{2n}H_{n}^{2} − 2^{n} ∑_{k=1}^{n} \frac{(H_{n} − 2H_{k} + H_{n−k})F_{2n−2k}}{k2^{k}} − 2^{n+1} ∑_{k=1}^{n} \frac{F_{2n−2k}}{k^{2}2^{k}}

and

∑_{k=1}^{n} \binom{n}{k}H_{k}^{2}L_{3k}

= 2^{n}L_{2n}H_{n}^{2} − 2^{n} ∑_{k=1}^{n} \frac{(H_{n} − 2H_{k} + H_{n−k})L_{2n−2k}}{k2^{k}} − 2^{n+1} ∑_{k=1}^{n} \frac{L_{2n−2k}}{k^{2}2^{k}} .

The proof of the following identity can be done similar to the proof of Identity 15 by letting x = −α^{3} and x = −β^{3} in Identity 8, respectively.

Identity 19. For n ∈ ℕ we have

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{2}F_{3k} = (−1)^{n}2^{n}(F_{n}H_{n}^{2} − 2 ∑_{k=1}^{n} \frac{(−1)^{k}F_{n−k}}{k^{2}2^{k}}

− ∑_{k=1}^{n} \frac{(−1)^{k}(H_{n} − 2H_{k} + H_{n−k})F_{n−k}}{k2^{k}} ),

and

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{2}L_{3k} = (−1)^{n}2^{n}(L_{n}H_{n}^{2} − 2 ∑_{k=1}^{n} \frac{(−1)^{k}L_{n−k}}{k^{2}2^{k}}

− ∑_{k=1}^{n} \frac{(−1)^{k}(H_{n} − 2H_{k} + H_{n−k})L_{n−k}}{k2^{k}} ).

Identity 20. For n ∈ ℕ we have

∑_{k=1}^{n} \binom{n}{k}H_{k}^{−}x^{k} = (1 + x)^{n} ∑_{k=1}^{n} \frac{1 − (1 − x)^{k}}{k(1 + x)^{k}} .  (27)

Proof. The proof follows from Theorem 4 by setting a_{k} = \frac{(−1)^{k+1}}{k}.

Remark 21. Identity 20 can be easily obtained from [10, Cor. 1] by setting a_{k} = (−1)^{k}H_{k}^{−}; see also [8, Thm. 1.6]. Letting x = −1 and x = 1 in (27), respectively, we get

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{−} = \frac{1 − 2^{n}}{n} and ∑_{k=1}^{n} \binom{n}{k}H_{k}^{−} = 2^{n} ∑_{k=1}^{n} \frac{1}{k2^{k}} .

The first identity here can be found in [8, Eq. (9.20)], and [9, Eq. (14)]. The second identity recovers (2).

The next identity is not new and can be found in entry (9.43) in [8].

Identity 22. For integers n ≥ 1 we have

∑_{k=1}^{n} \binom{n}{k}H_{k}^{−}F_{3k} = 2^{n} ∑_{k=1}^{n} \frac{F_{2n−2k}}{2^{k}k} − 2^{n} ∑_{k=1}^{n} \frac{(−1)^{k}F_{2n−k}}{k}

and ∑_{k=1}^{n} \binom{n}{k}H_{k}^{−}L_{3k} = 2^{n} ∑_{k=1}^{n} \frac{L_{2n−2k}}{2^{k}k} − 2^{n} ∑_{k=1}^{n} \frac{(−1)^{k}L_{2n−k}}{k} .

Proof. Clearly, we have 1 + α^{3} = 2α^{2}, 1 − α^{3} = −2α and 1 + β^{3} = 2β^{2}, 1 − β^{3} = −2β. Thus, evaluating (27) at x = α^{3} yields

Q_{n}(α) := ∑_{k=1}^{n} \binom{n}{k}H_{k}^{−}α^{3k} = 2^{n} ∑_{k=1}^{n} \frac{α^{2n−2k}}{k2^{k}} − ∑_{k=1}^{n} \frac{(−1)^{k}α^{2n−k}}{k} ,

and similarly

Q_{n}(β) := ∑_{k=1}^{n} \binom{n}{k}H_{k}^{−}β^{3k} = 2^{n} ∑_{k=1}^{n} \frac{β^{2n−2k}}{k2^{k}} − 2^{n} ∑_{k=1}^{n} \frac{(−1)^{k}β^{2n−k}}{k} .

The evaluation of Q_{n}(α) ∓ Q_{n}(β) leads to the desired results.

The proof of the following result is similar to that of Identity 15. Identity 23. For n ∈ ℕ we have

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{−}F_{3k} = (−1)^{n}2^{n}( ∑_{k=1}^{n} \frac{(−1)^{k}F_{n−k}}{2^{k}k} − ∑_{k=1}^{n} \frac{(−1)^{k}F_{n+k}}{k} ),

and

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{−}L_{3k} = (−1)^{n}2^{n}( ∑_{k=1}^{n} \frac{(−1)^{k}L_{n−k}}{2^{k}k} − ∑_{k=1}^{n} \frac{(−1)^{k}L_{n+k}}{k} ).

The proof of the next two identities can be done by proceeding as in the proof of Identity 8 by setting a_{k} = \frac{1}{k^{2}} and a_{k} = (H_{k}^{−})^{2} − (H_{k−1}^{−})^{2} in Theorem 4. We omit the proofs. Identity 24. Letting a_{k} = \frac{1}{k^{2}} in (7), we get after some simple computations

∑_{k=1}^{n} \binom{n}{k}H_{k}^{(2)}x^{k} = (1 + x)^{n}(H_{n}^{(2)} − ∑_{k=1}^{n} \frac{H_{n} − H_{n−k}}{k(1 + x)^{k}} ).  (28)

Considering the two values of x = 1 and x = −1, we have

∑_{k=1}^{n} \binom{n}{k}H_{k}^{(2)} = 2^{n} (H_{n}^{(2)} − ∑_{k=1}^{n} \frac{H_{n} − H_{n−k}}{k2^{k}} )

and ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{(2)} = −\frac{H_{n}}{n} .

Identity 25. Letting a_{k} = \frac{(−1)^{k+1}}{k} in Theorem 4, we get for n ∈ ℕ and x ∈ ℂ

∑_{k=1}^{n} \binom{n}{k} (H_{k}^{−})^{2} x^{k} = (1 + x)^{n}(2 ∑_{k=1}^{n} \frac{H_{k} + H_{n−k} − H_{n}}{k} (\frac{1 − x}{1 + x})^{k}

+ H_{n}^{(2)} + ∑_{k=1}^{n} \frac{H_{n} − H_{n−k}}{k(1 + x)^{k}} − 2 ∑_{k=1}^{n} \frac{1}{k}(\frac{1 − x}{1 + x})^{k} ∑_{j=1}^{k} \frac{(1 − x)^{−j}}{j} ).  (29)

Considering the two values of x = 1 and x = −1, we get

∑_{k=1}^{n} \binom{n}{k} (H_{k}^{−})^{2} = 2^{n}(H_{n}^{(2)} + ∑_{k=1}^{n} \frac{H_{n} − H_{n−k}}{2^{k}k} − 2 ∑_{k=1}^{n} \frac{1}{2^{k}k^{2}} ),

and ∑_{k=1}^{n}(−1)^{k}\binom{n}{k} (H_{k}^{−})^{2} = \frac{H_{n}}{n} − \frac{2^{n+1}}{n} ∑_{k=1}^{n} \frac{1}{k2^{k}} .

Identity 26. Letting x = α and x = β in (28) and combining the resulting expressions according to the Binet formula one gets

∑_{k=1}^{n} \binom{n}{k}H_{k}^{(2)}F_{k} = F_{2n}H_{n}^{(2)} − ∑_{k=1}^{n} \frac{(H_{n} − H_{n−k})F_{2n−2k}}{k} ,

and ∑_{k=1}^{n} \binom{n}{k}H_{k}^{(2)}L_{k} = L_{2n}H_{n}^{(2)} − ∑_{k=1}^{n} \frac{(H_{n} − H_{n−k})L_{2n−2k}}{k} .

Identity 27. Letting x = α^{3} and x = β^{3} in (28) and combining the results according to the Binet formula one gets

∑_{k=1}^{n} \binom{n}{k}H_{k}^{(2)}F_{3k} = 2^{n}H_{n}^{(2)}F_{2n} − 2^{n} ∑_{k=1}^{n} \frac{(H_{n} − H_{n−k})F_{2n−2k}}{k2^{k}}

and ∑_{k=1}^{n} \binom{n}{k}H_{k}^{(2)}L_{3k} = 2^{n}H_{n}^{(2)}L_{2n} − 2^{n} ∑_{k=1}^{n} \frac{(H_{n} − H_{n−k})L_{2n−2k}}{k2^{k}} .

Identity 28. Setting x = −α^{3} and x = −β^{3} in (28), respectively, and then combining the resulting identities according to the Binet formula, we get

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{(2)}F_{3k} = (−1)^{n}2^{n}(H_{n}^{(2)}F_{n} − ∑_{k=1}^{n} \frac{(−1)^{k}(H_{n} − H_{n−k})F_{n−k}}{k} ),

and

∑_{k=1}^{n}(−1)^{k}\binom{n}{k}H_{k}^{(2)}L_{3k} = (−1)^{n}2^{n}(H_{n}^{(2)}L_{n} − ∑_{k=1}^{n} \frac{(−1)^{k}(H_{n} − H_{n−k})L_{n−k}}{k} ).

Identity 29. Setting x = α^{3} and x = β^{3} in (29), respectively, and then combining the resulting identities according to the Binet formula, we get

∑_{k=1}^{n} \binom{n}{k} (H_{k}^{−})^{2} F_{3k} = 2^{n}F_{2n}H_{n}^{(2)} − 2^{n+1} ∑_{k=1}^{n} \frac{(−1)^{k}}{k} ∑_{j=1}^{k} \frac{(−1)^{j}F_{2n+k−j}}{j}

+ 2^{n+1} ∑_{k=1}^{n} \frac{(−1)^{k}(H_{k} + H_{n−k} − H_{n})F_{2n−k}}{k2^{k}} + 2^{n} ∑_{k=1}^{n} \frac{(H_{n} − H_{k})F_{2n−k}}{k2^{k}} .

and

∑_{k=1}^{n} \binom{n}{k} (H_{k}^{−})^{2} L_{3k} = 2^{n}L_{2n}H_{n}^{(2)} − 2^{n+1} ∑_{k=1}^{n} \frac{(−1)^{k}}{k} ∑_{j=1}^{k} \frac{(−1)^{j}L_{2n+k−j}}{j}

+ 2^{n+1} ∑_{k=1}^{n} \frac{(−1)^{k}(H_{k} + H_{n−k} − H_{n})L_{2n−k}}{k2^{k}} + 2^{n} ∑_{k=1}^{n} \frac{(H_{n} − H_{k})L_{2n−k}}{k2^{k}} .

The following identity has been posed as a problem by Ohtsuka in [19].

Identity 30. For all positive integers n the following identity holds:

∑_{k=1}^{n} \binom{n}{k} ∑_{1≤i≤j≤k} \frac{1}{ij} = ∑_{1≤i≤j≤n} \frac{2^{n} − 2^{n−i}}{ij} .

Proof. Since

∑_{1≤i≤j≤k} \frac{1}{ij} = 1 + \frac{1}{2} (1 + \frac{1}{2}) + \frac{1}{3} (1 + \frac{1}{2} + \frac{1}{3}) + ⋯

+ \frac{1}{k} (1 + \frac{1}{2} + ⋯ + \frac{1}{k}) = ∑_{k=1}^{n} \frac{H_{k}}{k}

and similarly

∑_{1≤i≤j≤n} \frac{2^{n} − 2^{n−i}}{ij} = ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{2^{n} − 2^{k−j}}{j} ,

it suffices to show

∑_{k=1}^{n} \binom{n}{k} ∑_{k=1}^{n} \frac{H_{k}}{k} = ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{2^{n} − 2^{k−j}}{j} .

Substituting a_{k} = \frac{H_{k}}{k} in (10), we get by the help of (3)

∑_{k=1}^{n} \binom{n}{k} ∑_{j=1}^{k} \frac{H_{j}}{j} = 2^{n−1} + 2^{n−1} ∑_{k=1}^{n−1} \frac{1}{2^{k}} ∑_{j=1}^{k} \binom{k}{j}\frac{H_{j+1}}{j + 1}

= 2^{n−1} + 2^{n} ∑_{k=2}^{n} \frac{1}{k2^{k}} ∑_{j=1}^{k} \binom{k}{j}H_{j}.

Using the second identity in (12), we find

∑_{k=1}^{n} \binom{n}{k} ∑_{j=1}^{k} \frac{H_{j}}{j} = 2^{n−1} + 2^{n} ∑_{k=2}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{2^{j} − 1}{j2^{j}}

= 2^{n} ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{2^{j} − 1}{j2^{j}} = ∑_{k=1}^{n} \frac{1}{k} ∑_{j=1}^{k} \frac{2^{n} − 2^{n−j}}{j} ,

as claimed.

As usual let S(n, k) denote the Stirling numbers of the second kind, that is

S(n, k) = \frac{(−1)^{k}}{k} ∑_{j=0}^{k}(−1)^{j}\binom{k}{j}j^{n}.

The following identity provides a new proof, based on Theorem 3, of a well-known formula for the sum of powers of consecutive positive integers; see, for example, [5].

Identity 31. For m, n ∈ ℕ the following identity holds:

∑_{k=1}^{n} k^{m} = ∑_{k=1}^{n} \binom{n}{k}(k − 1)!S(m + 1, k).

Proof. Putting a_{k} = k^{m} in Theorem 3, we get

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

= \frac{1}{n} ∑_{k=1}^{n}(−1)^{k}\binom{n}{k}k^{m+1} = (−1)^{n}(n − 1)!S(m + 1, n).

Employing the well-known binomial inversion formula the proof is completed.

4 Acknowledgments

We wish to thank the anonymous referee for useful comments and bringing our attention to the papers [9] and [10].

References

[1] V. Adamchik, On Stirling numbers and Euler sums, J. Comput. Appl. Math. 79 (1997), 119–130.

[2] N. Batır, On some combinatorial identities and harmonic sums, Int. J. Number Theory 13 (2017), 1695–1709.

[3] N. Batır, Combinatorial identities involving harmonic numbers, Integers 20 (2020), #A25.

[4] N. Batır, Remarks on Vălean’s master theorem of series, J. Class. Anal. 13 (2018), 79–82.

[5] K. N. Boyadzhiev, Close encounters with the Stirling numbers of the second kind, Math. Mag. 85 (2012), 252–266.

[6] K. N. Boyadzhiev, Series with central binomial coefficients, Catalan numbers, and harmonic numbers, J. Integer Sequences 15 (2012), Article 12.1.7.

[7] K. N. Boyadzhiev, Harmonic number identities via Euler’s transform, J. Integer Sequences 12 (2009), Article 09.6.1.

[8] K. N. Boyadzhiev, Notes on the Binomial Transform, Theory and Table, World Scientific, 2018.

[9] K. N. Boyadzhiev, Binomial transform and the backward difference, Adv. Appl. Discrete Math. 18 (2014), 43–63.

[10] K. N. Boyadzhiev, Binomial transform of products, Ars Combin. 126 (2006), 415–434.

[11] M. W. Coffey, On some series representations of the Hurwitz zeta function, J. Comput. Appl. Math. 216 (2008), 297–305.

[12] L. Comtet, Advanced Combinatorics, D. Reidel Pub. Co, 1974.

[13] L. Euler, Demonstratio insignis theorematis numerici circa uncias potestatum binomialium, Nova Acta Acad. Sci. Petropol. 15 (1799/1802), 33–43.

[14] R. Frontczak, Harmonic sums via Euler’s transform: Complementing the approach of Boyadzhiev, J. Integer Sequences 23 (2020), Article 20.3.2.

[15] R. Frontczak, Binomial sums with skew-harmonic numbers, preprint, 2020. Avail-

    able at: https://www.researchgate.net/publication/339446734_Binomial_sums_
    with_skew-harmonic_numbers.

[16] L. Gonzalez, A new approach for proving generating combinatorial identities, Internat. J. Math. Ed. Sci. Tech. 41 (2010), 359–372.

[17] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[18] M. Hassani and S. Rahimpour, L-summing method, Research Report Collection 7 (2004), Article 10.

[19] H. Ohtsuka, Proposed problem 12106, Amer. Math. Monthly 126 (2019), 370.

[20] A. Sofo, New classes of harmonic number identities. J. Integer Sequences 15 (2012), Article 12.7.4.

[21] A. Sofo and H. M. Srivastava, Identities for the harmonic numbers and binomial coefficients, Ramanujan J. 25 (2011), 93–113.

[22] M. Z. Spivey, Combinatorial sums and finite differences, Discrete Math. 307 (2007), 3130–3146.

[23] W. Wang, Riordan arrays and harmonic number identities, Comput. Math. Appl. 60 (2010), 1494–1509.

[24] A. N. ’t Woord, Solution II to problem 10490, Amer. Math. Monthly 106 (1999), 588.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 05A19. Keywords: combinatorial identity, binomial coefficient, harmonic number, Fibonacci sequence, Lucas sequence, harmonic number sum.

(Concerned with sequences \underline{A000032} and \underline{A000045}.)

Received November 16 2020; revised versions received November 28 2020; November 30 2020; December 30 2020; January 6 2021; February 2 2021. Published in Journal of Integer Sequences, February 2 2021.

Return to Journal of Integer Sequences home page.