Binomial Transform and Dold Sequences

Klaudiusz Wójcik Department of Mathematics and Computer Science Jagiellonian University Łojasiewicza 6 30-348 Kraków Poland

                  Klaudiusz.Wojcik@uj.edu.pl

Abstract We prove that the binomial transform T (a) of a Dold sequence a is a Dold sequence itself. We also show that if a and T (a) are bounded Dold sequences then they are both periodic with period 6.

1 Introduction

Let a = (a_{n})_{n≥0} be a sequence of complex numbers. The binomial transform of the sequence a is the sequence T (a) = (T (a)_{n})_{n≥0} defined in [16] by

T (a)_{n} = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}a_{i}, n ≥ 0.

The binomial transform is a linear involution and the original sequence a can be recovered from the relation

a_{n} = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}T (a)_{i}, n ≥ 0.

We say that a sequence of integers a = (a_{n})_{n≥0} is a Dold sequence [11] if

∑_{k|n} μ(k)a_{n/k} ≡ 0 (mod n), n ≥ 1,  (1)

where μ : ℕ → ℤ is the Möbius function given by

μ(n) = \begin{cases}1, & if n = 1; \\ (−1)^{k}, & if n = p_{1} ⋯ p_{k}, p_{i}, distinct primes; \\ 0, & otherwise. \end{cases}

It is easy to verify that a sequence of integers a is a Dold sequence a if and only if for every prime p and natural numbers m, α such that gcd(p, m) = 1 we have

a_{mp^{α}} ≡ a_{mp^{α−1}} (mod p^{α}).

We will say that a sequence of integers a is a weak Dold sequence if for every prime number p

a_{p} ≡ a_{1} (mod p).

Obviously a Dold sequence is a weak Dold sequence. Babienko and Bogatyi proved that if a Dold sequence is bounded, then it is periodic [11]. Among the Dold sequences, the Lefschetz sequences play an important role from the point of view of applications in dynamical systems. A sequence of integers a is a Lefschetz sequence if there exist a compact ENR (i.e., Euclidean neighborhood retract) X and a continuous map f : X → X such that a_{n} is the Lefschetz number L(f^{n}) of the n-th iteration of f. Let us recall that a Lefschetz number of f is defined by

L(f) = ∑_{k≥0}(−1)^{k}tr H_{k}(f),

where H_{k}(f) : H_{k}(X) → H_{k}(X) is the endomorphism induced by f on the k-th singular homology of X (with rational coefficients). One can prove [11] that a Dold sequence a = (a_{n})_{n≥1} is a Lefschetz sequence if and only if there are integer matrices A ∈ M_{k}(ℤ), B ∈ M_{m}(ℤ) such that

a_{n} = tr A^{n} − tr B^{n}, n ≥ 1.

In the sequel we will treat a Lefschetz sequence a = (a_{n})_{n≥1} as a sequence a = (a_{n})_{n≥0} with

a_{0} = tr A^{0} − tr B^{0}.

If a is a Lefschetz sequence with B = 0 then we call it a sequence of traces of integer matrix, i.e., a_{n} = tr A^{n}.

The aim of this note is to study the binomial transforms of Dold sequences. We show that a is a Dold sequence if and only if its binomial transform T (a) is a Dold sequence (Theorem 7). The proof of Theorem 7 is trivial if a is a Lefschetz sequence. Indeed, if a is a sequence of traces then we have a closed formula for its binomial transform T (a), namely

T (a)_{n} = ∑_{i=1}^{n}(−1)^{i}\binom{n}{i}tr A^{i} = tr (I − A)^{n},

so T (a) is a sequence of traces. In particular, binomial transform of the sequence of traces is a Dold sequence. Obviously the same argument works in the case of a Lefschetz sequence a with matrices A and B. Then T (a) is a Lefschetz sequence itself with matrices I − A and I − B. Unfortunately, there are Dold sequences that are not Lefschetz sequences. Let us observe that if a is a Lefschetz sequence then |a_{n}| ≤ kρ^{n}, where ρ is the spectral radius of H(f) and k is a dimension of H(X). In particular, the sequence a_{n} = ∑_{k|n} k^{k} cannot be obtained as a Lefschetz sequence although it is Dold sequence [11].

We also prove that if a is a Dold sequence such that a and T (a) are bounded then both a and T (a) are 6-periodic. In particular, if a is l-periodic (non-constant) Dold sequence with l ≠ 6 then T (a) is unbounded (Theorem 9). This result has interesting consequences from the point of view of the geometric method for detecting chaotic dynamics generated by non-autonomous periodic in time ordinary differential equations based on the notion of isolating segments [19, 20, 15, 17]. The above method gives a sufficient conditions for the existence of the compact invariant set I for the Poincaré map P such that P restricted to I is semi-conjugated to the shift map σ : Σ_{2} → Σ_{2} where Σ_{2} = {0, 1}^{ℤ} i.e., there is a continuous surjective map g : I → Σ_{2} such that g ∘ P |_{I} = σ ∘ g. The important dynamical question is if for n-periodic sequence c ∈ Σ_{2} there exists n-periodic point x of the Poincaré map P such that x ∈ g^{−1}(c), i.e., trajectory of x is coded by the sequence c. In the context of results in [20] it appears that there is a Dold sequence a with the property that T (a)_{k} ≠ 0 implies that g^{−1}(c) contains n-periodic point of P for every n-periodic sequence c ∈ Σ_{2} with k-symbols 1. Our Theorem 9 guarantees the existence of infinitely many periodic points of the Poincaré map.

