Some Congruences for Central Binomial Sums Involving Fibonacci and Lucas Numbers

Roberto Tauraso Dipartimento di Matematica Università di Roma “Tor Vergata” 00133 Rome Italy

                    tauraso@mat.uniroma2.it

Abstract We present several polynomial congruences about sums with central binomial coefficients and harmonic numbers. In the final section we collect some new congruences involving Fibonacci and Lucas numbers.

1 Introduction

Recently, the following identity was proposed by Knuth in the problem section of the American Mathematical Monthly [3]:

(∑_{k=1}^{∞} \binom{2k}{k}\frac{x^{k}}{k} )^{2} = 4 ∑_{k=1}^{∞} \binom{2k}{k}(H_{2k−1} − H_{k})\frac{x^{k}}{k} ,  (1)

where H_{n} = ∑_{k=1}^{n} 1/k is the n-th harmonic number. Playing around with this formula, we realized that there is a corresponding polynomial congruence, namely, for all prime numbers p,

(∑_{k=1}^{p−1} \binom{2k}{k}\frac{x^{k}}{k} )^{2} ≡ 4 ∑_{k=1}^{p−1} \binom{2k}{k}(H_{2k−1} − H_{k})\frac{x^{k}}{k} (mod p).  (2)

By using this congruence together with some previous results given in [5, 6], we find that for all prime numbers p > 3,

∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{2k}x^{k}}{k} ≡ (2x − α)^{p}£_{2}(−β/α) + 2α^{p}£_{2}(β/α) (mod p)  (3)

where £_{2}(x) = ∑_{k=1}^{p−1} \frac{x^{k}}{k^{2}} is the finite dilogarithm and

α = \frac{1}{2} (1 + \sqrt{1 − 4x}) and β = \frac{1}{2} (1 − \sqrt{1 − 4x}) .

These kind of congruences have been actively investigated and many interesting formulas have been discovered (see the references in [5, 6]). For example, by letting x = 1 in (3), we recover the congruence

∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{2k}}{k} ≡ \frac{7}{12} (\frac{p}{3}) B_{p−2} (1/3) (mod p)  (4)

which appeared in [4], where (\frac{x}{y}) denotes the Legendre symbol, and B_{n}(x) is the n-th Bernoulli polynomial. Moreover, we show several congruences involving Fibonacci numbers F_{n} and Lucas numbers L_{n}. Two of them are as follows: for all prime numbers p > 5,

∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{2k}F_{3k} ≡ \frac{13}{10} (\frac{p}{5}) q_{L}^{2} (mod p),  (5)

∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{2k}L_{3k} ≡ \frac{5}{2} q_{L}^{2} (mod p),  (6)

where q_{L} = (L_{p} − 1)/p is the so-called Lucas quotient.

The paper is organized into four sections. The next section is devoted to a brief introduction to the finite polylogarithm. In Section 3 we present the proofs of the main theorems about the polynomial congruences and in the final section we establish various congruences involving Fibonacci numbers.

2 The finite polylogarithm

The classical polylogarithm function is defined for complex |z| < 1 and all positive integers d by the power series

Li_{d}(z) = ∑_{k=1}^{∞} \frac{z^{k}}{k^{d}} .

It is well known that the polylogarithm can be extended analytically to a wider range of z and it satisfies several remarkable identities such as the two reflection properties,

Li_{2}(z) + Li_{2}(1/z) = −\frac{π^{2}}{6} − \frac{ln^{2}(−z)}{2} and Li_{2}(z) + Li_{2}(1 − z) = \frac{π^{2}}{6} − ln(z) ln(1 − z).

These identities allow the explicit evaluation of the polylogarithm at some special values, such as

Li_{2}(1) = ζ(2) = \frac{π^{2}}{6} , Li_{2}(1/2) = \frac{π^{2}}{12} − \frac{ln^{2}(2)}{2}, Li_{2}(ϕ_{−}) = −\frac{π^{2}}{15} + \frac{ln^{2}(ϕ_{+})}{2}.

where ϕ_{±} = (1 ± \sqrt{5})/2.

