Double Sums Involving Binomial Coefficients and Special Numbers

Kunle Adegoke; Robert Frontczak; Karol Gryszka

doi:10.2478/amsil-2026-0013

1. Motivation

The binomial coefficients are defined, for non-negative integers n and k, by

0

(\begin{matrix} n \\ k \end{matrix}) = \begin{array}{l} \frac{n!}{k! (n - k)!}, & n \geq k, \\ 0, & n < k . \end{array}

More generally, for complex numbers r and s, they are defined by

0

(\begin{matrix} r \\ s \end{matrix}) = \frac{Γ (r + 1)}{Γ (s + 1) Γ (r - s + 1)},

where the Gamma function, Γ(z), is defined for ℜ(z) > 0 by the integral [26]

0

Γ (z) = \int_{0}^{\infty} e^{- t} t^{z - 1} dt .

Sum identities involving binomial coefficients are ubiquitous in probability, combinatorics and number theory. These sums are so prominent that whole textbooks have been devoted to describing the techniques for their evaluation [14, 15, 23, 29], the most prominent being generating function, contour integration, the usage of analytical and combinatorial arguments, and the application of the Wilf-Zeilberger algorithm. Single sums over a reciprocal of a binomial coefficient have also been studied extensively. Recent articles dealing with these forms include [1, 2, 6, 7, 8, 21, 25, 30], and several others. One common technique to tackle these forms is to express the binomial coefficient ${(\begin{matrix} n \\ k \end{matrix})}^{- 1}$ as a Beta integral. Another approach is to apply differentiation to generalized binomial coefficients.

Double binomial sums have also been studied in the recent past. A general telescoping approach for double summation was outlined by Chen et al. in [11]. Chu [12, 13] studied two prominent double sums in 2017 and 2018, respectively. Our paper was particularly inspired by the observation that the incomplete binomial sum

(1.1)

\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) x^{j}, x \in ℂ, k < n,

has no simple closed form. If we work with the Gaussian hypergeometric function ₂F₁ defined by

0

_{2} F_{1} (a, b; c; z) = \sum_{n = 0}^{\infty} \frac{{(a)}_{n} {(b)}_{n}}{{(c)}_{n}} \frac{z^{n}}{n!},

where (q)_n is the Pochhammer symbol given by (q)_n = Γ(q + n)/Γ(q), and a, b, c are complex numbers, then there is the relation [27]

0

\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) x^{j} = \frac{x^{k + 1}}{x + 1} (\begin{matrix} n \\ k \end{matrix}) {}_{2}F_{1} (1, n + 1; n + 1 - k; \frac{1}{x + 1}) .

This relation is useful under some circumstances but it does not allow for an elementary treatment of sums involving the incomplete binomial sum. In this paper, we find an elementary approach for double sums where the inner sum is binomial but incomplete as in (1.1). We apply our core identity to double sums involving a range of famous numbers such as harmonic numbers, Fibonacci numbers, Stirling numbers and r-Stirling numbers of the second kind.

2. Preliminaries

This section contains the definitions and basic relations for the quantities used in the main text.

The Fibonacci numbers F_n and the Lucas numbers L_n are defined, for n ∈ ℤ, through the recurrence relations

0

\begin{matrix} F_{n} = F_{n - 1} + F_{n - 2}, n \geq 2, F_{0} = 0, F_{1} = 1, \\ L_{n} = L_{n - 1} + L_{n - 2}, n \geq 2, L_{0} = 2, L_{1} = 1. \end{matrix}

The Binet formulas for these sequences are

0

F_{n} = \frac{α^{n} - β^{n}}{α - β}, L_{n} = α^{n} + β^{n}, n \in ℤ,

with

α = \frac{1 + \sqrt{5}}{2}

being the golden ratio and

β = - \frac{1}{α}

. For negative subscripts we have F_−n = (−1)ⁿ⁻¹F_n and L_−n = (−1)ⁿL_n. These famous sequences are indexed as sequences A000045 and A000032 in the On-Line Encyclopedia of Integer Sequences [24]. A huge amount of further information about them can be found in the books by Koshy [17] and Vajda [28], for instance. Also recall that the Gibonacci sequence has the same recurrence relation as the Fibonacci sequence but starts with arbitrary initial values, i.e.,

0

G_{k} = G_{k - 1} + G_{k - 2}, (k \geq 2) .

with G₀ and G₁ arbitrary numbers (usually integers) not both zero. When G₀ = 0 and G₁ = 1 then G_n = F_n, and when G₀ = 2 and G₁ = 1 then G_n = L_n, respectively. The sequence obeys the generalized Binet formula

0

G_{n} = A α^{n} + B β^{n},

where

A = \frac{G_{1} - G_{0} β}{α - β}

and

B = \frac{G_{0} α - G_{1}}{α - β}

Harmonic numbers H_s and odd harmonic numbers O_s are defined for 0 ≠ s ∈ ℂ \ ℤ⁻ by the recurrence relations

0

H_{s} = H_{s - 1} + \frac{1}{s} and O_{s} = O_{s - 1} + \frac{1}{2 s - 1},

with H₀ = 0 and O₀ = 0. One way to generalize this definition is to consider harmonic numbers

H_{s}^{(m)}

and odd harmonic numbers

O_{s}^{(m)}

of order m ∈ ℂ that are defined by

0

H_{s}^{(m)} = H_{s - 1}^{(m)} + \frac{1}{s^{m}} and O_{s}^{(m)} = O_{s - 1}^{(m)} + \frac{1}{{(2 s - 1)}^{m}},

with

H_{0}^{(m)} = 0

and

O_{0}^{(m)} = 0

so that

H_{s} = H_{s}^{(1)}

and

O_{s} = O_{s}^{(1)}

. The recurrence relations imply that if s = n is a non-negative integer, then

0

H_{n}^{(m)} = \sum_{j = 1}^{n} \frac{1}{j^{m}} and O_{n}^{(m)} = \sum_{j = 1}^{n} \frac{1}{{(2 j - 1)}^{m}} .

Harmonic numbers are connected to the digamma function ψ(z) = Γ′(z)/Γ(z) through the fundamental relation

0

H_{z} = ψ (z + 1) + γ,

where γ is the Euler–Mascheroni constant.

We conclude this section with a definition of Stirling numbers of the second kind. For integers n and k the Stirling numbers of the second kind, denoted by $\begin{array}{l} n \\ k \end{array}\}$ , are the coefficients in the expansion

0

z^{n} = \sum_{k = 0}^{n} \begin{array}{l} n \\ k \end{array}\} {(z)}_{k},

where (z)_k is the falling factorial defined by (z)₀ = 1, (z)_n = z(z − 1) ⋯ (z − n + 1) for n > 0. These numbers count the number of ways to partition a set of n elements into exactly k nonempty subsets. We will often make use of the property

0

\begin{matrix} \begin{array}{l} n \\ k \end{array}\} = 0, & if k > n . \end{matrix}

The exponential generating function of

\begin{array}{l} n \\ k \end{array}\}

equals

0

\sum_{n \geq k} \begin{array}{l} n \\ k \end{array}\} \frac{t^{n}}{n!} = \frac{1}{k!} {(e^{t} - 1)}^{k} .

Let r be a positive integer. The r-Stirling numbers of the second kind

{\begin{array}{l} n + r \\ k + r \end{array}\}}_{r}

are defined by the exponential generating function

0

\sum_{n \geq k} {\begin{array}{l} n + r \\ k + r \end{array}\}}_{r} \frac{t^{n}}{n!} = \frac{1}{k!} e^{rt} {(e^{t} - 1)}^{k} .

We also have

0

{(z + r)}^{n} = \sum_{k = 0}^{n} \begin{array}{l} n + r \\ k + r \end{array}\} {(z)}_{k}, n \geq 0.

Details about these special numbers can be found in Laissaoui and Rahmani [18] and references therein.

3. The main result

Theorem 3.1.

For all complex numbers x and y with x ≠ 1 we have

(3.1)

\sum_{k = 0}^{n} x^{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j}) = \frac{1}{1 - x} ({(1 + xy)}^{n} - x^{n + 1} {(1 + y)}^{n}) .

Proof.

We have the following chain of equalities:

0

\begin{array}{l} (1 - x) \sum_{k = 0}^{n} x^{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = 1 - x^{n + 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} + \sum_{k = 1}^{n - 1} (x^{k} - x^{k + 1}) \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} \\ = 1 + \sum_{k = 1}^{n} x^{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} - \sum_{j = 0}^{k - 1} (\begin{matrix} n \\ j \end{matrix}) y^{j}) - x^{n + 1} {(1 + y)}^{n} \\ = 1 + \sum_{k = 1}^{n} x^{k} (\begin{matrix} n \\ k \end{matrix}) y^{k} - x^{n + 1} {(1 + y)}^{n} \\ = {(1 + xy)}^{n} - x^{n + 1} {(1 + y)}^{n} . \end{array}

When x = 1, both sides equal 0. Assuming x ≠ 1 and dividing by 1 − x we complete the proof.

We proceed with two important observations dealing with variations of our main result. The first variation is based on an equivalent form of the incomplete binomial sum stated as Identity (1.9) by Gould in his book [14]

0

\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = \sum_{j = 0}^{k} (\begin{matrix} k - n \\ j \end{matrix}) {(1 + y)}^{k - j} {(- y)}^{j} .

It now follows that Theorem 3.1 can be restated as follows.

Theorem 3.2.

For all complex numbers x and y we have

0

\sum_{k = 0}^{n} x^{k} (\sum_{j = 0}^{k} (\begin{matrix} k - n \\ j \end{matrix}) {(1 + y)}^{k - j} {(- y)}^{j}) = \frac{1}{1 - x} ({(1 + xy)}^{n} - x^{n + 1} {(1 + y)}^{n}) .