It seems that the results we obtained can be also interesting from the point of view of elementary number theory and combinatorics, because many classical integer sequences are Dold sequences. For example, the k-Lucas sequences [6, 18], the generalized k-Fibonacci sequences [5], sequences generated by Lucas functions [4, 6], and sequences generated by Tchebycheff polynomials of the first kind [6, 9]. In particular, the classical Lucas sequence L given by

L_{n} = (\frac{1 + \sqrt{5}}{2})^{n} + (\frac{1 − \sqrt{5}}{2})^{n} ,

is a Dold sequence (even sequence of traces with the matrix A = [ \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ]) and the following congruences

1. if p is odd prime then L_{2p} ≡ 3 (mod p),

2. for k ≥ 1 we have L_{2^{k}} ≡ 3 (mod 4).

3. if r ≥ 2 then L_{2^{r}} ≡ 7 (mod 8).

considered by the authors in [1, 12, 13] easily follow by Eq. (1).

We will finish this paper with the results concerning the sequences of the form

a_{n}(l, r) = ∑_{s≡r (mod l)}(−1)^{s}\binom{n}{s}, b_{n}(l, r) = la_{n}(l, r), n ≥ 0.

where l ≥ 2 and r ∈ {0, …, l−1} are fixed. The congruences related to these sequences were studied in [21, 22]. As the application of Theorem 7 we get that for l ≥ 2 and r ∈ {0, …, l−1} the sequence b(l, r) is a Dold sequence exactly if one of the following conditions holds

1. l ≥ 2 and r = 0,

2. l = 2r and r ≥ 1.

We also show that a_{n}(l, 0) = 0 if and only if l is odd and \frac{n}{l} ∈ 2ℕ + 1. It is easy to check that if a is l-periodic then T (a)_{n} = ∑_{r=0}^{l−1} a_{r}a_{n}(l, r). We prove that if a is l-periodic (weak) Dold sequence and l is prime then

T (a)_{n} = a_{n}(l, 0)(a_{0} − a_{1}), n ≥ 0.

2 Main results.

Lemma 1. Let a be a sequence of integers. Then a is a weak Dold sequence if and only if T (a) is a weak Dold sequence.

Proof. Since T is an involution so it is sufficient to show that T (a) is a weak Dold sequence provided a is a weak Dold sequence. We have

T (a)_{1} = a_{0} − a_{1}, T (a)_{2} = a_{0} − 2a_{1} + a_{2},

and a_{1} ≡ a_{2} (mod 2) so

T (a)_{2} ≡ a_{0} + a_{2} ≡ a_{0} + a_{1} ≡ a_{0} − a_{2} ≡ T (a)_{1} (mod 2).

Let p be odd prime. Then

T (a)_{p} = ∑_{i=0}^{p}(−1)^{i}\binom{p}{i}a_{i} ≡ a_{0} − a_{p} ≡ a_{0} − a_{1} ≡ T (a)_{1} (mod p),

because p|\binom{p}{i} for i = 1, …, p − 1.

Lemma 2. Let a be a l-periodic weak Dold sequence (l ≥ 2). If gcd(n, l) = 1 then a_{n} = a_{1}.

Proof. It follows by Dirichlet’s theorem that there exist infinitely many primes in the sequence kl + n. Let p be a prime of the form kl + n such that p > |a_{n} − a_{1}|. Since a is a l-periodic weak Dold sequence, we have

a_{n} = a_{p} ≡ a_{1} (mod p).

Hence p|a_{n} − a_{1} and consequently a_{n} = a_{1}.

Corollary 3. Let a be a l-periodic weak Dold sequence with l prime. Then

T (a)_{n} = a_{n}(l, 0)(a_{0} − a_{1}), n ≥ 0,

where a_{n}(l, 0) = ∑_{s≡0 (mod l)}(−1)^{s}\binom{n}{s}.

Proof. It follows by Lemma 2 that the l-periodic sequence a has the form

a_{1} = … = a_{l−1}, a_{0} = a_{l},

hence

T (a)_{n} = ( ∑_{s≡0 (mod l)}(−1)^{s}\binom{n}{s}) a_{0} + ( ∑_{s≢0 (mod l)}(−1)^{s}\binom{n}{s}) a_{1}
= a_{n}(l, 0)(a_{0} − a_{1})

because ∑_{s=0}^{n}(−1)^{s}\binom{n}{s} = 0.

We recall the characterization of Dold sequences given in [6]. Let us note that Dold sequence in [6] is called a generalized Fermat sequence. Let c = (c_{n})_{n≥1} be a sequence of integers. We say that sequence a is a Newton sequence generated by c if

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ⋯ + c_{n−1}a_{1} + nc_{n}, n ≥ 1.

Remark 4. Assume that c is a finite sequence, i.e., there exists m ≥ 1 such that c_{n} = 0 for n > m. One can check [6] that then

a_{n} = tr M_{m}^{n}, n ≥ 1