The finite polylogarithm function is the partial sum of the above series over the range 0 < k < p where p is a prime

£_{d}(x) = ∑_{k=1}^{p−1} \frac{x^{k}}{k^{d}} .

It satisfies some nice properties that resemble the ones satisfied by the classical polylogarithm.

Here we restrict our attention to £_{2}(x) (see [5] for more details): for all prime numbers p > 3,

£_{2}(x) ≡ x^{p}£_{2}(1/x) (mod p),
£_{1}(1 − x) ≡ −Q_{p}(x) − p£_{2}(x) (mod p^{2}),
£_{2}(x) ≡ £_{2}(1 − x) + x^{p}£_{2}(1 − 1/x) (mod p),
x^{p}£_{2}(x) + (1 − x)^{p}£_{2}(1 − x) ≡ \frac{1}{2} Q_{p}^{2}(x) (mod p).

where

Q_{p}(x) = xq_{p}(x) + (1 − x)q_{p}(1 − x), with q_{p}(x) = \frac{x^{p−1} − 1}{p}.

Several congruences for special values of £_{2}(x) are known:

£_{2}(1) ≡ £_{2}(−1) ≡ 0, £_{2}(2) ≡ 2£_{2}(1/2) ≡ −q_{p}^{2}(2) (mod p).

Moreover

\begin{matrix}£_{2}((1±i)/2) ≡ −\frac{q_{p}^{2}(2)}{8} + \frac{1}{4} ((\frac{−1}{p}) ± i) E_{p−3} (mod p), \\ £_{2}(ω_{6}^{±1}) ≡ \frac{1}{8}((\frac{p}{3}) ± i\frac{\sqrt{3}}{3})B_{p−2}(1/3), (mod p) \end{matrix}

where ω_{6} = (1 ± i\sqrt{3})/2 and E_{n} is n-th Euler number. Finally, for all prime numbers p > 5 we have

£_{2}(ϕ_{±}) ≡ ∓\frac{\sqrt{5}}{10} (\frac{p}{5}) q_{L}^{2} (mod p),
£_{2}(ϕ_{±}^{2}) ≡ −\frac{1}{2}(1 ± \frac{\sqrt{5}}{5} (\frac{p}{5}))q_{L}^{2} (mod p),
£_{2}(−ϕ_{±}) ≡ −\frac{1}{4}(1 ± \frac{\sqrt{5}}{5} (\frac{p}{5}))q_{L}^{2} (mod p).

Notice that the Lucas quotient satisfies (see [7]),

q_{L} = Q(ϕ_{±}) ≡ \frac{5 F_{p−(\frac{p}{5})}}{2p} (mod p).

3 Polynomial congruences for central binomial sums

In [5, 6], we studied various sum involving the central binomial coefficients. In particular, it has been shown that for all prime numbers p > 3,

∑_{k=1}^{p−1} \binom{2k}{k}x^{k} ≡ ∑_{k=1}^{p−1} \binom{\frac{p−1}{2}}{k}(−4x)^{k} ≡ (1 − 4x)^{(p−1)/2} (mod p),  (7)

∑_{k=1}^{p−1} \binom{2k}{k}\frac{x^{k}}{k} ≡ £_{1}(α) + £_{1}(β) (mod p),  (8)

∑_{k=1}^{p−1} \binom{2k}{k}\frac{x^{k}}{k^{2}} ≡ 2£_{2}(α) + 2£_{2}(β) (mod p),  (9)

∑_{k=1}^{p−1} \binom{2k}{k}H_{k}^{(2)}x^{k} ≡ \frac{2(£_{2}(β) − £_{2}(α))}{\sqrt{1 − 4x}} (mod p).  (10)

where H_{n}^{(2)} = ∑_{k=1}^{n} 1/k^{2}.

In [1, Proposition 5], Boyadzhiev used the following Euler-type series transformation formula to handle series with central binomial coefficients: if a_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}b_{k} then in a neighborhood of x = 0,