The second variation is concerned with the trigonometric versions of Theorem 3.1. Replacing x with e^ix, $i = \sqrt{- 1}$ , using that

0

\frac{1}{1 - e^{ix}} = \frac{1}{2} (1 + i cot (\frac{x}{2})),

and comparing the real and imaginary parts we get the trigonometric variants.

Theorem 3.3.

For all complex numbers x and y such that x ∉ 2πℤ we have

0

\begin{array}{l} \sum_{k = 0}^{n} cos (kx) \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} & = \frac{1}{2} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} (cos (kx) - sin (kx) cot (x / 2)) \\ - {(1 + y)}^{n} (cos ((n + 1) x) - sin ((n + 1) x) cot (x / 2))), \end{array}

and

0

\begin{array}{l} \sum_{k = 0}^{n} sin (kx) \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} & = \frac{1}{2} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} (sin (kx) + cos (kx) cot (x / 2)) \\ - {(1 + y)}^{n} (sin ((n + 1) x) + cos ((n + 1) x) cot (x / 2))) . \end{array}

Now we state some results that can be drawn from the main result (3.1).

Corollary 3.4.

With x and y being complex numbers we have the following identities:

(3.2)

\sum_{k = 0}^{n} x^{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix})) = \frac{1}{1 - x} ({(1 + x)}^{n} - 2^{n} x^{n + 1}),

(3.3)

\sum_{k = 0}^{n} x^{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j}) = {(1 - x)}^{n - 1},

(3.4)

\sum_{k = 0}^{n} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j}) = n {(1 + y)}^{n - 1} + {(1 + y)}^{n},

(3.5)

\begin{matrix} \sum_{k = 0}^{n} {(- 1)}^{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j}) = \frac{1}{2} ({(1 - y)}^{n} + {(- 1)}^{n} {(1 + y)}^{n}), \\ \sum_{k = 0}^{n} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) x^{k - j}) = \frac{1}{1 - x} (2^{n} - x {(1 + x)}^{n}), \end{matrix}

(3.6)

\sum_{k = 0}^{n} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} y^{n + j - k}) = {(1 - y)}^{n - 1} .

Proof.

These are special cases of (3.1). Set y = 1 and y = −1 to get (3.2) and (3.3), respectively. Identity (3.4) is obtained from (3.1) by taking the limit x → 1 and using l'Hospital's rule. The remaining three follow by setting x = −1, y = 1/x, and x = −1/y in (3.1), respectively.

Remark 3.1.

Identity (3.3) is seen to be true by noting that

(3.7)

\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} = {(- 1)}^{k} (\begin{matrix} n - 1 \\ k \end{matrix}),

which is Equation (5.16) in [15] or Equation (39) in [27]. This immediately yields

0

\sum_{k = 0}^{n} x^{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j}) = \sum_{k = 0}^{n} (\begin{matrix} n - 1 \\ k \end{matrix}) {(- 1)}^{k} x^{k} = {(1 - x)}^{n - 1} .

Corollary 3.5.

With x and y being complex numbers we have the following relations

(3.8)

\sum_{k = 1}^{n} x^{k} (\sum_{j = 1}^{k} (\begin{matrix} n \\ j \end{matrix}) \frac{y^{j}}{j}) = \frac{1}{1 - x} \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \frac{y^{k}}{k} (x^{k} - x^{n + 1})

or equivalently

0

\sum_{k = 1}^{n} x^{k} (\sum_{j = 1}^{n} (\begin{matrix} n \\ j \end{matrix}) \frac{y^{j}}{j}) = \frac{1}{1 - x} \sum_{k = 1}^{n} \frac{{(1 + xy)}^{k} - x^{n + 1} {(1 + y)}^{k}}{k} - H_{n} \frac{1 - x^{n + 1}}{1 - x},

where H_n is the nth harmonic number. In particular,

0

\sum_{k = 1}^{n} \sum_{j = 1}^{k} (\begin{matrix} n \\ j \end{matrix}) \frac{y^{j}}{j} = (n + 1) \sum_{k = 1}^{n} \frac{{(1 + y)}^{k}}{k} + 1 - {(1 + y)}^{n} - (n + 1) H_{n} .

Proof.

Divide (3.1) by y and write the result as

0

\begin{array}{l} \sum_{k = 0}^{n} \frac{x^{k}}{y} + \sum_{k = 1}^{n} x^{k} \sum_{j = 1}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j - 1} \\ = \frac{1}{1 - x} (\frac{1}{y} - \frac{x^{n + 1}}{y} + \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} y^{k - 1} - x^{n + 1} \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k - 1}) . \end{array}

Integrate with respect to y from 0 to z and change back the notation to y. This yields

0

\sum_{k = 0}^{n} x^{k} ln y + \sum_{k = 1}^{n} x^{k} \sum_{j = 1}^{k} (\begin{matrix} n \\ j \end{matrix}) \frac{y^{j}}{j} = ln y \frac{1 - x^{n + 1}}{1 - x} + \frac{1}{1 - x} \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \frac{y^{k}}{k} (x^{k} - x^{n + 1}) .

This completes the proof of the first identity. The second identity is obtained from the first by using [3, Prop. 1, Eq. (22)]

0

\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \frac{y^{k}}{k} = \sum_{k = 1}^{n} \frac{{(1 + y)}^{k}}{k} - H_{n}

and some simplifications. The particular case follows by taking the limit x → 1 and using l'Hospital's rule.

Two special double sums evaluations that we want to record are

0

\sum_{k = 1}^{n} \sum_{j = 1}^{k} (\begin{matrix} n \\ j \end{matrix}) \frac{1}{j} = (n + 1) \sum_{k = 1}^{n} \frac{2^{k}}{k} + 1 - 2^{n} - (n + 1) H_{n}

and

0

\sum_{k = 1}^{n} \sum_{j = 1}^{k} (\begin{matrix} n \\ j \end{matrix}) \frac{{(- 1)}^{j}}{j} = 1 - (n + 1) H_{n} .

Corollary 3.6.

With x and y being complex numbers we have the following identity

(3.9)

\sum_{k = 1}^{n} \frac{x^{k}}{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j}) = {(1 + y)}^{n} \sum_{m = 1}^{n} \frac{x^{m}}{m} - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} \sum_{m = 1}^{k - 1} \frac{x^{m}}{m} .

In particular,

(3.10)

\sum_{k = 1}^{n} \frac{1}{k} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j}) = H_{n} {(1 + y)}^{n} - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} H_{k - 1} .

Proof.

Divide (3.1) by x and write the result as

0

\frac{1}{x} + \sum_{k = 1}^{n} x^{k - 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = \frac{1}{x (1 - x)} + \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} \frac{x^{k - 1}}{1 - x} - \frac{x^{n}}{1 - x} {(1 + y)}^{n}

or equivalently

0

- \frac{1}{1 - x} + \sum_{k = 1}^{n} x^{k - 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} \frac{x^{k - 1}}{1 - x} - \frac{x^{n}}{1 - x} {(1 + y)}^{n} .

Integrate with respect to x from 0 to z using

0

\int_{0}^{z} \frac{x^{n}}{1 - x} dx = - \sum_{m = 1}^{n} \frac{z^{m}}{m} - ln 1 - z|, (n \geq 0) .

After changing back the notation to x this procedure yields

0

\begin{array}{l} ln 1 - x| + \sum_{k = 1}^{n} \frac{x^{k}}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} (\sum_{m = 1}^{k - 1} \frac{x^{m}}{m} + ln 1 - x|) \\ + {(1 + y)}^{n} (\sum_{m = 1}^{n} \frac{x^{m}}{m} + ln 1 - x|) = - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) y^{k} \sum_{m = 1}^{k - 1} \frac{x^{m}}{m} \\ - ln 1 - x| ({(1 + y)}^{n} - 1 + {(1 + y)}^{n} \sum_{m = 1}^{n} \frac{x^{m}}{m} + ln 1 - x| {(1 + y)}^{n} . \end{array}

The logarithmic terms cancel out and the proof is completed. The particular case follows by setting x = 1.

We record the evaluations

(3.11)

\sum_{k = 1}^{n} \frac{1}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) = 2^{n} H_{n} - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) H_{k - 1}

and

0

\sum_{k = 1}^{n} \frac{1}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} = \frac{1}{n} - H_{n} .

More basic identities can be derived from (3.1). Mimicking the results obtained above, we have the following.

Corollary 3.7.

With x and y being complex numbers we have the following relation

0

\sum_{k = 0}^{n} x^{k} (\sum_{j = 1}^{k} j (\begin{matrix} n \\ j \end{matrix}) y^{j}) = \frac{nxy}{1 - x} ({(1 + xy)}^{n - 1} - x^{n} {(1 + y)}^{n - 1}) .

In particular, the following sums hold:

0

\begin{array}{l} \sum_{k = 0}^{n} x^{k} (\sum_{j = 1}^{k} j (\begin{matrix} n \\ j \end{matrix})) = \frac{nx}{1 - x} ({(1 + x)}^{n - 1} - 2^{n - 1} x^{n}), \\ \sum_{k = 0}^{n} x^{k} (\sum_{j = 1}^{k} {(- 1)}^{j} j (\begin{matrix} n \\ j \end{matrix})) = - nx {(1 - x)}^{n - 2}, \end{array}

where in the last one identity it is assumed that n ≥ 2.

Proof.

Apply the operator $y \cdot \frac{d}{dy}$ to (3.1). Particular cases are y = 1 and y = −1, respectively.

Remark 3.2.

We note that the second particular identity can be obtained directly via two intermediate steps. First, we used the identity

0

