On Prime-Detecting Sequences From Apéry’s Recurrence Formulae for ζ(3) and ζ(2)

Carsten Elsner Fachhochschule für die Wirtschaft University of Applied Sciences Freundallee 15 D-30173 Hannover Germany

                carsten.elsner@fhdw.de

Abstract

We consider the linear three-term recurrence formula

X_{n} = (34(n − 1)^{3} + 51(n − 1)^{2} + 27(n − 1) + 5)X_{n−1} − (n − 1)^{6}X_{n−2} (n ≥ 2)

corresponding to Apéry’s non-regular continued fraction for ζ(3). It is shown that integer sequences (X_{n})_{n≥0} with 5X_{0} ≠ X_{1} satisfying the above relation are primedetecting, i.e., X_{n} ≢ 0 (mod n) if and only if n is a prime not dividing |5X_{0} − X_{1}|. Similar results are given for integer sequences satisfying the recurrence formula

X_{n} = (11(x − 1)^{2} + 11(x − 1) + 3)X_{n−1} + (n − 1)^{4}X_{n−2} (n ≥ 2)

corresponding to Apéry’s non-regular continued fraction for ζ(2) and for sequences related to log 2.

1 Introduction

In 1979, R. Apéry [1] proved the irrationality of ζ(3) = ∑_{n=1}^{∞} 1/n^{3}. The jumping-off point of his proof is a recurrence formula,

(n + 1)^{3}X_{n+1} − (34n^{3} + 51n^{2} + 27n + 5)X_{n} + n^{3}X_{n−1} = 0,  (1)

which is satisfied by X_{n} = a_{n} and X_{n} = b_{n} with

a_{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2},  b_{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2}c_{n,k},  (2)

where

c_{n,k} = ∑_{m=1}^{n} \frac{1}{m^{3}} + ∑_{m=1}^{k} \frac{(−1)^{m−1}}{2m^{3}\binom{n}{m}\binom{n + m}{m}}  (1 ≤ k ≤ n).  (3)

One basic fact for the irrationality proof of ζ(3) is the following inequality:

0 ≠ ζ(3) − \frac{b_{n}}{a_{n}} = O( (1 + \sqrt{2})^{−8n} ).

When n increases, b_{n}/a_{n} converges rapidly to ζ(3) so that one can conclude the irrationality of ζ(3). From (1), Apéry’s continued fraction expansion of ζ(3) can be derived, namely

ζ(3) = \frac{6}{5 − \frac{1^{6}}{117 − \frac{2^{6}}{535 − ... −\frac{n^{6}}{34n^{3} + 51n^{2} + 27n + 5 − ⋯}}}}  (4)

(see [4]). F. Beukers [2] proved the congruence

a_{((p−1)/2)} ≡ γ_{p} (mod p)

for all odd primes p, where the integers γ_{n} are given by the following series expansion of an infinite product:

∑_{n=1}^{∞} γ_{n}q^{n} = q ∏_{n=1}^{∞} (1 − q^{2n})^{4}(1 − q^{4n})^{4}.

Note that (b_{n})_{n≥0} is a sequence of rationals. For the concept of prime-detecting sequences introduced below we shall need integer sequences. Therefore, we define

q_{0} = 1, q_{n} = (n!)^{3}a_{n} (n ≥ 1), p_{0} = 0, p_{n} = (n!)^{3}b_{n} (n ≥ 1),  (5)

so that the p_{n} are integers. It can be shown that both sequences, (q_{n})_{n≥0} and (p_{n})_{n≥0}, satisfy the recurrence formula

X_{n} = T (n)X_{n−1} − U(n)X_{n−2} (n ≥ 2),  (6)

where T (n) = 34(n − 1)^{3} + 51(n − 1)^{2} + 27(n − 1) + 5 and U(n) = (n − 1)^{6}. This requires some technical computations. Alternatively, for X_{n} = q_{n} one can verify (6) by application of the Zeilberger algorithm [6, Chapter 7, Algorithm 7.1] using a computer. The same algorithm works for X_{n} = a_{n} and (1) ([6, p. 101-102]), but not for p_{n} and b_{n}, respectively. We also have

\frac{p_{n}}{q_{n}} = \frac{b_{n}}{a_{n}} ⟶ ζ(3)

as n tends to infinity. Finally, computing p_{1} = 6 and q_{1} = 5 from (2) and (3), the continued fraction (4) follows from the formula (1) in [7, §§1, 2].