∑_{k=0}^{∞} \binom{2k}{k}a_{k}x^{k} = \frac{1}{\sqrt{1 − 4x}} ∑_{j=0}^{∞} \binom{2j}{j}b_{j} (\frac{−x}{1 − 4x})^{j} .

It turns out that something similar holds for finite sum congruences:

∑_{k=0}^{p−1} \binom{2k}{k}a_{k}x^{k} ≡ ∑_{k=0}^{(p−1)/2} \binom{\frac{p−1}{2}}{k}a_{k}(−4x)^{k} = ∑_{k=0}^{(p−1)/2} \binom{\frac{p−1}{2}}{k}(−4x)^{k} ∑_{j=0}^{k} \binom{k}{j}(−1)^{j}b_{j}

= ∑_{j=0}^{(p−1)/2}(−1)^{j}b_{j} ∑_{k=j}^{(p−1)/2} \binom{\frac{p−1}{2}}{k}\binom{k}{j}(−4x)^{k}

= ∑_{j=0}^{(p−1)/2}(−1)^{j}b_{j}\binom{\frac{p−1}{2}}{j}(−4x)^{j}(1 − 4x)^{\frac{p−1}{2} −j}

≡ (1 − 4x)^{\frac{p−1}{2}} ∑_{j=0}^{p−1} \binom{2j}{j}b_{j} (\frac{−x}{1 − 4x})^{j} (mod p).  (11)

In the next theorem we apply the above transformation. Theorem 1. For all prime numbers p > 3,

∑_{k=1}^{p−1} \binom{2k}{k}H_{k}x^{k} ≡ −2(1 − 4x)^{\frac{p−1}{2}} £_{1} (−\frac{β}{\sqrt{1 − 4x}}) (mod p),  (12)
∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{k}x^{k}}{k} ≡ 2(1 − 4x)^{\frac{p}{2}} (£_{2} (\frac{α}{\sqrt{1 − 4x}}) − £_{2} (−\frac{β}{\sqrt{1 − 4x}})) (mod p). (13)

Proof. It is easy to verify by induction that

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

Moreover

α (\frac{−x}{1 − 4x}) = \frac{α}{\sqrt{1 − 4x}} and β (\frac{−x}{1 − 4x}) = −\frac{β}{\sqrt{1 − 4x}}.

Hence, by (11) and (8),

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

≡ −(1 − 4x)^{\frac{p−1}{2}} (£_{1} (\frac{α}{\sqrt{1 − 4x}}) + £_{1} (−\frac{β}{\sqrt{1 − 4x}}))

≡ −(1 − 4x)^{\frac{p−1}{2}} (£_{1} (1 − \frac{α}{\sqrt{1 − 4x}}) + £_{1} (−\frac{β}{\sqrt{1 − 4x}}))

≡ −2(1 − 4x)^{\frac{p−1}{2}} £_{1} (−\frac{β}{\sqrt{1 − 4x}}) (mod p),

where we also used £_{1}(x) ≡ £_{1}(1 − x). Thus the proof of (12) is complete.

As regards (13), Eqns. (11) and (10) imply

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

≡ 2(1 − 4x)^{\frac{p}{2}} (£_{2} (\frac{α}{\sqrt{1 − 4x}}) − £_{2} (−\frac{β}{\sqrt{1 − 4x}})) (mod p).

In the next theorem, we establish (2), the analogous congruence for the series (1).

Theorem 2. For all prime numbers p > 3,

(∑_{k=1}^{p−1} \binom{2k}{k}x^{k}) · (∑_{k=1}^{p−1} \binom{2k}{k}\frac{x^{k}}{k} ) ≡ 2 ∑_{k=1}^{p−1} \binom{2k}{k}(H_{2k−1} − H_{k})x^{k} (mod p), (14)

(∑_{k=1}^{p−1} \binom{2k}{k}\frac{x^{k}}{k} )^{2} ≡ 4 ∑_{k=1}^{p−1} \binom{2k}{k}(H_{2k−1} − H_{k})\frac{x^{k}}{k} (mod p).  (15)

Proof. Since p divides \binom{2k}{k} for (p − 1)/2 < k < p, it follows that