where M_{m} is the companion matrix of the polynomial x^{m}−c_{1}x^{m−1}−c_{2}x^{m−2}−⋯−c_{m−1}x−c_{m}, i.e.,

M_{m} = [ \begin{matrix}0 & 0 & ⋯ & 0 & c_{m} \\ 1 & 0 & ⋯ & 0 & c_{m−1} \\ 0 & 1 & ⋯ & 0 & c_{m−2} \\ ⋮ & 0 & ... & 0 & ⋮ \\ 0 & ⋯ & 0 & 1 & c_{1} \end{matrix} ] ∈ M_{m}(ℤ)

Proposition 5. Let a = (a_{n})_{n≥1} be a sequence of integers. Then a is a Dold sequence if and only if there exists an integer sequence c such that a is a Newton sequence generated by c.

Proof. It follows by [6, Thm. 5, Thm. 6].

Lemma 6. Let a = (a_{n})_{n≥1} be a sequence of integers. Then a is a Dold sequence if and only if for every m ≥ 1 there exists a matrix A_{m} ∈ M_{m}(ℤ) such that

a_{n} = tr A_{m}^{n}, 1 ≤ n ≤ m.

Proof. We first prove the part “if”, so we assume that a is a Dold sequence. Let c be a sequence of integers such that a is a Newton sequence generated by c. Let m ≥ 1 be fixed. Let us consider a finite sequence c(m) such that

c(m)_{n} = \begin{cases}c_{n}, & if 1 ≤ n ≤ m; \\ 0, & otherwise. \end{cases}

Let b be a Newton sequence generated by c(m). Then

b_{n} = tr M_{m}^{n}, n ≥ 1,

and a_{n} = b_{n} for 1 ≤ n ≤ m by definition of the Newton sequence, so the result follows.

We now prove the “only if” part. We have to show that a is a Dold sequence. Let m ≥ 1 be fixed. We show that

∑_{k|m} μ(k)a_{m/k} ≡ 0 (mod m).

By assumption there exists a matrix A_{m} ∈ M_{m}(ℤ) such that

a_{n} = tr M_{m}^{n}, 1 ≤ n ≤ m.

Let b be a sequence defined by b_{n} = tr A_{m}^{n}, n ≥ 1. Then b is a Dold sequence and a_{n} = b_{n} for 1 ≤ n ≤ m. In particular,

∑_{k|m} μ(k)a_{m/k} = ∑_{k|m} μ(k)b_{m/k} ≡ 0 (mod m),

so the proof is complete.

Theorem 7. Assume that a = (a_{n})_{n≥0} is a sequence of integers. Then a is a Dold sequence if and only if T (a) is a Dold sequence.

Proof. Since T is an involution, it is sufficient to show that T (a) is a Dold sequence provided that a is a Dold sequence. Let m ≥ 2 be fixed. We have to show that

∑_{k|m} μ(k)T (a)_{m/k} ≡ 0 (mod m).

By Lemma 6 there exists a matrix A_{m} ∈ M_{m}(ℤ) such that

a_{n} = tr A_{m}^{n}, 1 ≤ n ≤ m.

Let ã be a sequence defined by

ã_{n} = tr A_{m}^{n}.

Then

a_{1} = ã_{1}, a_{m} = ã_{m}, ã_{0} = m,

and T (ã) is a Dold sequence given by

T (ã)_{n} = tr (I − A_{m})^{n}, n ≥ 0.

In particular,

∑_{k|m} μ(k)T (ã)_{m/k} ≡ 0 (mod m).

Let 1 ≤ n ≤ m. Then

T (ã)_{m} = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}ã_{i} = m − a_{0} + ∑_{i=0}^{n}(−1)^{i}\binom{n}{i}a_{i} = m − a_{0} + T (a)_{m}.

Consequently, we get that

∑_{k|m} μ(k)T (a)_{m/k} = ∑_{k|m} μ(k)T (ã)_{m/k} + (m − a_{0}) (∑_{k|m} μ(k))

= ∑_{k|m} μ(k)T (ã)_{m/k} ≡ 0 (mod m),

because ∑_{k|m} μ(k) = 0 for m ≥ 2. The proof is complete since m ≥ 2 was arbitrary.

Let a be a Lefschetz sequence with matrices A and B. We call a complex number λ ∈ ℂ an essential eigenvalue of the pair (A, B) if the algebraic multiplicity of λ as the eigenvalue of A is different from the algebraic multiplicity of λ as the eigenvalue of B. By σ_{ess}(A, B) we denote the set of all essential eigenvalues of (A, B). Let ρ_{ess} := ρ_{ess}(A, B) be the essential spectral radius of (A, B), i.e.,

ρ_{ess} = max{|λ| : λ ∈ σ_{ess}(A, B)}.

Remark 8. Assume that a Dold sequence a = (a_{n})_{n≥0} is bounded. It follows by [11, Theorem 3.1.26] that a is a periodic Lefschetz sequence with l-periodic matrices A and B. We treat a as the sequence (a_{n})_{n≥0} with a_{0} = tr A^{0} − tr B^{0}. Then a_{0} = a_{l} and binomial transform of a is given by

T (a)_{n} = tr (I − A)^{n} − tr (I − B)^{n}, n ≥ 0.