\sum_{j = 1}^{k} {(- 1)}^{j} j (\begin{matrix} n \\ j \end{matrix}) = {(- 1)}^{k} n (\begin{matrix} n - 1 \\ k - 1 \end{matrix}),

which follows from (3.7) and

j (\begin{matrix} n \\ j \end{matrix}) = n (\begin{matrix} n - 1 \\ j - 1 \end{matrix})

. Second, we have

0

\sum_{k = 1}^{n - 1} {(- 1)}^{k} n (\begin{matrix} n - 2 \\ k - 1 \end{matrix}) x^{k} = - nx {(1 - x)}^{n - 2} .

It is clear that more identities are possible, as one can use similar substitutions or transformations as in Corollary 3.4.

4. Some consequences – sums involving Fibonacci numbers

We can obtain many new and interesting Fibonacci and also Gibonacci identities from Theorem 3.1. For example, we have the following.

Proposition 4.1.

If m and t are integers such that m ≠ 1, then

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(\frac{F_{m}}{F_{m - 1}})}^{j} F_{k + j + t - 1} = F_{m - 1}^{- n} F_{(m + 1) n + t + 1} - \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) {(\frac{F_{m}}{F_{m - 1}})}^{k} F_{2 k + t}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(\frac{F_{m}}{F_{m - 1}})}^{j} L_{k + j + t - 1} = F_{m - 1}^{- n} L_{(m + 1) n + t + 1} - \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) {(\frac{F_{m}}{F_{m - 1}})}^{k} L_{2 k + t} .

In particular,

0

\begin{matrix} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{k + j + t - 1} = F_{3 n + t + 1} - \begin{array}{l} 5^{n / 2} F_{n + t}, & if n is even, \\ 5^{(n - 1) / 2} L_{n + t}, & if n is odd, \end{array} \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{k + j + t - 1} = L_{3 n + t + 1} - \begin{array}{l} 5^{n / 2} L_{n + t}, & if n is even, \\ 5^{(n + 1) / 2} F_{n + t}, & if n is odd, \end{array} \end{matrix}

and

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} F_{k + j + t - 1} = {(- 1)}^{n + 1} (F_{n + t} - F_{t + 1}), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} L_{k + j + t - 1} = {(- 1)}^{n + 1} (L_{n + t} - L_{t + 1}) . \end{array}

Proof.

Set x = α and x = β, in turn, in (3.1) to get

(4.1)

\sum_{k = 0}^{n} α^{k - 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = α^{n + 1} {(1 + y)}^{n} - {(1 + α y)}^{n},

(4.2)

\sum_{k = 0}^{n} β^{k - 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = β^{n + 1} {(1 + y)}^{n} - {(1 + β y)}^{n} .

Now, work with the basic relations

0

α^{m} = α F_{m} + F_{m - 1} and β^{m} = β F_{m} + F_{m - 1} .

They yield together with

y = \frac{F_{m}}{F_{m - 1}} α

and

y = \frac{F_{m}}{F_{m - 1}} β

, in turn, the following

0

\begin{array}{l} \sum_{k = 0}^{n} α^{k - 1 + t} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(\frac{F_{m}}{F_{m - 1}})}^{j} α^{j} = F_{m - 1}^{- n} α^{(m + 1) n + t + 1} - α^{t} (1 + \frac{F_{m}}{F_{m - 1}} α^{2}), \\ \sum_{k = 0}^{n} β^{k - 1 + t} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(\frac{F_{m}}{F_{m - 1}})}^{j} β^{j} = F_{m - 1}^{- n} β^{(m + 1) n + t + 1} - β^{t} (1 + \frac{F_{m}}{F_{m - 1}} β^{2}) . \end{array}

The results follow by combining the above sums according to the Binet forms. The special cases correspond to m = 2 and m = −1, respectively. The Fibonacci sums on the right are elementary. They can be found, for instance, in [10] and [20].

Proposition 4.2.

If m and t are integers such that m ≠ 2, then

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{m - 2}^{- j} F_{2 k + mj + t + 1} = {(\frac{F_{m}}{F_{m - 2}})}^{n} F_{4 n + t + 2} - \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{m - 2}^{- k} F_{(m + 2) k + t}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{m - 2}^{- j} L_{2 k + mj + t + 1} = {(\frac{F_{m}}{F_{m - 2}})}^{n} L_{4 n + t + 2} - \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{m - 2}^{- k} L_{(m + 2) k + t} .

In particular,

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{2 k + j + t + 1} = F_{4 n + t + 2} - 2^{n} F_{2 n + t}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{2 k + j + t + 1} = L_{4 n + t + 2} - 2^{n} L_{2 n + t}, \end{array}

and

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} 3^{- j} F_{2 k - 2 j + t + 1} = 3^{- n} (F_{4 n + t + 2} - 2^{n} F), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} 3^{- j} L_{2 k - 2 j + t + 1} = 3^{- n} (L_{4 n + t + 2} - 2^{n} L_{t}) . \end{array}

Proof.

The proof is very similar to the previous proof. Set x = α² and x = β², in turn, in (3.1). Now, work with the less popular but also obvious relations

0

α^{m} = α^{2} F_{m} - F_{m - 2} and β^{m} = β^{2} F_{m} - F_{m - 2} .

We omit the rest as it is clear how to finish the proof. The special cases correspond to m = 1 and m = −2, respectively.

Working with x = α³ and x = β³ in (3.1) and making use of

0

1 - α^{3} = - 2 α and 1 - β^{3} = - 2 β

we get the next result without efforts.

Proposition 4.3.

If m and t are integers such that m ≠ 2, then

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{m - 2}^{- j} F_{3 k + mj + t + 1} = \frac{1}{2} {(\frac{F_{m}}{F_{m - 2}})}^{n} F_{5 n + t + 3} - \frac{1}{2} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{m - 2}^{- k} F_{(m + 3) k + t}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{m - 2}^{- j} L_{3 k + mj + t + 1} = \frac{1}{2} {(\frac{F_{m}}{F_{m - 2}})}^{n} L_{5 n + t + 3} - \frac{1}{2} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{m - 2}^{- k} L_{(m + 3) k + t},

of which

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{3 k + j + t + 1} = \frac{1}{2} (F_{5 n + t + 3} - 3^{n} F_{2 n + t})

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{3 k + j + t + 1} = \frac{1}{2} (L_{5 n + t + 3} - 3^{n} L_{2 n + t})

are special cases.

More sums of this nature are possible. We state two additional identities as showcases:

0

\begin{array}{l} \sum_{k = 0}^{n} {(- 1)}^{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{3 j + 3 k + t} = {(- 1)}^{n} (2^{n - 1} F_{5 n + t + 1} + 2^{2 n - 1} F_{3 n + t - 2}), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) F_{3 j + 3 k + t} = {(- 1)}^{n} (2^{n - 1} F_{4 n + t + 2} - 2^{2 n - 1} F_{3 n + t - 1}) . \end{array}

We can also derive slightly different but very general results involving four parameters. First, recall the following.

Lemma 4.4.

The following identities hold:

0

\begin{matrix} α^{4 m} + 1 = L_{2 m} α^{2 m}, α^{4 m + 2} - 1 = L_{2 m + 1} α^{2 m + 1}, \\ α^{4 m + 2} + 1 = F_{2 m + 1} (α^{2 m} + α^{2 m + 2}), \end{matrix}

and similar identities hold for β.

Proof.

The first and the second are direct consequences of the simple relation

(4.3)

{(- 1)}^{s} + α^{2 s} = α^{s} L_{s} .

For the third item, use α^u = F_uα + F_u−1 in combination with F_u + F_u+2 = L_u+1, F_uL_u = F_2u and F_u+1L_u = F_2u+1 + 1.

The next result is proved in [16].

Lemma 4.5.

For integers r and s we have

(4.4)

\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{2 sk + r} = \begin{array}{l} 5^{(n - 1) / 2} F_{s}^{n} L_{sn + r}, & if n is odd and s is odd, \\ 5^{n / 2} F_{s}^{n} F_{sn + r}, & if n is even and s is odd, \\ L_{s}^{n} F_{sn + r}, & if s is even, \end{array}

and

0

\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) L_{2 sk + r} = \begin{array}{l} 5^{(n + 1) / 2} F_{s}^{n} L_{sn + r}, & if n is odd and s is odd, \\ 5^{n / 2} F_{s}^{n} L_{sn + r}, & if n is even and s is odd, \\ L_{s}^{n} L_{sn + r}, & if s is even . \end{array}

Proposition 4.6.

If u, v and t are integers, then

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{(4 u + 2) k + (4 v + 2) j + t} = - \frac{L_{2 u + 2 v + 2}^{n}}{L_{2 u + 1}} F_{(2 u + 2 v + 2) n - (2 u + 1) + t} \\ + \frac{F_{2 v + 1}^{n}}{L_{2 u + 1}} \begin{array}{l} 5^{n / 2} F_{(4 u + 2 v + 3) n + 2 u + 1 + t}, & if n is even, \\ 5^{(n - 1) / 2} L_{(4 u + 2 v + 3) n + 2 u + 1 + t}, & if n is odd, \end{array} \end{array}

and

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{(4 u + 2) k + (4 v + 2) j + t} = - \frac{L_{2 u + 2 v + 2}^{n}}{L_{2 u + 1}} L_{(2 u + 2 v + 2) n - (2 u + 1) + t} \\ + \frac{F_{2 v + 1}^{n}}{L_{2 u + 1}} \begin{array}{l} 5^{n / 2} L_{(4 u + 2 v + 3) n + 2 u + 1 + t}, & if n is even, \\ 5^{(n + 1) / 2} F_{(4 u + 2 v + 3) n + 2 u + 1 + t}, & if n is odd, \end{array} \end{array}