We let ℙ denote the set of prime numbers. There are several possibilities for suitable functions and sequences to detect primes. We give a short summary of various primedetecting methods in the concluding section 4 of this paper. Of course, Wilson’s theorem plays a significant role.

Proposition 1. For all integers n ∈ ℕ \ {4} we have

(n − 1)! ≢ 0 (mod n) ⟺ n ∈ ℙ.

Proof. For any prime n we know by Wilson’s criterion that (n − 1)! ≡ −1 (mod n). So it remains to prove (n − 1)! ≡ 0 (mod n) for any n = ab ≠ 1, 4 with integers 1 < a, b < n.

Case 1: a = b ≥ 3 . Since n = a^{2} and lcm(2, a, 2a, a^{2}) = lcm(2, a^{2}), we have

lcm (1, …, a − 1, a + 1, …, 2a − 1, 2a + 1, …, n) = lcm (1, …, n),

and so

lcm (1, …, n) | ( 1 ⋯ (a − 1)(a + 1) ⋯ (2a − 1)(2a + 1) ⋯ n ) = \frac{n!}{2a^{2}} = \frac{(n − 1)!}{2}.

Case 2: 1 < a < b . Since n = ab = lcm(a, b, ab), we have

lcm (1, …, a − 1, a + 1, …, b − 1, b + 1, …, n) = lcm (1, …, n).

Hence

lcm (1, …, n) | ( 1 ⋯ (a − 1)(a + 1) ⋯ (b − 1)(b + 1) ⋯ n ) = \frac{n!}{ab} = (n − 1)!.

In any case, we get lcm(1, …, n) | (n − 1)!, in particular (n − 1)! ≡ 0 (mod n), which completes the proof of Proposition 1.

In the sequel we consider sequences of integers and contrive a prime-detecting concept. For that purpose we define: A sequence (x_{n})_{n≥0} of integers is said to be prime-detecting if the equivalence x_{n} ≢ 0(mod n) ⟺ n ∈ ℙ holds for all but finitely many positive integers n. Proposition 1 can be applied to detect primes in a form parallel to the results below based on Apéry’s recurrences. Thus we get a very simple primality criterion using a first order recurrence with polynomial coefficients.

Proposition 2. Let a be a positive integer. We let p_{1}, …, p_{s} denote the prime divisors of a. Let

T (x) = x − 1 , r_{n} = \frac{1}{n} ,

d_{1} = a , d_{n} = T (n)d_{n−1} (n ≥ 2) .

Then for all integers n ∈ ℕ \ {4} we have

d_{n} ≢ 0 (mod n) ⟺ n ∈ ℙ \ {p_{1}, …, p_{s}},

and for p ∈ ℙ

d_{p} ≡ −a (mod p).

Moreover,

d_{n} = n!r_{n}a ,

and, consequently,

lim_{n→∞} \frac{d_{n}}{n!r_{n}} = a .

It is also possible to detect primes by integer solutions of Apéry-type recurrences. In the case of Apéry’s recurrence relation (1), we have explicit formulae for X_{n} involving combinatorial sums. From the arithmetical properties of binomial coefficients (see Eqs. (22)-(25) in Section 2) we can deduce the prime-detecting property of the sequences (X_{n})_{n≥0}. The same can be done for sequences satisfying linear recurrence relations connected with ζ(2) and log 2. For our results we do not need continued fraction expansions of ζ(3), ζ(2), and log 2. However, we state them because they are closely related to the linear recurrence formulae.

Theorem 3. Let a, b be positive integers such that 5a ≠ b. Let p_{1}, …, p_{s} denote the prime divisors of |5a − b|. Let

T (x) = 34(x − 1)^{3} + 51(x − 1)^{2} + 27(x − 1) + 5, U(x) = (x − 1)^{6},
d_{0} = a, d_{1} = b, d_{n} = T (n)d_{n−1} − U(n)d_{n−2} (n ≥ 2).

Then for all integers n ∈ ℕ we have

d_{n} ≢ 0 (mod n) ⟺ n ∈ ℙ \ {p_{1}, …, p_{s}},  (7)

and for p ∈ ℙ

d_{p} ≡ 5a − b (mod p).

Moreover,

d_{n} = n!^{3} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} ( a + \frac{b − 5a}{6} c_{n,k} ) (n ≥ 0),  (8)

where c_{n,k} is defined in Eq. (3), and

lim_{n→∞} \frac{d_{n}}{n!^{3}a_{n}} = a + \frac{b − 5a}{6} ζ(3).