Theorem 9. If a is a Dold sequence and a, T (a) are bounded then (a_{n})_{n≥1}, (T (a))_{n≥1} are 6-periodic.

Proof. Since a is bounded Dold sequence, it follows by [11, Theorem 3.1.26] that a is lperiodic Lefschetz sequence with l-periodic matrices A, B (i.e., A^{l} = I_{k}, A^{l} = I_{m}). In particular,

σ(A), σ(B) ⊂ {1, ω, …, ω^{l−1}},

where ω = e^{\frac{2πi}{l}} is a primitive root of unity. We treat a as a sequence

a_{n} = tr A^{n} − tr B^{n}, n ≥ 0,

so

T (a)_{n} = tr (I − A)^{n} − tr (I − B)^{n}, n ≥ 0.

Observe that λ ∈ σ_{ess}(A, B) if and only if 1 − λ ∈ σ_{ess}(I − A, I − B) and T (a) is periodic, because it is a bounded Dold sequence. Let 1 − λ ∈ σ_{ess}(I − A, I − B) ∩ 𝕊^{1}. Then |λ| = |1 − λ| = 1, so one can easily check that λ = e^{± \frac{πi}{3}} . Observe that then 1 − λ = \overline{λ}. It follows that

σ_{ess}(A, B) ∩ (𝕊^{1} \ \{1\}) = σ_{ess}(I − A, I − B) ∩ 𝕊^{1} ⊂ \{e^{± \frac{πi}{3}} \}.

Suppose that ρ := ρ_{ess}(I − A, I − B) > 1. Then there exists exactly one pair λ, \overline{λ} ∈ {1, ω, …, ω^{l−1}} such that

|1 − λ| = |1 − \overline{λ}| = ρ.

Then

lim_{n→∞} \frac{T (a)_{n}}{ρ^{n}} = g ≠ 0,

so T (a) is unbounded, a contradiction. So we get that ρ ≤ 1. We show that

σ_{ess}(I − A, I − B) ⊂ \{0, e^{± \frac{πi}{3}} \}.

We have that

T (a)_{n} = ∑_{1−λ∈σ_{ess}(I−A,I−B)∩\{0,e^{± \frac{πi}{3}} \}}(1 − λ)^{n} + ∑_{1−λ∈σ_{ess}(I−A,I−B)∩\{z:0<|z|<1\}}(1 − λ)^{n},

so the sequence

∑_{1−λ∈σ_{ess}(I−A,I−B)∩{z:0<|z|<1}}(1 − λ)^{n}

is the periodic integer sequence that converge to 0, so we get that

σ_{ess}(I − A, I − B) ∩ {z : 0 < |z| < 1} = ∅.

Corollary 10. If a is l-periodic (non-constant) Dold sequence with l ≠ 6 then T (a) is unbounded.

3 Applications to binomial sums

Assume that l ≥ 2 and r ∈ ℤ. We define the l-periodic sequence a[l, r] = (a_{n}[l, r])_{n≥0} by

a_{n}[l, r] = \begin{cases}1, & if n ≡ r (mod l); \\ 0, & otherwise. \end{cases}

Then a(l, r) = (a_{n}(l, r))_{n≥0} = T (a[l, r]) is its binomial transform where

a_{n}(l, r) = ∑_{s≡r (mod l)}(−1)^{s}\binom{n}{s}, n ≥ 0.

We define

b[l, r] := la[l, r], b(l, r) := la(l, r).

Remark 11. It follows by Corollary 3 we have

T (a) = a(l, 0)(a_{0} − a_{1}), n ≥ 0,

if a is l-periodic Dold sequence with l prime. Moreover, by Eq. (1)

a_{0} = a_{l} ≡ a_{1} (mod l),

so T (a) = kb(l, 0) for some k ∈ ℤ.

Remark 12. The sequence b(l, r) is particularly interesting from the point of view of applications in the detection of chaotic dynamics [19, 20]. It turns out that it is closely related to the sequence of indices of fixed points allowing to understand the nature of symbolic dynamics for the Poincaré mapping associated with the periodic in time ordinary differential equations [15, 17]. More specifically, let P be the Poincaré map for the planar periodic equation

ż = \overline{z}^{k}(1 + |z|^{2}e^{iκt}), z ∈ ℂ.

For sufficiently small κ > 0 there exist a compact invariant set I for P and a continuous surjective map g : I → Σ_{2} such that

g ∘ (P |_{I}) = σ ∘ g,

where σ : Σ_{2} → Σ_{2} is the shift map [20]. It follows by [20] that if b_{n}(k + 1, 0) ≠ 0 and c ∈ Σ_{2} is m-periodic sequence with n-symbols 1 then the Poincaré map P has m-periodic point x ∈ I such that g(x) = c.

In this section we apply Theorem 7 to prove that for l ≥ 2 and r ∈ {0, …, l − 1} the sequence b(l, r) is a Dold sequence if and only if l ≥ 2 and r = 0 or l = 2r and r ≥ 1. We also prove Glaisher-type congruences for the sequence a(l, r). Moreover, we show that a_{n}(l, 0) = 0 if and only if l is odd and n is an odd multiplicity of l.

Remark 13. Let us observe that

b_{n}(l, r) = ∑_{t=0}^{l−1} ω^{−tr}(1 − ω^{t})^{n}, n ≥ 0,