In particular,

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{2 (k + j) + t} = - 3^{n} F_{2 n - 1 + t} + \begin{array}{l} 5^{n / 2} F_{3 n + 1 + t}, & if n is even, \\ 5^{(n - 1) / 2} L_{3 n + 1 + t}, & if n is odd, \end{array} \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{2 (k + j) + t} = - 3^{n} L_{2 n - 1 + t} + \begin{array}{l} 5^{n / 2} L_{3 n + 1 + t}, & if n is even, \\ 5^{(n + 1) / 2} F_{3 n + 1 + t}, & if n is odd, \end{array} \end{array}

and

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{6 (k + j) + t} = 2^{n - 2} (- 3^{2 n} F_{3 (2 n - 1) + t} + \begin{array}{l} 5^{n / 2} F_{3 (3 n + 1) + t}, & if n is even, \\ 5^{(n - 1) / 2} L_{3 (3 n + 1) + t}, & if n is odd, \end{array}), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{6 (k + j) + t} = 2^{n - 2} (- 3^{2 n} L_{3 (2 n - 1) + t} + \begin{array}{l} 5^{n / 2} L_{3 (n + 1) + t}, & if n is even, \\ 5^{(n + 1) / 2} F_{3 (3 n + 1) + t}, & if n is odd, \end{array}) . \end{array}

Proof.

Set x = α^4u+2 and y = α^4v+2 in (3.1). This gives

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) α^{4 uk + 4 vj + 2 k + 2 j} = \frac{1}{1 - α^{4 u + 2}} ({(1 + α^{4 u + 4 v + 4})}^{n} - {(α^{4 u + 2})}^{n + 1} {(1 + α^{4 v + 2})}^{n}) .

We now simplify using Lemma 4.4, which gives

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) α^{4 uk + 4 vj + 2 k + 2 j} = \frac{F_{2 v + 1}^{n}}{L_{2 u + 1}} \cdot \frac{{(α^{2 v} + α^{2 v + 2})}^{n}}{α^{2 u + 1}} α^{(4 u + 2) (n + 1)} - \frac{L_{2 u + 2 v + 2}^{n}}{L_{2 u + 1}} \cdot \frac{α^{2 un + 2 vn + 2 n}}{α^{2 u + 1}} .

Expressing

0

{(α^{2 v} + α^{2 v + 2})}^{n} = α^{2 vn} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) α^{2 k} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) α^{2 vn + 2 k}

yields the identity

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{2 u + 1} F_{k (4 u + 2) + j (4 v + 2) + t} \\ = F_{2 v + 1}^{n} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{n (4 u + 2 v + 2) + 2 k + 2 u + 1 + t} - L_{2 u + 2 v + 2}^{n} F_{n (2 u + 2 v + 2) - 2 u - 1 + t} . \end{array}

The final identity follows since we have

0

\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{An + B + 2 k} = \begin{array}{l} 5^{n / 2} F_{(A + 1) n + B}, & if n is even, \\ 5^{(n - 1) / 2} L_{(A + 1) n + B}, & if n is odd, \end{array}

which is a special case of (4.4).

Proposition 4.7.

If u, v and t are integers such that u is even and v is odd, then

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{v (2 k + 1) + 2 uj + t} \\ = \frac{L_{u}^{n}}{L_{v}} F_{(2 v + u) n + 2 v + t} - \frac{1}{L_{v}} \begin{array}{l} 5^{n / 2} F_{v + u}^{n} F_{(v + u) n + t}, & if n is even, \\ 5^{(n - 1) / 2} F_{v + u}^{n} L_{(v + u) n + t}, & if n is odd, \end{array} \end{array}

and

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{v (2 k + 1) + 2 uj + t} \\ = \frac{L_{u}^{n}}{L_{v}} L_{(2 v + u) n + 2 v + t} - \frac{1}{L_{v}} \begin{array}{l} 5^{n / 2} F_{v + u}^{n} L_{(v + u) n + t}, & if n is even, \\ 5^{(n + 1) / 2} F_{v + u}^{n} F_{(v + u) n + t}, & if n is odd . \end{array} \end{array}

Proof.

Let u be even and v be odd. Then substituting x = α^2v and y = α^2u into (3.1), and then using (4.3), we obtain

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) α^{v (2 k + 1) + 2 uj + t} = \frac{1}{L_{v}} (L_{u}^{n} α^{(2 v + u) n + 2 v + t} - α^{t} {(1 + α^{2 (v + u)})}^{n}) .

Similarly, with x = β^2v and y = β^2u

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) β^{v (2 k + 1) + 2 uj + t} = \frac{1}{L_{v}} (L_{u}^{n} β^{(2 v + u) n + 2 v + t} - β^{t} {(1 + β^{2 (v + u)})}^{n}) .

Upon combining according to the Binet form we end up with

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{v (2 k + 1) + 2 uj + t} = \frac{L_{u}^{n}}{L_{v}} F_{(2 v + u) n + 2 v + t} - \frac{1}{L_{v}} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) F_{2 (v + u) k + t}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{v (2 k + 1) + 2 uj + t} = \frac{L_{u}^{n}}{L_{v}} L_{(2 v + u) n + 2 v + t} - \frac{1}{L_{v}} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) L_{2 (v + u) k + t} . \end{array}

The final identities follow from Lemma 4.5 using the fact that v +u is odd.

Corollary 4.8.

The following identities hold:

0

\begin{array}{r} \sum_{k = 0}^{n} F_{2 k + 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) = 2^{n} F_{2 n + 2} - \begin{array}{l} 5^{n / 2} F_{n}, & if n is even, \\ 5^{(n - 1) / 2} L_{n}, & if n is odd, \end{array} \\ \sum_{k = 0}^{n} L_{2 k + 1} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) = 2^{n} L_{2 n + 2} - \begin{array}{l} 5^{n / 2} L_{n}, & if n is even, \\ 5^{(n + 1) / 2} F_{n}, & if n is odd, \end{array} \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{2 k + 1 + 4 j} = 3^{n} F_{4 n + 2} - \begin{array}{l} 5^{n / 2} 2^{n} F_{3 n}, & if n is even, \\ 5^{(n - 1) / 2} 2^{n} L_{3 n}, & if n is odd, \end{array} \end{array}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{2 k + 1 + 4 j} = 3^{n} L_{4 n + 2} - \begin{array}{l} 5^{n / 2} 2^{n} L_{3 n}, & if n is even, \\ 5^{(n + 1) / 2} 2^{n} F_{3 n}, & if n is odd . \end{array}

Proposition 4.9.

The following identities hold:

0

\begin{matrix} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) 2^{k} F_{j + t} = 2^{n + 1} F_{2 n + t} - F_{3 n + t}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) 2^{k} L_{j + t} = 2^{n + 1} L_{2 n + t} - L_{3 n + t}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) 2^{k} F_{2 j + t} = {(- 1)}^{n} (2^{n + 1} F_{n + t} - F_{3 n + t}), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) 2^{k} L_{2 j + t} = {(- 1)}^{n} (2^{n + 1} L_{n + t} - L_{3 n + t}) . \end{matrix}

Proof.

Apply (3.1) with x = 2 and y = α (y = −α², respectively) and use 1 + 2α = α³ (1 − 2α² = −α³, respectively). Then, in turn, do the same for β and combine using the Binet form.

We can make things a bit more general. Combining (4.1) and (4.2), we have the identity stated in Lemma 4.10. Throughout the remainder of this section, we assume that n ≥ r + s.

Lemma 4.10.

If n, r and s are non-negative integers, t is an integer and x and y are complex numbers, then

(4.5)

\begin{matrix} \sum_{k = 0}^{n} G_{k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) x^{n - j - s} y^{j - r} = G_{n + t + 2} {(x + y)}^{n - r - s} \\ - (A α^{t + r + 1} {(x + α y)}^{n - r - s} + B β^{t + r + 1} {(x + β y)}^{n - r - s}) . \end{matrix}

Proposition 4.11.

If n, r and s are non-negative integers and m and t are integers, then

(4.6)

\begin{array}{l} \sum_{k = 0}^{n} G_{k + t} \sum_{j = r}^{k} {(- 1)}^{j} (\begin{matrix} n - r - s \\ j - r \end{matrix}) F_{m + 1}^{n - j - s} F_{m}^{j - r} \\ = {(- 1)}^{m (n - r - s) - r + 1} G_{t + r + 1 - m (n - r - s)} + {(- 1)}^{r} F_{m - 1}^{n - r - s} G_{n + t + 2} . \end{array}

In particular,

(4.7)

\sum_{k = r}^{n} {(- 1)}^{k} (\begin{matrix} n - r - s \\ k - r \end{matrix}) G_{k + t} = {(- 1)}^{n - s} G_{t + 2 r + s - n}

and

0

\sum_{k = 0}^{n} G_{k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) = - G_{t + r + 1 + 2 (n - r - s)} + 2^{n - r - s} G_{n + t + 2} .

Proof.

Set x = F_m+1 and y = −F_m in (4.5) and use

0

F_{m + 1} - F_{m} α = β^{m} and F_{m + 1} - F_{m} β = α^{m} .

The particular cases are evaluations of (4.6) at m = 1 and m = −2, respectively. Note that, in obtaining (4.7), we used

0

\sum_{j = r}^{k} {(- 1)}^{j} (\begin{matrix} n - r - s \\ j - r \end{matrix}) = {(- 1)}^{k} (\begin{matrix} n - r - s - 1 \\ k - r \end{matrix}),

which is a consequence of the binomial theorem and of which (3.7) is a particular case.

Lemma 4.12.

If n, r and s are non-negative integers, t is an integer and x and y are complex numbers, then

(4.8)