R. Apéry [1] also proved the irrationality of ζ(2) using

a′_{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k},  b′_{n} = ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}c′_{n,k}  (9)

where

c′_{n,k} = 2 ∑_{m=1}^{n} \frac{(−1)^{m−1}}{m^{2}} + ∑_{m=1}^{k} \frac{(−1)^{n+m−1}}{m^{2}\binom{n}{m}\binom{n + m}{m}}  (1 ≤ k ≤ n).  (10)

Both X_{n} = a′_{n} and X_{n} = b′_{n} satisfy the recurrence formula

(n + 1)^{2}X_{n+1} − (11n^{2} + 11n + 3)X_{n} − n^{2}X_{n−1} = 0.  (11)

Here, we have

ζ(2) = \frac{5}{3 + \frac{1^{4}}{25 + \frac{2^{4}}{69 + ... +\frac{n^{4}}{11n^{2} + 11n + 3 + ⋯}}}} .

Using the coefficient polynomials of the recurrence formula (11), we get Theorem 4. Let a, b be positive integers such that 3a ≠ b. Let p_{1}, …, p_{s} denote the prime divisors of |3a − b|. Let

T (x) = 11(x − 1)^{2} + 11(x − 1) + 3, U(x) = (x − 1)^{4}, d_{0} = a, d_{1} = b, d_{n} = T (n)d_{n−1} + U(n)d_{n−2} (n ≥ 2).

Then for all integers n ∈ ℕ we have

d_{n} ≢ 0 (mod n) ⟺ n ∈ ℙ \ {p_{1}, …, p_{s}},

and for p ∈ ℙ

d_{p} ≡ b − 3a (mod p).

Moreover,

d_{n} = n!^{2} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k} ( a + \frac{b − 3a}{5} c′_{n,k} ) (n ≥ 0),

where c′_{n,k} is defined in (10), and

lim_{n→∞} \frac{d_{n}}{n!^{2}a′_{n}} = a + \frac{b − 3a}{5} ζ(2).

Theorems 3 and 4 are based on recurrence relations given by Apéry in [1]. Now we consider the recurrence formula

(n + 1)X_{n+1} − 3(2n + 1)X_{n} + nX_{n−1} = 0,  (12)

which is satisfied by X_{n} = a′′_{n} and X_{n} = b′′_{n} with

a′′_{n} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}, b′′_{n} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}c_{k},  (13)

where

c_{k} = ∑_{m=1}^{k} \frac{(−1)^{m−1}}{m} (1 ≤ k ≤ n).  (14)

We prove this result in Section 2 below. From (12) we have the continued fraction expansion

log 2 = \frac{2}{3 − \frac{1^{2}}{9 − \frac{2^{2}}{15 − ... −\frac{n^{2}}{3(2n + 1) − ⋯}}}} .

Theorem 5. Let a, b be positive integers such that 3a ≠ b. Let p_{1}, …, p_{s} denote the prime divisors of |3a − b|. Let

T (x) = 3(2x − 1), U(x) = (x − 1)^{2},
d_{0} = a,  d_{1} = b,  d_{n} = T (n)d_{n−1} − U(n)d_{n−2} (n ≥ 2).

Then for all integers n ∈ ℕ \ {4} we have

d_{n} ≢ 0 (mod n) ⟺ n ∈ ℙ \ {p_{1}, …, p_{s}},

and for p ∈ ℙ

d_{p} ≡ 3a − b (mod p).

Moreover,

d_{n} = n! ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k} (a + \frac{b − 3a}{2} c_{k}) ,

where c_{k} is defined in Eq. (14), and

lim_{n→∞} \frac{d_{n}}{n!a′′_{n}} = a + \frac{b − 3a}{2} log 2.

Remark: For n = 4 one has d_{4} = 2670b − 306a, which is not divisible by 4 if and only if a ≢ b (mod 2).

2 Proof of Theorems 3 and 4.

Proof of Theorem 3: First we prove the explicit expression (8) of d_{n}. From p_{n} and q_{n} defined in (5) and their common recurrence formula (6), we see that both Y_{n} = q_{n} and Y_{n} = p_{n} satisfy the recurrence relation

Y_{n} = T (n)Y_{n−1} − U(n)Y_{n−2} (n ≥ 2).  (15)

Obviously, for any real α and β, Y_{n} = αq_{n} + βp_{n} satisfy the relation (15) too. Now we compute α and β according to initial conditions of the sequence (d_{n})_{n≥0}:

\begin{aligned}d_{0} = & a = & αq_{0} + βp_{0} & = & α, \\ d_{1} = & b = & αq_{1} + βp_{1} & = & 5α + 6β. \end{aligned}

Then d_{n} = αq_{n} + βp_{n} are solutions of (15). The system of equations has a unique solution: α = a and β = (b − 5a)/6. Thus, expressing p_{n}, q_{n} by Eq. (5) and a_{n}, b_{n} by Eq. (2), we have the explicit formula (8) for d_{n}. Dividing this identity by n!^{3}a_{n} and using b_{n}/a_{n} → ζ(3), we find the limit a + (b − 5a)ζ(3)/6 of the sequence (d_{n}/n!^{3}a_{n})_{n≥0}.

We use the formula (8) for d_{n}. Observing that n^{3}|n!^{3} and

\frac{n!^{3}}{m^{3}} ≡ 0 (mod n) (1 ≤ m ≤ n − 1),

we get

12d_{n} ≡ 2(b − 5a)n!^{3} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2}c_{n,k} (mod n)

= 2(b − 5a)n!^{3} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} ∑_{m=1}^{n} \frac{1}{m^{3}}

+ 2(b − 5a)n!^{3} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} ∑_{m=1}^{k} \frac{(−1)^{m−1}}{2m^{3}\binom{n}{m}\binom{n + m}{m}}

≡ 2(b − 5a)n!^{3} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} \frac{1}{n^{3}}

+ \frac{(b − 5a)n!^{3}}{lcm^{3}(1, …, n)} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k} ∑_{m=1}^{k} \frac{(−1)^{m−1}lcm^{3}(1, …, n)\binom{n + k}{k}}{m^{3}\binom{n}{m}\binom{n + m}{m}} (mod n). (16)

It follows from the proof of Proposition 3 in [4] that

\frac{lcm^{3}(1, …, n)\binom{n + k}{k}}{m^{3}\binom{n}{m}\binom{n + m}{m}} ∈ ℕ (1 ≤ m ≤ k ≤ n).  (17)

Case 1: n ∉ ℙ. There is nothing to show for n = 1. Moreover, Theorem 3 is also true for n = 4 and n = 6, since

\begin{aligned}d_{4} & = & 91397560b − 781976a & ≡ & 0 & (mod 4), \\ d_{6} & = & 1604788039632960b − 13730188564800a & ≡ & 0 & (mod 6). \end{aligned}

Now let n ∉ ℙ ∪ {1, 4, 6}. In particular, we have n ≥ 8. Then, using

\frac{n!^{3}}{n^{3}} = (n − 1)! · (n − 1)!^{2},
(n − 1)! ≡ 0 (mod n) (for n ≠ 4 by Proposition 1),
(n − 1)!^{2} ≡ 0 (mod 12) (n ≥ 4),

we can simplify (16) as follows:

12d_{n} ≡ \frac{(b − 5a)n!^{3}}{lcm^{3}(1, …, n)} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k} ∑_{m=1}^{k} \frac{(−1)^{m−1}lcm^{3}(1, …, n)\binom{n + k}{k}}{m^{3}\binom{n}{m}\binom{n + m}{m}} (mod n).

Thus d_{n} ≡ 0 (mod n) follows from (17) and

\frac{n!^{3}}{lcm^{3}(1, …, n)} ≡ 0 (mod 12n) (n ∉ ℙ , n ≥ 6).  (18)

For (18) it suffices to prove the two congruences

\frac{n!}{lcm (1, …, n)} ≡ 0 (mod 12) (n ≥ 6),  (19)

\frac{n!}{lcm (1, …, n)} ≡ 0 (mod n) (n ∉ ℙ , n ≥ 6).  (20)

Both congruences (19) and (20) hold for n = 6, 7 and n = 6, respectively. In the sequel we assume that n ≥ 8 and n ∉ ℙ. First, we observe for 1 ≤ m ≤ n that

lcm (1, …, n) | lcm (1, …, m)lcm (m + 1, …, n) | m! (m + 1)(m + 2) … n = n!.  (21)

Therefore, it follows from n ≥ 8 that

\frac{n!}{lcm (1, …, 6)lcm (7, 8, …, n)} = \frac{6! · (7 · 8 ⋯ n)}{lcm (1, …, 6)lcm (7, 8, …, n)}

= 12 · \frac{7 · 8 ⋯ n}{lcm (7, 8, …, n)} ≡ 0 (mod 12),