where ω = e^{\frac{2πi}{l}} is a primitive l-root of unity. Indeed, it is well-known that

∑_{t=0}^{l−1} ω^{ts} = \begin{cases}l, & if l|s; \\ 0, & otherwise. \end{cases}

so we get that

∑_{t=0}^{l−1} ω^{−tr}(1 − ω^{t})^{n} = ∑_{t=0}^{l−1} ω^{−tr} ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{n − k}ω^{t(n−k)}

= ∑_{k=0}^{n}(−1)^{n−k}\binom{n}{n − k} (∑_{t=0}^{l−1} ω^{t(n−k−r)})

= ∑_{s=0}^{n}(−1)^{s}\binom{n}{s} (∑_{t=0}^{l−1} ω^{t(s−r)}) = b_{n}(l, r).

Theorem 14. The sequence b(l, 0) = (b_{n}(l, 0))_{n≥0} is a sequence of traces. In particular, b(l, 0) is a Dold sequence.

Proof. Let l ≥ 2 and ω = e^{\frac{2πi}{l}}. We consider the matrix A_{l} ∈ M_{l}(ℤ) given by

A_{l} = [ \begin{matrix}0 & 0 & ⋯ & 0 & 1 \\ 1 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & 0 & ... & 0 & ⋮ \\ 0 & ⋯ & 0 & 1 & 0 \end{matrix} ] ∈ M_{l}(ℤ).

One can check that A_{l} has eigenvalues 1, ω, …, ω^{l−1}, hence

tr (I − A_{l})^{n} = ∑_{t=0}^{l−1}(1 − ω^{t})^{n} = b_{n}(l, 0).

Theorem 15. Let l ≥ 2 and r ∈ {1, …, l − 1}. The sequence b(l, r) is a Dold sequence if and only if l = 2r.

Lemma 16. If l = 2r then b(2r, r) is a Dold sequence (even a Lefschetz sequence).

Proof. For l = 2r and ω = e^{\frac{2πi}{l}} we have

b_{n}(2r, r) = ∑_{t=0}^{l−1} ω^{−tr}(1 − ω^{t})^{n} = ∑_{t=0}^{l−1}(−1)^{t}(1 − ω^{t})^{n}

= ∑_{t even}(1 − ω^{t})^{n} − ∑_{t odd}(1 − ω^{t})^{n}.

Let us observe that 1, ω^{2}, …, ω^{l−2} are roots of the polynomial λ^{r} −1 = 0 and the eigenvalues of the matrix

A = [ \begin{matrix}0 & 0 & ⋯ & 0 & 1 \\ 1 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & 0 & ... & 0 & ⋮ \\ 0 & ⋯ & 0 & 1 & 0 \end{matrix} ] ∈ M_{r}(ℤ)

and ω, ω^{3}, …, ω^{l−1} are roots of the polynomial λ^{r} + 1 = 0 and the eigenvalues of the matrix

B = [ \begin{matrix}0 & 0 & ⋯ & 0 & −1 \\ 1 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & ⋯ & 0 & 0 \\ ⋮ & 0 & ... & 0 & ⋮ \\ 0 & ⋯ & 0 & 1 & 0 \end{matrix} ] ∈ M_{r}(ℤ)

hence

b_{n}(2r, r) = tr (I − A)^{n} − tr (I − B)^{n},

so b(2r, r) is a Dold sequence (even Lefschetz sequence).

Remark 17. If n > 2 then there exists a prime number p < n such that gcd(n, p) = 1. Indeed, if n is odd then one can take p = 2. If n = 2k is even then by Bertrand’s postulate there is a prime p such that k < p < 2k.

Lemma 18. If l > 2 and r ∈ {1, …, l − 1} then the sequence b(l, r) is a weak Dold sequence if and only if gcd(r, l) > 1. In particular, b(l, 1) is not a Dold sequence for l > 2.

Proof. Assume that l > 2. Since b(l, r) = T (b[l, r]), so by Theorem 7 it is sufficient to show that b[l, r] is a weak Dold sequence if and only if gcd(r, l) > 1. Assume that gcd(r, l) > 1. In particular, r > 1 so b_{1}[l, r] = 0 by definition of the sequence b[l, r]. Since gcd(r, l) > 1, there is no prime p of the form kl + r. Hence b_{p}[l, r] = 0 for every prime p, and b[l, r] is a weak Dold sequence.

Assume that b[l, r] is a weak Dold sequence and suppose that gcd(r, l) = 1. If r > 1 then b_{1}[l, r] = 0 and b_{r}[l, r] = l by definition. On the other hand b_{1}[l, r] = b_{r}[l, r] by Lemma 2, a contradiction. Let r = 1. Then b_{1}[l, 1] = l by definition. By Remark 17 there is a prime number p such that p < l and gcd(l, p) = 1. Then b_{p}[l, 1] = b_{1}[l, 1] = l by Lemma 2 and b_{p}[l, 1] = 0 by definition, a contradiction.

Lemma 19. Let l > 2 and r ∈ {1, …, l − 1}. If b(l, r) is a Dold sequence then r > 1 and r|l. Proof. Assume that b(l, r) = la(l, r) is a Dold sequence. We may assume that gcd(r, l) > 1. In particular, 2 ≤ r < l − 1. Then for 1 ≤ n < r we have b_{n}(l, r) = 0 and b_{r}(l, r) = (−1)^{r}l. By Eq. (1) we get that