(∑_{k=1}^{p−1} \binom{2k}{k}x^{k}) · (∑_{k=1}^{p−1} \binom{2k}{k}\frac{x^{k}}{k} ) ≡ ∑_{n=1}^{p−1} x^{n} ∑_{k=1}^{n−1} (\frac{1}{k}\binom{2k}{k}\binom{2(n − k)}{n − k}) (mod p).

In a similar way,

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

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

≡ 2 ∑_{n=1}^{p−1} \frac{x^{n}}{n} ∑_{k=1}^{n−1} (\frac{1}{k}\binom{2k}{k}\binom{2(n − k)}{n − k}) (mod p).

Therefore, it suffices to show by induction that

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

It holds for n = 1, and it is straightforward to verify that

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) with G(n, k) = −\frac{k^{2}(2n − 2k + 1)F (n, k)}{(n + 1)(2n + 1)(n + 1 − k)}.

Hence, by the inductive assumption,

∑_{k=1}^{n} F (n + 1, k) = ∑_{k=1}^{n} F (n, k) + ∑_{k=1}^{n}(G(n, k + 1) − G(n, k))

= 2(H_{2n−1} − H_{n}) + F (n, n) + G(n, n + 1) − G(n, 1)

= 2(H_{2n−1} − H_{n}) + \frac{1}{n} + 0 + \frac{(2n − 1)F (n, 1)}{(n + 1)(2n + 1)n}

= 2(H_{2n−1} − H_{n}) + \frac{1}{n} + \frac{1}{(n + 1)(2n + 1)} = 2(H_{2n+1} − H_{n+1}).

Now we are ready to show that our main result (3) and the congruence corresponding to the series [2, Theorem 6]: for |x| < 1/4,

∑_{k=1}^{∞} \binom{2k}{k}H_{2k}x^{k} = \frac{1}{\sqrt{1 − 4x}} (ln (\frac{1 + \sqrt{1 − 4x}}{2}) − 2 ln(\sqrt{1 − 4x})) .  (16)

Theorem 3. For all prime numbers p > 3,

∑_{k=1}^{p−1} \binom{2k}{k}H_{2k}x^{k} ≡ (1 − 4x)^{(p−1)/2} (£_{1}(β) − 2£_{1} (−\frac{β}{\sqrt{1 − 4x}})) (mod p) (17)

∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{2k}x^{k}}{k} ≡ (2x − α)^{p}£_{2}(−β/α) + 2α^{p}£_{2}(β/α) (mod p).  (18)

Proof. As regards (17), since H_{2k} = \frac{1}{2k} + (H_{2k−1} − H_{k}) + H_{k}, it follows immediately that,

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

and we apply (7), (14), and (12). In a similar way, for (18),

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

and then we use (9), (15), and (13).

As a remark, we point out that although the series (16) does not converge for x = 1/4, by letting f(x) be the left-hand side of (16) then

∑_{k=1}^{∞} \binom{2k}{k}\frac{H_{2k}}{4^{k}k} = ∫0^{\frac{1}{4}} \frac{f(x)}{x} dx = \frac{5π^{2}}{12} .

On the other hand, it can be verified that the congruence (18) holds even for x = 1/4, and for all prime numbers p > 3,

∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{2k}}{4^{k}k} ≡ £_{2}(1) ≡ 0 (mod p).

4 Congruences with Fibonacci and Lucas numbers

By looking at this table and by using the values of £_{1} and £_{2}, we can easily obtain the explicit values of the congruences established in the previous section.

\begin{matrix}x & α & β \\ 1 & ω_{6} & ω_{6}^{−1} \\ −1 & ϕ_{+} & ϕ_{−} \\ −2 & 2 & −1 \\ 1/2 & (1 + i)/2 & (1 − i)/2 \\ 1/3 & (1 + ω_{6})/3 & (1 + ω_{6}^{−1})/3 \\ 1 + i & 1 − i & i \\ 1 − i & 1 + i & −i \\ ±i\sqrt{3} & 1 + ω_{6}^{∓1} & −ω_{6}^{∓1} \\ −ϕ_{−}^{3} & −ϕ_{−} & ϕ_{−}^{2} \\ −ϕ_{+}^{3} & ϕ_{+}^{2} & −ϕ_{+} \end{matrix}