so that (21) implies (19). The congruence (20) is already shown in the proof of Proposition 1, and therefore one conlusion in (7) of Theorem 3 holds.

Case 2: n ∈ ℙ . For n = p ∈ {2, 3} we have

\begin{aligned}d_{2} & = & 117b − a & ≡ & 5a − b (mod 2), \\ d_{3} & = & 62531b − 535a & ≡ & 5a − b (mod 3). \end{aligned}

In the sequel we assume p ≥ 5 is a prime. We need some arithmetic properties of binomial coefficients:

\binom{p}{k} ≢ 0 (mod p) ⟺ k ∈ \{0, p\},  (22)

\binom{p + k}{k} = \frac{(p + 1)(p + 2) · (p + k)}{1 · 2 … k} ≡ \frac{1 · 2 … k}{1 · 2 … k} (mod p)
≡ 1 (mod p) ⟺ k ∈ {0, 1, 2, …, p − 1},  (23)

\binom{2p}{p} = \frac{(p + 1)(p + 2) … (2p)}{1 · 2 … p} = 2 \frac{(p + 1)(p + 2) … (2p − 1)}{1 · 2 … (p − 1)}

≡ 2 \frac{1 · 2 … (p − 1)}{1 · 2 … (p − 1)} ≡ 2 (mod p),  (24)

e_{p} ( \binom{p}{k} ) ∈ \{0, 1\} (k ∈ \{0, 1, …, p\}),  (25)

where e_{p}(m) is the exponent of p in the decomposition of m. We denote the first term on the right side of (16) by S_{1} and compute its residue class modulo p using (22) and (24):

S_{1} = 2(b − 5a)p!^{3} ∑_{k=0}^{p} \binom{p}{k}^{2}\binom{p + k}{k}^{2} \frac{1}{p^{3}}

= 2(b − 5a)(p − 1)!^{3} ∑_{k=0}^{p} \binom{p}{k}^{2}\binom{p + k}{k}^{2}

≡ −2(b − 5a) ∑_{k∈\{0 , p\}} \binom{p}{k}^{2}\binom{p + k}{k}^{2} (mod p)

≡ −2(b − 5a)(1 + 4) ≡ 10(5a − b) (mod p).  (26)

Next, we treat the second term S_{2} on the right side of (16):

S_{2} = (b − 5a)p!^{3} ∑_{k=0}^{p} \binom{p}{k}^{2}\binom{p + k}{k}^{2} ∑_{m=1}^{k} \frac{(−1)^{m−1}}{m^{3}\binom{p}{m}\binom{p + m}{m}}.  (27)

It is convenient to compute the sum of the terms with 1 ≤ k ≤ p − 1 separately. By (22), (23), and (25) we have

e_{p} ( \binom{p}{k}^{2}\binom{p + k}{k}^{2} ) = 2,

e_{p} ( m^{3}\binom{p}{m}\binom{p + m}{m} ) = 1 (1 ≤ m ≤ k).

Hence we get

p!^{3} ∑_{k=1}^{p−1} \binom{p}{k}^{2}\binom{p + k}{k}^{2} ∑_{m=1}^{k} \frac{(−1)^{m−1}}{m^{3}\binom{p}{m}\binom{p + m}{m}} ≡ 0 (mod p).

Then the sum in (27) simplifies to

S_{2} ≡ (b − 5a)p!^{3} ∑_{k∈\{0 , p\}} \binom{p}{k}^{2}\binom{p + k}{k}^{2} ∑_{m=1}^{k} \frac{(−1)^{m−1}}{m^{3}\binom{p}{m}\binom{p + m}{m}}

≡ 4(b − 5a)p!^{3} ∑_{m=1}^{p} \frac{(−1)^{m−1}}{m^{3}\binom{p}{m}\binom{p + m}{m}} (mod p).

It follows from Eqs. (22), (23) and (24) that

p!^{3} ∑_{m=1}^{p} \frac{(−1)^{m−1}}{m^{3}\binom{p}{m}\binom{p + m}{m}} = \frac{p!^{3}}{p^{3}\binom{2p}{p}} + p!^{3} ∑_{m=1}^{p−1} \frac{(−1)^{m−1}}{m^{3}\binom{p}{m}\binom{p + m}{m}} ≡ \frac{p!^{3}}{2p^{3}} (mod p),

which yields

S_{2} ≡ (b − 5a) \frac{4p!^{3}}{2p^{3}} = 2(b − 5a)(p − 1)!^{3} ≡ 2(5a − b) (mod p).  (28)