\begin{array}{l} \sum_{k = 0}^{n} G_{2 k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) x^{n - j - s} y^{j - r} = G_{2 n + t + 1} {(x + y)}^{n - r - s} \\ - (A α^{t + 2 r - 1} {(x + α^{2} y)}^{n - r - s} + B β^{t + 2 r - 1} {(x + β^{2} y)}^{n - r - s}) . \end{array}

Proposition 4.13.

If n, r and s are non-negative integers and m and t are integers, then

0

\begin{array}{l} \sum_{k = 0}^{n} G_{2 k + t} \sum_{j = r}^{k} {(- 1)}^{j} (\begin{matrix} n - r - s \\ j - r \end{matrix}) F_{m + 2}^{n - j - s} F_{m}^{j - r} \\ = {(- 1)}^{m (n - r - s) + r - 1} G_{t + 2 r - 1 - m (n - r - s)} + {(- 1)}^{r} G_{2 n + t + 1} F_{m + 1}^{n - r - s} . \end{array}

In particular,

0

\sum_{k = r}^{n} {(- 1)}^{k} (\begin{matrix} n - r - s \\ k - r \end{matrix}) G_{2 k + t} = {(- 1)}^{n + s} G_{t + n - s + 1} .

Proof.

Set x = F_m+2 and y = −F_m in (4.8) and use

0

F_{m + 2} - F_{m} α^{2} = β^{m} and F_{m + 2} - F_{m} β = α^{m} .

Proposition 4.14.

If n, r and s are non-negative integers and t is an integer, then

0

\begin{array}{l} \sum_{k = 0}^{n} G_{2 k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) = 2^{n - r - s} G_{2 n + t + 1} \\ - \begin{array}{l} 5^{(n - r - s) / 2} G_{t + n + r - s - 1}, & if n + r + s is even, \\ 5^{(n - r - s - 1) / 2} (G_{t + n + r - s} + G_{t + n + r - s - 2}), & if n + r + s is odd . \end{array} \end{array}

Proof.

Set x = 1 = y in (4.8).

Setting x = α³ and x = β³, in turn, in (3.1) and combining according to the Binet formula gives the identity stated in Lemma 4.15.

Lemma 4.15.

If n, r and s are non-negative integers, t is an integer and x and y are complex numbers, then

(4.9)

\begin{array}{l} \sum_{k = 0}^{n} G_{3 k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) x^{n - j - s} y^{j - r} = \frac{1}{2} G_{3 n + t + 2} {(x + y)}^{n - r - s} \\ - \frac{1}{2} (A α^{t + 3 r - 1} {(x + α^{3} y)}^{n - r - s} + B β^{t + 3 r - 1} (x + β^{3} y)^{n - r - s}) . \end{array}

Proposition 4.16.

If n, r and s are non-negative integers and m and t are integers, then

0

\begin{array}{l} \sum_{k = 0}^{n} G_{3 k + t} \sum_{j = r}^{k} {(- 1)}^{j} (\begin{matrix} n - r - s \\ j - r \end{matrix}) F_{m + 3}^{n - j - s} F_{m}^{j - r} \\ = {(- 1)}^{m (n - r - s) - r + 1} 2^{n - r - s - 1} G_{t + 3 r - 1 - m (n - r - s)} \\ + {(- 1)}^{r} 2^{n - r - s - 1} F_{m + 1}^{n - r - s} G_{3 n + t + 2} . \end{array}

In particular,

0

\begin{matrix} \sum_{k = 0}^{n} G_{3 k + t} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) = 2^{n - 1} (G_{3 n + t + 2} - G_{2 n + t - 1}) \end{matrix}

0

\sum_{k = r}^{n} {(- 1)}^{k} (\begin{matrix} n - r - s \\ k - r \end{matrix}) G_{3 k + t} = {(- 1)}^{n - s} 2^{n - r - s} G_{t + 2 r + n - s},

and

0

\sum_{k = 0}^{n} G_{3 k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) = 2^{n - r - s - 1} (G_{3 n + t + 2} - G_{t + 2 (n - s) + r - 1}) .

Proof.

Set x = F_m+3 and y = −F_m in (4.9) and use

0

F_{m + 3} - F_{m} α^{3} = 2 β^{m} and F_{m + 3} - F_{m} β^{3} = 2 α^{m} .

Proposition 4.17.

If n, r and s are non-negative integers and t is an integer, then

0

\begin{array}{l} \sum_{k = 0}^{n} G_{3 k + t} \sum_{j = r}^{k} (\begin{matrix} n - r - s \\ j - r \end{matrix}) 2^{j} = 2^{r - 1} 3^{n - r - s} G_{3 n + t + 2} \\ - 2^{r - 1} \begin{array}{l} 5^{(n - r - s) / 2} G_{t + 3 (n - s) - 1}, & if n + r + s is even, \\ 5^{(n - r - s - 1) / 2} (G_{t + 3 (n - s)} + G_{t + 3 (n - s) - 2}), & if n + r + s is odd . \end{array} \end{array}

Proof.

Use x = 1 and y = 2 in (4.9) and use the fact that

0

1 + 2 α^{3} = α^{3} \sqrt{5} and 1 + 2 β^{3} = - β^{3} \sqrt{5} .

4.1. Results for m-step numbers

Recall that Fibonacci m-step numbers $F_{n}^{(m)}$ are defined via recurrence

0

F_{n}^{(m)} = F_{n - 1}^{(m)} + \dots + F_{n - m}^{(m)}

with initial values

F_{1}^{(m)} = 1

and

F_{j}^{(m)} = 0

for j = −m + 2, …, 0. We let

T_{n} = F_{n}^{(3)}

and

Q_{n} = F_{n}^{(4)}

denote the Tribonacci and the Tetranacci numbers. Similarly, we define the Lucas m-step numbers

L_{n}^{(m)}

via the same recurrence, but with different initial values

L_{0}^{(m)} = m

L_{1}^{(m)} = 1

and

L_{j}^{(m)} = 0

for j = −m + 2, …, −1. Both sequences admit Binet-type formulas: if (with slight abuse of notation) α₁, … , α_m are the roots of the characteristic equation

(4.10)

x^{m} = x^{m - 1} + \dots + 1,

then

0

L_{n}^{(m)} = α_{1}^{n} + \dots + α_{m}^{n} and F_{n}^{(m)} = \sum_{k = 1}^{n} \frac{α_{k}^{n + 1}}{\prod_{j \neq k} (α_{k} - α_{j})} .

Lemma 4.18.

Fix m > 2. If λ denotes any root of the characteristic equation (4.10), then λ^m+1 + 1 = 2λ^m and 1 − λ^m+1 = 2λ^m(1 − λ).

Proof.

Simple use of the characteristic equation.

With the lemma in mind, we can formulate several simple consequences.

Corollary 4.19.

The following identities hold:

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{(m + 1) j + t}^{(m)} = n 2^{n - 1} F_{m (n - 1) + t}^{(m)} + 2^{n} F_{mn + t}^{(m)}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{(m + 1) j + t}^{(m)} = n 2^{n - 1} L_{m (n - 1) + t}^{(m)} + 2^{n} L_{mn + t}^{(m)} .

Proof.

Set y = λ^m+1 in (3.4). This gives, with help of Lemma 4.18,

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) λ^{(m + 1) j} = n 2^{n - 1} λ^{m (n - 1)} + 2^{n} λ^{mn} .

Multiply by λ^t and use the Binet formula.

In a similar fashion, we have the next result.

Corollary 4.20.

The following identities hold:

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{k} (\begin{matrix} n \\ j \end{matrix}) F_{(m + 1) j + t}^{(m)} = \frac{1}{2} (\sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) F_{(m + 1) k + t}^{(m)} + {(- 2)}^{n} F_{mn + t}^{(m)}), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{k} (\begin{matrix} n \\ j \end{matrix}) L_{(m + 1) j + t}^{(m)} = \frac{1}{2} (\sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) L_{(m + 1) k + t}^{(m)} + {(- 2)}^{n} L_{mn + t}^{(m)}) . \end{array}

Proof.

Set y = −λ^m+1 and proceed as in the previous result.

We note particular cases of the results (set m = 3 and m = 4):

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) T_{4 j + t} = n 2^{n - 1} T_{3 (n - 1) + t} + 2^{n} T_{3 n + t}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) Q_{5 j + t} = n 2^{n - 1} Q_{4 (n - 1) + t} + 2^{n} Q_{4 n + t}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{k} (\begin{matrix} n \\ j \end{matrix}) T_{4 j + t} = \frac{1}{2} (\sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) T_{4 k + t} + {(- 2)}^{n} T_{3 n + t}), \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{k} (\begin{matrix} n \\ j \end{matrix}) Q_{5 j + t} = \frac{1}{2} (\sum_{k = 0}^{n} {(- 1)}^{k} (\begin{matrix} n \\ k \end{matrix}) Q_{5 k + t} + {(- 2)}^{n} Q_{4 n + t}) . \end{array}

5. Consequences – identities with harmonic numbers

We employ the technique described in [2] to change the polynomial identity into an identity with harmonic numbers.

Proposition 5.1.

Let r, s ∈ ℂ \ ℤ⁻ be such that s ≠ 0 and r − s ∉ ℤ⁻. Then the following identities hold:

(5.1)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} \frac{(_{j}^{n})}{(j + s) ({j + s}_{j + r})} = \frac{n}{s (\begin{matrix} n + r - 1 \\ s \end{matrix})} + \frac{1}{s (\begin{matrix} n + r \\ s \end{matrix})},

(5.2)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{k} \frac{(_{j}^{n})}{(j + s) (_{j + s}^{j + r})} = \frac{1}{2 s (\begin{matrix} n + r \\ s \end{matrix})} + \frac{1}{2} {(- 1)}^{n} \sum_{k = 0}^{n} \frac{(_{k}^{n})}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} .