(−1)^{r}l = b_{r}(l, r) = ∑_{k|r} μ (\frac{r}{k} ) b_{k}(l, r) ≡ 0 (mod r),

so the result follows. Lemma 20. Assume l > 2 and r ∈ {1, …, l − 1}. If b(l, r) is a Dold sequence then l = 2r. Proof. It follows by Theorem 7 that b[l, r] is a Dold sequence. By Lemma 19 we may assume that r|l, so l = mr for some m > 1. By definition we have that b_{r}[l, r] = l and b_{n}[l, r] = 0 for n ∈ {1, …, r(m + 1) − 1} \ {r}. Let p < m be a prime number. It follows by Eq. (1) with n = pr that

∑_{k|n} μ(k)b_{n/k}[l, r] = b_{r}[l, r] = l ≡ 0 (mod n).

Hence pr|l = mr, and p|m. By Remark 17 we get that m = 2.

Proof of Theorem 15: It follows by Lemmas 16 and 20. Lemma 21. The sequence b_{n}(l, r) has properties

1. b_{n+1}(l, r) = b_{n}(l, r) − b_{n}(l, r − 1) for n ≥ 0,

2. b_{n}(l, r) = b_{n}(l, r + l) for n ≥ 0. Proof. A direct calculation shows that

b_{n+1}(l, r) = ∑_{t=0}^{l−1} ω^{−tr}(1 − ω^{t})^{n+1} = ∑_{t=0}^{l−1} ω^{−tr}(1 − ω^{t})^{n} − ∑_{t=0}^{l−1} ω^{−t(r−1)}(1 − ω^{t})^{n}
= b_{n}(l, r) − b_{n}(l, r − 1).

Since ω^{l} = 1 so

b_{n}(l, r + l)) = ∑_{t=0}^{l−1} ω^{−t(r+l)}(1 − ω^{t})^{n} = b_{n}(l, r).

Theorem 22. Let l ≥ 2. Assume that q > 1 and k ≥ 1 are such that

a_{k+1}(l, r) ≡ \begin{cases}1 (mod q), & if r ≡ 0 (mod l); \\ −1 (mod q), & if r ≡ 1 (mod l); \\ 0 (mod q), & if r ≡ s ∈ \{2, …, l − 1\}. \end{cases}

Then for every r ∈ ℤ we have

a_{n+k}(l, r) ≡ a_{n}(l, r) (mod q), n > 0.

Proof. We have

a_{1}(l, r) = \begin{cases}1, & r ≡ 0 (mod l); \\ −1, & r ≡ 1 (mod l); \\ 0, & otherwise, \end{cases}

so the result holds for n = 1. Assume that it holds for some n ≥ 1. Then by inductive step and Lemma 21 we have

a_{n+1+k}(l, r) = a_{n+k}(l, r) − a_{n+k}(l, r − 1)
≡ a_{n}(l, r) − a_{n}(l, r − 1) = a_{n+1}(l, r) (mod q).

Example 23 (Glaisher). Assume that p is prime and b ≥ 1 is such that p^{b} ≡ 1 (mod l). Then for k = p^{b} − 1 and q = p we get

a_{n+p^{b}−1}(l, r) ≡ a_{n}(l, r) (mod p).

In particular, for l = p − 1 and b = 1 we get Glaisher’s congruence

a_{n+p−1}(p − 1, r) ≡ a_{n}(p − 1, r) (mod p), n > 0.

Example 24. Assume that q > 1 is an integer relatively prime to l ∈ ℤ^{+}. Let q = ∏_{s=1}^{t} p_{s}^{α_{s}}, where p_{1}, …, p_{t} are distinct primes and α_{s} ∈ ℤ^{+}. Put

ν_{l}(q) = LCM (p_{1}^{α_{1}−1}(p_{1}^{β_{1}} − 1), …, p_{t}^{α_{t}−1}(p_{t}^{β_{t}} − 1)) ,

where β_{s} is the smallest positive integer with p_{s}^{β_{s}} ≡ 1 (mod m). Then we have [22]

a_{1+ν_{l}(q)}(l, r) ≡ \begin{cases}1 (mod q), & if r ≡ 0 (mod l); \\ −1 (mod q), & if r ≡ 1 (mod l); \\ 0 (mod q), & if r ≡ s ∈ \{2, …, l − 1\}. \end{cases}

Lemma 25. For n ≥ 0 and k ∈ ℤ we have 1. b_{2n}(l, n + k) = b_{2n}(l, n − k),

2. b_{2n+1}(l, n + k + 1) = −b_{2n+1}(l, n − k). Proof. The result is obvious for n = 0, because b_{0}(l, m) = b_{l}(0, −m) and

b_{0}(l, r) = \begin{cases}l, & r = kl; \\ 0, & otherwise. \end{cases}

For n ≥ 1 we get

b_{2n}(l, n + k) = ∑_{t=0}^{l−1} ω^{−t(n+k)}(1 − ω^{t})^{2n} = ∑_{t=0}^{l−1} ω^{−t(n+k)}(1 − 2ω^{t} + ω^{2t})^{n}