The congruences (26) and (28) for S_{1} and S_{2} give

12d_{p} ≡ S_{1} + S_{2} ≡ 10(5a − b) + 2(5a − b) = 12(5a − b) (mod p) (p ≥ 5).

Since p ≥ 5 we have d_{p} ≡ 5a − b (mod p). This completes the proof. □

Proof of Theorem 4: Putting

q′_{0} = 1, q′_{n} = (n!)^{2}a′_{n} (n ≥ 1), p′_{0} = 0, p′_{n} = (n!)^{2}b′_{n} (n ≥ 1)

with a′_{n} and b′_{n} defined in (9), both sequences, (q′_{n})_{n≥0} and (p′_{n})_{n≥0}, satisfy the recurrence formula

X_{n} = T (n)X_{n−1} + U(n)X_{n−2} (n ≥ 2),  (29)

where T (n) = 11(n − 1)^{2} + 11(n − 1) + 3 and U(n) = (n − 1)^{4}. For any real α and β, Y_{n} = αq′_{n} + βp′_{n} satisfy the relation (29) too. Again we compute α and β according to the initial conditions of the sequence (d_{n})_{n≥0}:

\begin{aligned}d_{0} = & a = & αq′_{0} + βp′_{0} & = & α, \\ d_{1} = & b = & αq′_{1} + βp′_{1} & = & 3α + 5β. \end{aligned}

Then d_{n} = αq′_{n} + βp′_{n} are solutions of (29). The system of equations has a unique solution: α = a and β = (b − 3a)/5. Thus, expressing a′_{n} and b′_{n} by (9), we get the formula for d_{n}. The limit of the sequence (d_{n}/n!^{2}a′_{n})_{n≥0} can be computed using the explicit formula of d_{n} and b′_{n}/a′_{n} → ζ(2).

In what follows we use exactly the same arguments as in the proof of Theorem 3. Using the explicit formula for d_{n} we get

5d_{n} ≡ (b − 3a)n!^{2} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}c′_{n,k} (mod n)

= 2(b − 3a)n!^{2} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k} ∑_{m=1}^{n} \frac{(−1)^{m−1}}{m^{2}}

+(b − 3a)n!^{2} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k} ∑_{m=1}^{k} \frac{(−1)^{n+m−1}}{m^{2}\binom{n}{m}\binom{n + m}{m}}

≡ 2(b − 3a)n!^{2} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k} \frac{(−1)^{n−1}}{n^{2}}

+\frac{(b − 3a)n!^{2}}{lcm^{2}(1, …, n)} ∑_{k=0}^{n} \binom{n}{k}^{2} ∑_{m=1}^{k} \frac{(−1)^{n+m−1}lcm^{2}(1, …, n)\binom{n + k}{k}}{m^{2}\binom{n}{m}\binom{n + m}{m}} (mod n)

=: S_{1} + S_{2}.

For n ∉ ℙ we proceed as in the proof of Theorem 3. Next, we treat the case n ∈ ℙ. For n = p ∈ {2, 3, 5} we have

d_{2} =  25b + a ≡ b − 3a (mod 2),
d_{3} =  1741b + 69a ≡ b − 3a (mod 3),
d_{5} = 53310076b + 2112972a ≡ b − 3a (mod 5).

Now we compute the residue classes of S_{1} and S_{2} modulo p for n = p ∈ ℙ \ {2, 3, 5}. For S_{1} we get by (22) and (24):

S_{1} = 2(b − 3a)p!^{2} ∑_{k=0}^{p} \binom{p}{k}^{2}\binom{p + k}{k} \frac{(−1)^{p−1}}{p^{2}}
= 2(b − 3a)(p − 1)!^{2} ∑_{k=0}^{p} \binom{p}{k}^{2}\binom{p + k}{k}
≡ 2(b − 3a) ∑_{k∈\{0 , p\}} \binom{p}{k}^{2}\binom{p + k}{k}
≡ 2(b − 3a)(1 + 2) ≡ 6(b − 3a) (mod p).  (30)

Before treating S_{2} we observe for 1 ≤ k ≤ p − 1 that

e_{p} ( \binom{p}{k}^{2}\binom{p + k}{k} ) = 2,
e_{p} ( m^{2}\binom{p}{m}\binom{p + m}{m} ) = 1 (1 ≤ m ≤ k).

Then we get