Furthermore, we also have

(5.3)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} \frac{H_{r - s} - H_{j + r}}{(j + s) (_{j + s}^{j + r})} = \frac{n}{s} \cdot \frac{H_{n - 1 + r - s} - H_{n - 1 + r}}{(\begin{matrix} n - 1 + r \\ s \end{matrix})} + \frac{H_{n + r - s} - H_{n + r}}{s (\begin{matrix} n + r \\ s \end{matrix})},

(5.4)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{k} \frac{H_{r - s} - H_{j + r}}{(j + s) (_{j + s}^{j + r})} = \frac{H_{n + r - s} - H_{n + r}}{2 s (\begin{matrix} n + r \\ s \end{matrix})} + \frac{1}{2} {(- 1)}^{n} \sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) (H_{r - s} - H_{k + r})}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} .

Proof.

First, we prove (5.1). Replace y with −y in (3.4) and multiply the result by (1 − y)^ry^s−1. Now, integrate from 0 to 1 with respect to y to obtain

0

\begin{array}{l} \int_{0}^{1} \sum_{k = 0}^{n} (\sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{j} {(1 - y)}^{r} y^{j + s - 1}) dy) \\ = n \int_{0}^{1} {(1 - y)}^{n - 1 + r} y^{s - 1} dy + \int_{0}^{1} {(1 - y)}^{n + r} y^{s - 1} dy . \end{array}

We now use the following representation of the Beta integral:

0

\int_{0}^{1} x^{u} {(1 - x)}^{v} dx = \frac{1}{(u + 1) (\begin{matrix} u + v + 1 \\ u + 1 \end{matrix})},

which is valid for ℜ(u) > −1 and ℜ(v) > −1. This gives, after substitution r ↦ r − s, the sum (5.1). To obtain (5.3), differentiate the former with respect to r.

For (5.2) and (5.4) we use (3.5) and the following evaluation:

0

\begin{array}{l} \int_{0}^{1} {(1 - x)}^{r} x^{s - 1} {(1 + x)}^{n} dx & = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) \int_{0}^{1} {(1 - x)}^{r} x^{k + s - 1} dx \\ = \sum_{k = 0}^{n} \frac{(_{k}^{n})}{(k + s) (^{k + s + r} k + s)} . \end{array}

Corollary 5.2.

The following identities hold:

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} \frac{(\begin{matrix} n \\ j \end{matrix})}{j + 1} = \frac{n + 2}{n + 1}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} \frac{(_{j}^{n}) H_{j + 1}}{j + 1} = \frac{1}{n} + \frac{1}{{(n + 1)}^{2}} .

Proof.

Set r = s = 1 in (5.1) and (5.3).

Corollary 5.3.

The following identities hold:

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{k} \frac{(\begin{matrix} n \\ j \end{matrix})}{j + 1} = \frac{1 + {(- 1)}^{n} (2^{n + 1} - 1)}{2 n + 2}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {(- 1)}^{k} \frac{H_{j + 1}}{j + 1} = \frac{1}{2 {(n + 1)}^{2}} + \frac{{(- 2)}^{n}}{n + 1} (H_{n + 1} - \sum_{k = 1}^{n + 1} \frac{1}{k 2^{k}}) .

Proof.

Set r = s = 1 in (5.2) and (5.4). Use the standard sum

0

\sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix})}{k + 1} = \frac{2^{n + 1} - 1}{n + 1}

and the identity

(5.5)

\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) H_{k} = 2^{n} (H_{n} - \sum_{k = 1}^{n} \frac{1}{k 2^{k}})

(see [5, 9]) in conjunction with

0

\sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) H_{k + 1}}{k + 1} = \frac{1}{n + 1} \sum_{k = 0}^{n + 1} (\begin{matrix} n + 1 \\ k \end{matrix}) H_{k} .

Remark 5.1.

Identity (3.11) can be simplified via (5.5) to the unusual identity

0

\sum_{k = 1}^{n} \frac{1}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) = \sum_{k = 1}^{n} \frac{2^{n - k} + (\begin{matrix} n \\ k \end{matrix})}{k} .

More identities with harmonic numbers are possible. For instance, we can start directly with (3.1) and perform computation similar to the one in the opening of this section. This can lead to the following.

Proposition 5.4.

For any complex y and any admissible r, s we have

(5.6)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(_{j}^{n})}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} y^{j} = \sum_{k = 0}^{n} \frac{(_{k}^{n})}{(k + s) (\begin{matrix} k + s - 1 \\ k + s \end{matrix})} y^{k} - \frac{{(1 + y)}^{n}}{(n + s + 1) (\begin{matrix} n + r \\ n + s + 1 \end{matrix})}

and

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(\begin{matrix} n \\ j \end{matrix}) (H_{r - s} - H_{k + r})}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} y^{j} \\ = \sum_{k = 0}^{0} \frac{(\begin{matrix} n \\ k \end{matrix}) (H_{r - 1 - s} - H_{k + r - 1})}{(k + s) (\begin{matrix} k + r - 1 \\ k + s \end{matrix})} y^{k} - \frac{{(1 + y)}^{n} (H_{r - s - 1} - H_{n + r})}{(n + s + 1) (\begin{matrix} n + r \\ n + s + 1 \end{matrix})} . \end{array}

Proof.

Start with (3.1) by expanding the right-hand side:

0

\sum_{k = 0}^{n} x^{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) y^{j} = \frac{1}{1 - x} \sum_{j = 0}^{k} (\begin{matrix} n \\ k \end{matrix}) x^{k} y^{k} - \frac{x^{n + 1}}{1 - x} {(1 + y)}^{n} .

Multiply that by (1 − x)^rx^s−1 and use the Beta integral formula.

Corollary 5.5.

The following identities hold:

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(_{j}^{n})}{(k + 1) (k + 2)} y^{j} = \frac{{(1 + y)}^{n + 1} - 1}{y (n + 1)} - \frac{{(1 + y)}^{n}}{n + 2}

and

(5.7)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(_{j}^{n}) (H_{k + 2} - 1)}{(k + 1) (k + 2)} y^{j} = \sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) H_{k + 1}}{k + 1} y^{k} - \frac{{(1 + y)}^{n} H_{n + 2}}{n + 2},

and in particular

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(_{j}^{n}) (H_{k + 2} - 1)}{(k + 1) (k + 2)} = \frac{2^{n + 1}}{n + 1} (H_{n + 1} - \sum_{k = 1}^{n + 1} \frac{1}{k 2^{k}}) - \frac{2^{n} H_{n + 2}}{n + 2} .

Proof.

Set r = 2 and s = 1 in Proposition 5.4. The particular case is y = 1.

Finally, we note that Proposition 5.4 can be used to generate a variety of identities with Fibonacci numbers as well. Below, we showcase some of the numerous possibilities.

Corollary 5.6.

The following identities hold:

0

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(\begin{matrix} n \\ j \end{matrix}) F_{j + t}}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} & = \sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) F_{k + t}}{(k + s) (\begin{matrix} k + r - 1 \\ k + s \end{matrix})} - \frac{F_{2 n + t}}{(n + s + 1) (\begin{matrix} n + r \\ n + s + 1 \end{matrix})}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(\begin{matrix} n \\ j \end{matrix}) F_{3 j + t}}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} & = \sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) F_{3 k + t}}{(k + s) (\begin{matrix} k + r - 1 \\ k + s \end{matrix})} - \frac{2^{n} F_{2 n + t}}{(n + s + 1) (\begin{matrix} n + r \\ n + s + 1 \end{matrix})}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(\begin{matrix} n \\ j \end{matrix}) F_{4 u j + t}}{(k + s) (\begin{matrix} k + r \\ k + s \end{matrix})} & = \sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) F_{4 u k + t}}{(k + s) (\begin{matrix} k + r - 1 \\ k + s \end{matrix})} - \frac{L_{2 u}^{n} F_{2 u n + t}}{(n + s + 1) (\begin{matrix} n + r \\ n + s + 1 \end{matrix})}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{(\begin{matrix} n \\ j \end{matrix}) (H_{k + 2} - 1) F_{j + t}}{(k + 1) (k + 2)} & = \sum_{k = 0}^{n} \frac{(\begin{matrix} n \\ k \end{matrix}) H_{k + 1} F_{k + t}}{k + 1} - \frac{F_{2 n + t} H_{n + 2}}{n + 2} . \end{array}

Proof.

Set, in turn, y = α, y = α³, y = α^4u in (5.6) and y = α in (5.7) (and similar substitutions with β).

6. Double sums evaluating to harmonic numbers

Lemma 6.1.

If r is a complex number that is not a negative integer, then

(6.1)

\int_{0}^{1} x^{r} ln (1 - x) dx = - \frac{H_{r + 1}}{r + 1},

(6.2)

\begin{array}{l} \int_{0}^{1} {(1 - x)}^{r} ln (1 - x) dx = - \frac{1}{{(1 + r)}^{2}}, \\ \int_{0}^{1} x^{r} {ln}^{2} (1 - x) dx = \frac{H_{r + 1}^{2} + H_{r + 1}^{(2)}}{r + 1}, \\ \int_{0}^{1} {(1 - x)}^{r} {ln}^{2} (1 - x) dx = \frac{2}{{(1 + r)}^{3}}, \\ \int_{0}^{1} x^{r} {ln}^{3} (1 - x) dx = - \frac{H_{r + 1}^{3} + 3 H_{r + 1} H_{r + 1}^{(2)} + 2 H_{r + 1}^{3}}{r + 1}, \end{array}

and

0