For example, for all prime numbers p > 3, by taking x = 1, 1/2, 1/3 in (18), we get respectively (4), and the next two congruences,

\begin{matrix}∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{2k}}{2^{k}k} ≡ \frac{3}{16} (\frac{−1}{p}) B_{p−2} (1/4) (mod p), \\ ∑_{k=1}^{p−1} \binom{2k}{k}\frac{H_{2k}}{3^{k}k} ≡ \frac{2}{9} (\frac{p}{3}) B_{p−2} (1/3) (mod p). \end{matrix}

To order to get the congruences with F_{n} and L_{n} we need consider the cases x = −ϕ_{±}^{3}. If x = −ϕ_{−}^{3} then 2x − α = −ϕ_{−}^{4} and

∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{2k}ϕ_{−}^{3k} ≡ (−ϕ_{−}^{4})^{p}£_{2}(ϕ_{−}) + 2(−ϕ_{−})^{p}£_{2}(−ϕ_{−})

≡ \frac{1}{2} (−7 + 3 (\frac{p}{5}) \sqrt{5}) £_{2}(ϕ_{−}) + (−1 + (\frac{p}{5}) \sqrt{5}) £_{2}(−ϕ_{−})

≡ (\frac{5}{4} − \frac{13}{20} (\frac{p}{5}) \sqrt{5}) q_{L}^{2} (mod p).

where we used the fact that 2ϕ_{±}^{p} ≡ 1 ± (\frac{p}{5}) \sqrt{5} (mod p). In a similar way, we find that

∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{2k}ϕ_{±}^{3k} ≡ (\frac{5}{4} ± \frac{13}{20} (\frac{p}{5}) \sqrt{5}) q_{L}^{2} (mod p),

∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{k}ϕ_{±}^{3k} ≡ (\frac{1}{2} ± \frac{3}{10} (\frac{p}{5}) \sqrt{5}) q_{L}^{2} (mod p).

Since \sqrt{5}F_{3k} = ϕ_{+}^{3k} − ϕ_{−}^{3k} and L_{3k} = ϕ_{+}^{3k} + ϕ_{−}^{3k}, it follows that for p > 5, (5) and (6) hold and also we find that

\begin{matrix}∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{k}F_{3k} ≡ \frac{3}{5} (\frac{p}{5}) q_{L}^{2} (mod p), \\ ∑_{k=1}^{p−1} \frac{(−1)^{k}}{k} \binom{2k}{k}H_{k}L_{3k} ≡ q_{L}^{2} (mod p). \end{matrix}

References

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

[2] H. Chen, Interesting series associated with central binomial coefficients, Catalan numbers and harmonic numbers, J. Integer Sequences 19 (2016), Article 16.1.5.

[3] D. E. Knuth, Problem 11832, Amer. Math. Monthly 122 (2015), 390.

[4] G.-S. Mao and Z.-W. Sun, Two congruences involving harmonic numbers with applications, Int. J. Number Theory 12 (2016), 527–539.

[5] S. Mattarei and R. Tauraso, Congruences for central binomial sums and finite polylogarithms, J. Number Theory 133 (2013), 131–157.

[6] S. Mattarei and R. Tauraso, From generating series to polynomial congruences, in preparation.

[7] H. C. Williams, A note on the Fibonacci quotient F_{p−ε}/p, Can. Math. Bull. 25 (1982), 366–370.

2010 Mathematics Subject Classification: Primary 11A07; Secondary 05A10.

Keywords: congruences, central binomial coefficient, harmonic number, Fibonacci number, Lucas number.

(Concerned with sequences \underline{A000045}, \underline{A000984}, \underline{A001008}, \underline{A014445}, and \underline{A014448}.) Received April 14 2016; revised version received May 10 2016. Published in Journal of Integer Sequences, June 2 2016. Return to Journal of Integer Sequences home page.