S_{2} ≡ (b − 3a)p!^{2} ∑_{k∈\{0 , p\}} \binom{p}{k}^{2}\binom{p + k}{k} ∑_{m=1}^{k} \frac{(−1)^{p+m−1}}{m^{2}\binom{p}{m}\binom{p + m}{m}}
≡ 2(b − 3a)p!^{2} ∑_{m=1}^{p} \frac{(−1)^{m}}{m^{2}\binom{p}{m}\binom{p + m}{m}}
≡ (b − 3a) \frac{−2p!^{2}}{2p^{2}} = −(b − 3a)(p − 1)!^{2} ≡ −(b − 3a) (mod p).

This together with Eq. (30) yields

5d_{p} ≡ S_{1} + S_{2} ≡ 6(b − 3a) − (b − 3a) = 5(b − 3a) (mod p).

By p ≥ 7 we have d_{p} ≡ b − 3a (mod p). This completes the proof. □

3 On a linear recurrence sequence for log 2.

In this section we first prove that the sequences (a′′_{n})_{n≥0} and (b′′_{n})_{n≥0} satisfy the relation (12). First, we consider (a′′_{n})_{n≥0}. Let

λ_{n,k} = \binom{n}{k}\binom{n + k}{k} , A_{n,k} = −(4n + 2)λ_{n,k} (0 ≤ k ≤ n),

and A_{n,n+1} = A_{n,−1} = 0 for n ≥ 0. Note that \binom{n}{k} = 0 for k < 0 or k > n. Using

\frac{λ_{n,k−1}}{λ_{n,k}} = \frac{k^{2}}{(n + k)(n − k + 1)} , \frac{λ_{n+1,k}}{λ_{n,k}} = \frac{n + k − 1}{n − k + 1} , \frac{λ_{n−1,k}}{λ_{n,k}} = \frac{n − k}{n + k} (1 ≤ k ≤ n),

we have

A_{n,k} − A_{n,k−1} = (n + 1)λ_{n+1,k} − 3(2n + 1)λ_{n,k} + nλ_{n−1,k} (1 ≤ k ≤ n).  (31)

Therefore, we get

0 = A_{n,n+1} − A_{n,−1} = ∑_{k=0}^{n+1}(A_{n,k} − A_{n,k−1}) = (n + 1)a′′_{n+1} − 3(2n + 1)a′′_{n} + na′′_{n−1},

which proves that (a′′_{n})_{n≥0} satisfies (12).

Next, we prove that (b′′_{n})_{n≥0} satisfies the relation (12). Let

S_{n,k} = (n + 1)λ_{n+1,k}c_{k} − 3(2n + 1)λ_{n,k}c_{k} + nλ_{n−1,k}c_{k} (1 ≤ k ≤ n),

B_{n,k} = A_{n,k}c_{k} for 0 ≤ k ≤ n, and B_{n,n+1} = B_{n,−1} = 0 for n ≥ 0. By (31) we have

B_{n,k} − B_{n,k−1} = (A_{n,k} − A_{n,k−1})c_{k} + A_{n,k−1}(c_{k} − c_{k−1})
= S_{n,k} + A_{n,k−1} \frac{(−1)^{k−1}}{k} (1 ≤ k ≤ n).

This yields

0 = B_{n,n+1} − B_{n,−1} = ∑_{k=0}^{n+1}(B_{n,k} − B_{n,k−1})

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

= (n + 1)b′′_{n+1} − 3(2n + 1)b′′_{n} + nb′′_{n−1} − (4n + 2) ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}\frac{(−1)^{k}}{k + 1}
= (n + 1)b′′_{n+1} − 3(2n + 1)b′′_{n} + nb′′_{n−1} (n ≥ 1),

since, by Vandermonde’s theorem on the hypergeometric series _{2}F_{1}(a, b; c; x),

∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}\frac{(−1)^{k}}{k + 1} = _{2}F_{1}(n + 1, −n; 2; 1) = \begin{matrix}(1 − n) & n \\ (2) & n \end{matrix} = 0 .

It remains to show that lim_{n→∞} b′′_{n}/a′′_{n} = log 2. For this purpose we shall apply a theorem of O. Toeplitz concerning linear series transformations (cf. [8, p. 10, no. 66], [10]). From Toeplitz’s result we have

lim_{n→∞} \begin{matrix}\binom{n}{ν} & \binom{n + ν}{ν} \\ ∑_{k=0}^{n} & \binom{n}{k} & \binom{n + k}{k} \end{matrix} = 0 (ν ≥ 0) ⟺ lim_{n→∞} \frac{b′′_{n}}{a′′_{n}} = log 2.