\int_{0}^{1} {(1 - x)}^{r} {ln}^{3} (1 - x) dx = - \frac{6}{{(1 + r)}^{4}} .

Proof.

These identities, some of which are well-known, are readily obtained by the repeated differentiation of the Beta function,

(6.3)

\int_{0}^{1} x^{u} {(1 - x)}^{v} dx = \frac{1}{(\begin{matrix} u + v + 1 \\ v + 1 \end{matrix}) (v + 1)}, ℜ u > - 1, ℜ v > - 1,

with respect to the parameters u and v.

Proposition 6.2.

If n is a non-negative integer, then

(6.4)

\begin{array}{l} \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n}{n + j - k + 1} = 1, n \neq 0, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n}{{(n + j - k + 1)}^{2}} = H_{n}, \\ \sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n}{{(n + j - k + 1)}^{3}} = \frac{1}{2} (H_{n}^{2} + H_{n}^{(2)}), \end{array}

and

(6.5)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n}{{(n + j - k + 1)}^{4}} = \frac{1}{6} (H_{n}^{3} + 3 H_{n} H_{n}^{(2)} + 2 H_{n}^{(3)}) .

Proof.

These results follow from multiplying both sides of (3.6) by ln^r(1 − x), r = 0, 1, 2, 3 and termwise integrating from 0 to 1, using Lemma 6.1.

Remark 6.1.

Identity (6.4) can be taken as a double-sum definition of harmonic numbers.

Remark 6.2.

There is a dual identity to each of identities (6.4)–(6.5). We leave their calculation to the reader.

Lemma 6.3.

If r is a complex number that is not a negative integer, then

(6.6)

\int_{0}^{1} x^{r} ({Li}_{2} (x) + ln x ln (1 - x)) dx = \frac{H_{r + 1}^{(2)}}{r + 1}

and

(6.7)

\int_{0}^{1} {(1 - x)}^{r} ({Li}_{2} (x) + ln x ln (1 - x)) dx = \frac{H_{r}}{{(r + 1)}^{2}} .

Proof.

The following integrals are known (see [4]):

0

\begin{matrix} \int_{0}^{1} x^{r} {Li}_{2} (x) dx = \frac{π^{2}}{6 (r + 1)} - \frac{H_{r + 1}}{{(r + 1)}^{2}}, \\ \int_{0}^{1} {(1 - x)}^{r} {Li}_{2} (x) dx = \frac{π^{2}}{6 (r + 1)} - \frac{H_{r + 1}^{(2)}}{r + 1}, \end{matrix}

and

0

\int_{0}^{1} x^{r} ln x ln (1 - x) dx = - \frac{π^{2}}{6 (r + 1)} + \frac{H_{r + 1}^{(2)}}{r + 1} + \frac{H_{r + 1}}{{(r + 1)}^{2}},

and hence (6.6) and (6.7).

Proposition 6.4.

If n is a non-negative integer, then

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (_{j}^{n}) n H_{n + j - k + 1}}{{(n + j - k + 1)}^{2}} = H_{n}^{(2)}

and

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n^{2} H_{n + j - k + 1}^{(2)}}{n + j - k + 1} = H_{n} .

Proof.

Multiply both sides of (3.6) by (Li₂(y) + ln y ln(1 − y)) and termwise integrate from 0 to 1 using (6.6) and (6.7).

Lemma 6.5.

If r is a non-negative integer, then

(6.8)

\int_{0}^{1} {(1 + x)}^{r} ln (1 + x) dx = \frac{1 - 2^{r + 1}}{{(r + 1)}^{2}} + \frac{2^{r + 1}}{r + 1} ln 2

and

(6.9)

\int_{0}^{1} x^{r} ln (1 + x) dx = \frac{1}{r + 1} \begin{array}{l} H_{r + 1} - H_{(r + 1) / 2}, & if r is odd, \\ H_{r + 1} - 2 O_{(r + 2) / 2} + 2 ln 2, & if r is even . \end{array}

Proof.

Identity (6.8) is obvious. A simple change of variable in (6.1) gives

0

\int_{0}^{1} x^{r} ln (1 + x) dx = \frac{H_{r + 1} - H_{(r + 1) / 2}}{r + 1}, r \in ℂ \ ℤ^{-},

of which (6.9) is a special case, since

0

H_{k + 1 / 2} = 2 O_{k + 1} - 2 ln 2.

Proposition 6.6.

If n is a non-negative integer, then

(6.10)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n 2^{j - k}}{{(n + j - k + 1)}^{2}} = 2^{- n} O_{n / 2⌉}

and

(6.11)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n 2^{j - k}}{n + j - k + 1} = \begin{array}{l} 0, & if n is even, \\ 2^{- n}, & if n is odd . \end{array}

Proof.

Write (3.6) as

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) {(1 + x)}^{n + j - k} = {(- 1)}^{n - 1} x^{n - 1}

and termwise integrate both sides from 0 to 1, using Lemma 6.5 to obtain

0

\begin{array}{r} \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) \frac{1 - 2^{n + j - k + 1}}{{(n + j - k + 1)}^{2}} + ln 2 \sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) \frac{2^{n + j - k + 1}}{n + j - k + 1} \\ = \frac{{(- 1)}^{n - 1}}{n} \begin{array}{l} H_{n} - H_{n / 2}, & if n is even, \\ H_{n} - 2 O_{(n + 1) / 2} + 2 ln 2, & if n is odd, \end{array} \end{array}

which upon equating the rational and irrational parts and simplifying gives (6.10) and (6.11).

Proposition 6.7.

If n is a non-negative integer, then

(6.12)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} \frac{{(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) n}{{(2 (n + j - k) + 1)}^{2}} = 2^{2 n - 1} \frac{O_{n}}{(\begin{matrix} 2 n \\ n \end{matrix})} .

Proof.

Set (3.6) up as

(6.13)

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) \int_{0}^{1} y^{2 (n + j - k)} ln y dy = \int_{0}^{1} {(1 - y^{2})}^{n - 1} ln y dy .

Upon differentiating (6.3) with respect to the parameter u, making a change of variable x = y² and using H_k−1/2 − H_−1/2 = 2O_k, it is not difficult to establish

0

\int_{0}^{1} dy {(1 - y^{2})}^{n - 1} ln y = - \frac{2^{2 n - 1}}{n} \frac{O_{n}}{(\begin{matrix} 2 n \\ n \end{matrix})},

while the integral on the left side of (6.13) is evaluated using (6.2).

Remark 6.3.

Identity (6.10) or (6.12) can be taken as a double-sum definition of odd harmonic numbers.

Remark 6.4.

The reader is invited to obtain the dual identity to (6.12).

7. Double sum identities involving Stirling numbers and r-Stirling numbers of the second kind

Lemma 7.1.

If k, r and v are non-negative integers, then

(7.1)

\begin{matrix} {\frac{d^{r}}{d x^{r}} {(1 - e^{x})}^{k}|}_{x = 0} = \sum_{p = 0}^{k} {(- 1)}^{p} (\begin{matrix} k \\ p \end{matrix}) p^{r} = {(- 1)}^{k} k! \begin{array}{l} r \\ k \end{array}\}, \\ {\frac{d^{r}}{d x^{r}} {(1 - e^{x})}^{k} e^{vx}|}_{x = 0} = \sum_{p = 0}^{k} {(- 1)}^{p} (\begin{matrix} k \\ p \end{matrix}) {(v + p)}^{r} = {(- 1)}^{k} k! {\begin{array}{l} r + v \\ k + v \end{array}\}}_{v} . \end{matrix}

Proof.

Since

0

{(1 - e^{x})}^{k} e^{vx} = \sum_{p = 0}^{k} {(- 1)}^{p} (\begin{matrix} k \\ p \end{matrix}) e^{(v + p) x},

we have

0

\frac{d^{r}}{d x^{r}} ({(1 - e^{x})}^{k} e^{vx}) = \sum_{p = 0}^{k} {(- 1)}^{p} (\begin{matrix} k \\ p \end{matrix}) {(v + p)}^{r} e^{(v + p) x},

and hence (7.1).

Proposition 7.2.

If m, n, r, and s are non-negative integers, then

(7.2)

\begin{array}{l} \sum_{k = 0}^{n} {(- 1)}^{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {\begin{matrix} m + s \\ n + j - k + r + s \end{matrix}\}}_{s} (n + j - k + r)! \\ = {(- 1)}^{n} r! {\begin{matrix} m + n + s - 1 \\ r + n + s + - 1 \end{matrix}\}}_{n + s - 1} . \end{array}

In particular,

(7.3)

\sum_{k = 0}^{n} {(- 1)}^{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{matrix} m \\ n + j - k \end{matrix}\} (n + j - k)! = {(- 1)}^{n} {(n - 1)}^{m} .

Proof.

Write (3.6) as

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) {(1 - y)}^{n + j - k + r} y^{s} = {(1 - y)}^{r} y^{n + s - 1},

write exp x for y, differentiate m times with respect to x and apply Lemma 7.1. Identity (7.3) is obtained by setting r = 0 = s in (7.2) and using the fact that

0

{\begin{matrix} m + n \\ n \end{matrix}\}}_{n} = n^{m} .

Proposition 7.3.

If m, r, s, u, and v are non-negative integers, then

0