= ∑_{t=0}^{l−1} ω^{−t(n+k)}(ω^{t}\overline{ω}^{t} − 2ω^{t} + ω^{2t})^{n} = ∑_{t=0}^{l−1} ω^{−tk}(ω^{t} + \overline{ω}^{t} − 2)^{n}.

Since b_{2n}(l, n + k) ∈ ℤ and ω^{t} + \overline{ω}^{t} − 2 ∈ ℝ, so

b_{2n}(l, n + k) = \overline{b_{l}(2n, n + k)} = ∑_{t=0}^{l−1} ω^{tk}(ω^{t} + \overline{ω}^{t} − 2)^{n} = b_{2n}(l, n − k).

By Lemma 21 and just proved formula we get

b_{2n+1}(l, n + k + 1) = b_{2n}(l, n + k + 1) − b_{2n}(l, n + k)
= b_{2n}(l, n − k − 1) − b_{2n}(l, n − k)
= −(b_{2n}(l, n − k) − b_{2n}(l, n − k − 1)) = −b_{2n+1}(l, n − k),

so the result follows. Corollary 26. For n ≥ 0 we have b_{n}(l, n) = (−1)^{n}b_{n}(l, 0). Lemma 27. If l is even then (−1)^{r}b_{n}(l, r) > 0 for n ≥ 0. Proof. If l is even then

(−1)^{r}b_{n}(l, r) = (−1)^{r}l ∑_{s≡r (mod l)}(−1)^{s}\binom{n}{s} = (−1)^{r}l ∑_{s≡r (mod l)}(−1)^{r}\binom{n}{s}

= l ∑_{s≡r (mod l)} \binom{n}{s} > 0.

Lemma 28. If l is odd and \frac{n−2r}{l} ∈ 2ℕ + 1 then b_{n}(l, r) = 0.

Proof. Assume that \frac{n−2r}{l} = 2k + 1. It follows that n − 1 is even, so by Lemma 25 with k = r − \frac{n−1}{2} we get that

b_{n−1}(l, r) = b_{n−1}(l, n − 1 − r).

By Lemma 21 we have

b_{n−1}(l, r − 1) = b_{n−1}(l, n − 1 − r + (2r − n))
= b_{n−1}(l, n − 1 − r − (2k + 1)l) = b_{n−1}(l, n − 1 − r)

hence by Lemma 25 we get

b_{n}(l, r) = b_{n−1}(l, r) − b_{n−1}(l, r − 1)
= b_{n−1}(l, n − 1 − r) − b_{n−1}(l, n − 1 − r) = 0.

We will finish this paper with the result obtained in [17].

Theorem 29. Assume that l is odd. Then for n ≥ l − 1

(−1)^{r}b_{n}(l, r) \begin{cases}= 0, & if \frac{n−2r}{l} ∈ 2ℕ + 1; \\ > 0, & if \frac{n−2r}{l} ∈ (4k − 1, 4k + 1); \\ < 0, & if \frac{n−2r}{l} ∈ (4k + 1, 4k + 3). \end{cases}

Proof. We will use the induction with respect to n. Let n = l − 1. Observe that since l is odd hence \frac{n−2r}{l} cannot be an odd number. By definition

(−1)^{r}b_{l−1}(l, r) = (−1)^{s+r}l\binom{l − 1}{s} = (−1)^{s−r}l\binom{l − 1}{s},

where s ∈ \{0, …, l − 1\} is such that s ≡ r (mod l). If l is odd then (−1)^{s−r} = (−1)^{\frac{r−s}{l}}, so

(−1)^{r}b_{l}(l − 1, r) > 0 ⇔ \frac{r − s}{l} ∈ 2ℕ ⇔ [\frac{r}{l}] ∈ 2ℕ

\frac{r}{l} ∈ [2m, 2m + 1) ⇔ \frac{l − 1 − 2r}{l} ∈ (−4m − 1 − \frac{1}{l}, −4m + 1 − \frac{1}{l}] .

Since l − 1 is even, so

\frac{l − 1 − 2r}{l} ∉ (−4m − 1 − \frac{1}{l}, −4m − 1 + \frac{1}{l}),

hence

\frac{l − 1 − 2r}{l} ∈ (−4m − 1 − \frac{1}{l}, −4m + 1 − \frac{1}{l}] ⇔ \frac{l − 1 − 2r}{l} ∈ (−4m − 1, −4m + 1).

Similarly,

(−1)^{r}b_{l−1}(l, r) < 0 ⇔ \frac{l − 1 − 2r}{l} ∈ (−4m + 1 − \frac{1}{l}, −4m + 3 − \frac{1}{l}]

⇔ \frac{l − 1 − 2r}{l} ∈ (−4m + 1, −4m + 3),

so the result is true for n = l − 1.

Assume that the conclusion is true for n − 1. We consider three cases. If \frac{n−2r}{l} = 2k + 1 then it follows by Lemma 28 that b_{n}(l, r) = 0.

Let \frac{n−2r}{l} ∈ (4k − 1, 4k + 1). Then the numbers

\frac{(n − 1) − 2(r − 1)}{l} = \frac{n − 2r}{l} + \frac{1}{l}, \frac{(n − 1) − 2r}{l} = \frac{n − 2r}{l} − \frac{1}{l}