The limit on the left-hand side follows from the inequality

\begin{matrix}\binom{n}{ν} & \binom{n + ν}{ν} \\ ∑_{k=0}^{n} & \binom{n}{k} & \binom{n + k}{k} \end{matrix} ≤ \frac{\binom{n}{ν}\binom{n + ν}{ν}}{\binom{n}{ν}\binom{n + ν}{ν} + \binom{n}{ν + 1}\binom{n + ν + 1}{ν + 1}} = \frac{1}{1 + \frac{(n + ν + 1)(n − ν)}{(ν + 1)^{2}}} ,

in which we choose n > ν. Theorem 5 can be proven in the same way as it was done for Theorems 3, 4 in Section 2.

4 Concluding remarks.

We complete the above results by a short summary of known prime-detecting methods. First, by Proposition 1 or Wilson’s theorem, it is clear that (Γ(n))_{n≥1} is a prime-detecting sequence formed by the Gamma function.

1. Detecting primes by polynomials. Legendre showed that there is no rational algebraic function which takes always primes. However, polynomials in many variables with integer coefficients are known whose positive values are exactly the prime numbers obtained as the variables run through all nonnegative integers, [9, p. 158]. The background of this result is given by the fact that the set of primes can be described by diophantine equations.

2. Detecting primes by binomial coefficients. Deutsch [5] has proven the following result for all integers n ≥ 2:

\binom{n − 1}{k} ≡ (−1)^{k} (mod n) (0 ≤ k ≤ n − 1) ⟺ n ∈ ℙ.

3. Detecting primes by Dirichlet series. Prime-detecting sequences can be constructed from Dirichlet series. Let s ≥ 2 be an integer, let (a_{m})_{m≥1} be a sequence of integers such that a_{m} = O(m^{s−1−ε}) for any ε > 0 as m → ∞. Then the Dirichlet series ∑_{m=1}^{∞} a_{m}/m^{s} converges. Assume the weak condition that a_{p} does not vanish for primes p. Then the sequence (x_{n})_{n≥1} defined by x_{n} = (n!)^{s} ∑_{m=1}^{n} a_{m}/m^{s} is prime-detecting since for n ∈ ℕ \ {4} we have by Proposition 1 that

x_{n} = n^{s} ∑_{m=1}^{n−1} a_{n}(\frac{(n − 1)!}{m})^{s} + a_{n}((n − 1)!)^{s}

≡ a_{n}((n − 1)!)^{s} ≡ \{ \begin{matrix}(−1)^{s}a_{n}(mod n), & if n ∈ ℙ; \\ 0 (mod n), & if n ∉ ℙ. \end{matrix}

5 Acknowledgement.

I warmly thank the referee for her/his report that helped to improve the initial version of this article. In particular, it was the referee’s idea to include Proposition 2.

References

[1] R. Apéry, Irrationalité de ζ(2) et ζ(3), Astérisque 61 (1979), 11–13.

[2] F. Beukers, Another congruence for the Apéry numbers, J. Number Theory 25 (1987), 201–210.

[3] F. Beukers, A note on the irrationality of ζ(2) and ζ(3), Bull. London Math. Soc. 11 (1979), 268–272.

[4] H. Cohen, Demonstration de l’irrationalité de ζ(3) (d’après R. Apéry), Séminaire de Théorie des Nombres, Grenoble (1978), VI.1 – VI.9.

[5] E. Deutsch, Problem 1494. Math.i Mag. 69, 143.

[6] W. Koepf, Hypergeometric Summation, Vieweg, 1998.

[7] O. Perron, Die Lehre von den Kettenbrüchen, Chelsea Publishing Company, 1929.

[8] G. Pólya, G. Szegö, Aufgaben und Lehrsätze aus der Analysis, Bd. 1, 3rd ed., Springer, 1964.

[9] P. Ribenboim, Die Welt der Primzahlen, Springer, 2006.

[10] O. Toeplitz, Über allgemeine lineare Mittelbildungen, Prace mat.-fiz., 22 (1911), 113– 119.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11B50, 11A41, 11A55. Keywords: recurrences, sequences mod m, primes, continued fractions.

(Concerned with sequences \underline{A000040}, \underline{A000045}, \underline{A000142}, \underline{A001850}, \underline{A003418}, \underline{A005258}, and \underline{A005259}.)

Received July 25 2008; revised version received October 23 2008. Published in Journal of Integer Sequences, November 16 2008.

Return to Journal of Integer Sequences home page.