\begin{array}{l} {\sum_{k = 1}^{n} {(- 1)}^{k} (k + u)! \begin{matrix} m + s \\ k + r + s \end{matrix}\}}_{s} \sum_{j = 1}^{k} {(- 1)}^{j + u} \frac{(_{j}^{n})}{j} {\begin{matrix} m + v \\ j + u + v \end{matrix}\}}_{v} (j + u)! \\ = \sum_{k = 1}^{n} {(- 1)}^{k} \frac{(\begin{matrix} n \\ k \end{matrix})}{k} (k + u)! {\begin{matrix} m + v \\ k + u + v \end{matrix}\}}_{v} {(- 1)}^{k + r} (k + r)! {\begin{array}{l} - m + s - 1 \\ k + r + s - 1 \end{array}\}}_{s - 1} \\ - {(- 1)}^{n + r + 1} (n + r + 1)! {\begin{array}{l} - m + s 1 \\ n + r + s \end{array}\}}_{s - 1}) . \end{array}

In particular,

0

\begin{array}{l} \sum_{k = 1}^{n} {(- 1)}^{k} k! \begin{matrix} m + 1 \\ k + 1 \end{matrix}\} \sum_{j = 1}^{k} \frac{{(- 1)}^{j}}{j} (\begin{matrix} n \\ j \end{matrix}) \begin{array}{l} m \\ j \end{array}\} j! \\ = \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} (\begin{matrix} n \\ k \end{matrix}) \begin{array}{l} m \\ k \end{array}\} k! ({(- 1)}^{k} k! \begin{array}{l} m \\ k \end{array}\} - {(- 1)}^{n + 1} (n + 1)! \begin{matrix} m \\ n + 1 \end{matrix}\}), \end{array}

with the special value

0

\sum_{k = 1}^{n} {(- 1)}^{k} k! \begin{matrix} n + 1 \\ k + 1 \end{matrix}\} \sum_{j = 1}^{k} \frac{{(- 1)}^{j}}{j} (\begin{matrix} n \\ j \end{matrix}) \begin{array}{l} n \\ j \end{array}\} j! = \sum_{k = 1}^{n} \frac{1}{k} (\begin{matrix} n \\ k \end{matrix}) \begin{array}{l} n \\ k \end{array}\} k!^{2} .

Proof.

Use (3.8) and proceed as in the proof of Proposition 7.2.

Proposition 7.4.

If m, r, s, u, and v are non-negative integers, then

0

\begin{array}{l} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} {\begin{matrix} m + s \\ k + r + s \end{matrix}\}}_{s} (k + r)! \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) {\begin{matrix} m + v \\ j + u + v \end{matrix}\}}_{v} (j + u)! \\ = u! {\begin{matrix} m + n + v \\ u + n + v \end{matrix}\}}_{n + v} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} {\begin{matrix} m + s \\ k + r + s \end{matrix}\}}_{s} (k + r)! \\ - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) {\begin{matrix} m + v \\ k + u + v \end{matrix}\}}_{v} (k + u)! \sum_{j = 1}^{k - 1} \frac{{(- 1)}^{j}}{j} {\begin{matrix} m + s \\ j + r + s \end{matrix}\}}_{s} (j + r)! . \end{array}

Proof.

Use (3.9) and proceed as in the proof of Proposition 7.2.

In particular,

0

\begin{array}{l} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{matrix} m \\ k + r \end{matrix}\} (k + r)! \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{matrix} m \\ j + u \end{matrix}\} (j + u)! \\ = u! {\begin{matrix} m + n \\ u + n \end{matrix}\}}_{n} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{matrix} m \\ k + r \end{matrix}\} (k + r)! \\ - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \begin{matrix} m + u \\ k + u \end{matrix}\} (k + u)! \sum_{j = 1}^{k - 1} \frac{{(- 1)}^{j}}{j} \begin{matrix} m \\ j + r \end{matrix}\} (j + r)! \end{array}

and

0

\begin{array}{l} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{matrix} m + 1 \\ k + r + 1 \end{matrix}\} (k + r)! \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{matrix} m + 1 \\ j + u + 1 \end{matrix}\} (j + u)! \\ = u! {\begin{matrix} m + n + 1 \\ u + n + 1 \end{matrix}\}}_{n + 1} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{matrix} m + 1 \\ k + r + 1 \end{matrix}\} (k + r)! \\ - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \begin{matrix} m + 1 \\ k + u + 1 \end{matrix}\} (k + u)! \sum_{j = 1}^{k - 1} \frac{{(- 1)}^{j}}{j} \begin{matrix} m + 1 \\ j + r + 1 \end{matrix}\} (j + r)!, \end{array}

with the special values

0

\begin{array}{l} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{array}{l} m \\ k \end{array}\} k! \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{array}{l} m \\ j \end{array}\} j! & = n^{m} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{array}{l} m \\ k \end{array}\} k! \\ - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \begin{array}{l} m \\ k \end{array}\} k! \sum_{j = 1}^{k - 1} \frac{{(- 1)}^{j}}{j} \begin{array}{l} m \\ j \end{array}\} j! \end{array}

and

0

\begin{array}{l} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{matrix} m + 1 \\ k + 1 \end{matrix}\} k! \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{matrix} m + 1 \\ j + 1 \end{matrix}\} j! = {(n + 1)}^{m} \sum_{k = 1}^{n} \frac{{(- 1)}^{k}}{k} \begin{matrix} m + 1 \\ k + 1 \end{matrix}\} k! \\ - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \begin{matrix} m + 1 \\ k + 1 \end{matrix}\} k! \sum_{j = 1}^{k - 1} \frac{{(- 1)}^{j}}{j} \begin{matrix} m + 1 \\ j + 1 \end{matrix}\} j! . \end{array}

Proposition 7.5.

If m, n, r, and s are non-negative integers, then

0

\begin{array}{l} \sum_{k = 1}^{n} \frac{1}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) (\begin{matrix} j + s \\ s \end{matrix}) {\begin{matrix} m + r \\ j + s + r \end{matrix}\}}_{r} j! = {\begin{matrix} m + r + n \\ s + r + n \end{matrix}\}}_{r + n} H_{n} \\ - \sum_{k = 1}^{m} (\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} k + s \\ s \end{matrix}) {\begin{matrix} m + r \\ k + s + r \end{matrix}\}}_{r} k! H_{k - 1} . \end{array}

In particular,

0

\sum_{k = 1}^{n} \frac{1}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{array}{l} m \\ j \end{array}\} j! = n^{m} H_{n} - \sum_{k = 1}^{m} (\begin{matrix} n \\ k \end{matrix}) \begin{array}{l} m \\ k \end{array}\} k! H_{k - 1},

with the special result

0

\sum_{k = 1}^{n} \frac{1}{k} \sum_{j = 0}^{k} (\begin{matrix} n \\ j \end{matrix}) \begin{array}{l} n \\ j \end{array}\} j! = n^{n} H_{n} - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) \begin{array}{l} n \\ k \end{array}\} k! H_{k - 1} .

Proof.

Use (3.10) and proceed as in the proof of Proposition 7.2.

Remark 7.1.

Obviously, many more identities involving Stirling numbers and r-Stirling numbers of the second kind can be derived from the various identities established above.

8. Concluding comments

In this paper, we have presented a completely elementary approach to binomial double sums with an incomplete inner sum. To highlight the broad applicability of the main results, we have stated a range of new double sum identities involving prominent sequences of numbers. It should not come as a surprise that the main identity and its derivatives can also be used to formulate identities involving polynomials, and even the Horadam sequence which contains many polynomial sequences as special cases (see the survey paper [19]; see also [22, Chapter 1] for the properties of the Lucas sequence). Recall that the Horadam sequence, (w_j)_j∈ℤ = (w_j(w₀, w₁; p, q)) is defined for all integers and arbitrary complex numbers w₀, w₁, p ≠ 0 and q ≠ 0, by the recurrence relation

0

w_{j} = p w_{j - 1} - q w_{j - 2}, j \geq 2,

with w_−j = (pw_−j+1 − w_−j+2)/q. Associated with (w_j) are the Lucas sequences of the first kind, u_j(p, q) = w_j(0, 1; p, q), and of the second kind, v_j(p, q) = w_j(2, p; p, q). Our ideas can be applied to w_j as well and this is showcased in the final two propositions.

Proposition 8.1.

If n is a non-negative integer and m, r and t are integers, then

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n \\ j \end{matrix}) (\begin{matrix} n + j - k \\ r \end{matrix}) v_{m}^{k - j} w_{t + m (n + j - k - r)} = {(- 1)}^{r} q^{m (n - r - 1)} v_{m} w_{t - m (n - r - 1)} .

Proposition 8.2.

If n is a non-negative integer and m, r and t are integers, then

0

\sum_{k = 0}^{n} \sum_{j = 0}^{k} {(- 1)}^{j} (\begin{matrix} n - r \\ j - r \end{matrix}) v_{m}^{n - j} w_{t + m (j - r)} = {(- 1)}^{r} ((n - r) v_{m} q^{m (n - r - 1)} w_{t - m (n - r - 1)} + q^{m (n - r)} w_{t - m (n - r)}) .

As another new field of application we will study the consequences of our main results to binomial transform pairs. The results of this study will be presented in an upcoming article.

Double Sums Involving Binomial Coefficients and Special Numbers

Full Article

1. Motivation

0

0

0

(1.1)

0

0

2. Preliminaries

0

0

0

0

0

0

0

0

0

0

0

0

0

3. The main result

Theorem 3.1.

(3.1)

Proof.

0

0

Theorem 3.2.

0

0

Theorem 3.3.

0

0

Corollary 3.4.

(3.2)

(3.3)

(3.4)

(3.5)

(3.6)

Proof.

Remark 3.1.

(3.7)

0

Corollary 3.5.

(3.8)

0

0

Proof.

0

0

0

0

0

Corollary 3.6.

(3.9)

(3.10)

Proof.

0

0

0

0

(3.11)

0

Corollary 3.7.

0

0

Proof.

Remark 3.2.

0

0

4. Some consequences – sums involving Fibonacci numbers

Proposition 4.1.

0

0

0

0

Proof.

(4.1)