lie in the interval [4k − 1, 4k + 1] and at least one of them is in the interior of [4k − 1, 4k + 1]. It follows by the inductive step that

(−1)^{r−1}b_{n−1}(l, r − 1) ≥ 0, (−1)^{r}b_{n−1}(l, r) ≥ 0

and at most one of them is an equality. Hence

(−1)^{r}b_{n}(l, r) = (−1)^{r}b_{n−1}(l, r) + (−1)^{r−1}b_{n−1}(l, r − 1) > 0.

In a similar way, for \frac{n−2r}{l} ∈ (4k + 1, 4k + 3), we get that

(−1)^{r}b_{n}(l, r) = (−1)^{r}b_{n−1}(l, r) + (−1)^{r−1}b_{n−1}(l, r − 1) < 0.

Corollary 30. Let l ≥ 2. Then b_{n}(l, 0) = 0 if and only if l is odd and \frac{n}{l} ∈ 2ℕ + 1.

References

[1] A. Barbulescu and D. Savin, Some congruences of Fibonacci and Lucas numbers and properties of Fibonacci functions, in N. E. Mastorakis and Z. Bojkovic, eds., Recent Researches in Applied Mathematics and Informatics, WSEAS Press, 2011, pp. 129–133.

[2] L. Carlitz, A special congruence, Proc. Amer. Math. Soc. 4 (1953), 933–936.

[3] I. Chalendar and K. Kellay, T. Ransford, Binomial sums, moments and invariant subspaces, Israel J. Math. 115 (2000), 303–320.

[4] L. E. Dickson, History of the Theory of Numbers, Vol. I, AMS Chelsea Publ., 1999.

[5] B.-S. Du, A simple method which generates infinitely many congruence identities, Fibonacci Quart. 27 (1989), 116–124.

[6] B.-S. Du, S.-S. Huang, and M.-C. Li, Generalized Fermat, Double Fermat and Newton Sequences J. Number Theory 98 (2003), 172–183.

[7] J. Franks, Homology and Dynamical Systems, CBMS Regional Conference Series in Mathematics, No. 49, American Mathematical Society, 1982.

[8] I. M. Gessel and T. Lengyel, On the order of Stirling numbers and alternating binomial coefficient sums, Fibonacci Quart. 39 (2001), 444–454.

[9] F. S. Gillespie, A generalization of Fermat’s little theorem, Fibonacci Quart. 27 (1989), 109-115.

[10] A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers, in Organic Mathematics, CBMS Conf. Proc., 20, American Math. Society, 1997, pp. 253–276.

[11] J. Jezierski and W. Marzantowicz, Homotopy Methods in Topological Fixed and Periodic Point Theory, Springer, 2006.

[12] R. Keskin and B. Demirturk, Fibonacci and Lucas congruences and its applications, Acta Math. Sin (Engl. Ser.) 27 (2011), 725–736.

[13] R. Keskin and Z. Yosma, On Fibonacci and Lucas numbers of the form cx^{2}, J. Integer Seq. 14 (2011), Article 11.9.3.

[14] J. Mashreghi and T. Ransford, Binomial sums and functions of exponential type, Bull. Lond. Math. Soc. 37 (2005), 15–24.

[15] W. Marzantowicz and K. Wójcik, Periodic segment implies infinitelly many periodic solutions, Proc. Amer. Math. Soc. 135 (2007), 2637–2647.

[16] H. Prodinger, Some information about binomial transform, Fibonacci Quart. 32 (1994), 412–415.

[17] L. Pienia̧żek and K. Wójcik, Complicated dynamics in non-autonomous ODE’s, Univ. Iag. Acta Math. 41 (2003), 163–179.

[18] A. Rotkiewicz, Problems on Fibonacci numbers and their generalizations, in G. E. Bergum, A. N. Philippou, and A. F. Horadam, eds., Fibonacci Numbers and Their Applications, D. Reidel Publishing Company, 1986, pp. 241–255.

[19] R. Srzednicki and K. Wójcik, A geometric method for detecting chaotic dynamics, J. Differential Equations 135 (1997), 66–82.

[20] R. Srzednicki, K. Wójcik, and P. Zgliczyński, Fixed point results based on Ważewski method, in R. Brown, M. Furi, L. Górniewicz, and B. Jiang, eds., Handbook of Topological Fixed Point Theory, Kluwer, 2004, pp. 903–941.

[21] Zhi-Wei Sun, On the sum ∑_{k≡r (mod m)} \binom{n}{k} and related congruences, Israel J. Math. 128 (2002), 135–156.

[22] Zhi-Wei Sun and R. Tauraso, Congruences for sums of binomial coefficients, J. Number Theory 126 (2007), 287–296.

[23] C. S. Weisman, Some congruences for binomial coefficients, Michigan Math. J. 24 (1977), 141–151.

[24] H. S. Wilf, Generatingfunctionology, 2nd edition, Academic Press, 1994.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11A07. Keywords: binomial transform, trace, Lefschetz number, integer matrix, congruence.

Received September 18 2014; revised versions received September 21 2014; December 13 2014. Published in Journal of Integer Sequences, December 14 2014.

Return to Journal of Integer Sequences home page.