\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \def\modd#1 #2{#1\ ({\rm mod}\ #2)} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Binomial Transform and Dold Sequences } \vskip 1cm \large Klaudiusz W\'ojcik\\ Department of Mathematics and Computer Science \\ Jagiellonian University \\ {\L}ojasiewicza 6 \\ 30-348 Krak\'ow \\ Poland \\ \href{mailto:Klaudiusz.Wojcik@uj.edu.pl}{\tt Klaudiusz.Wojcik@uj.edu.pl} \end{center} \vskip .2 in \begin{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$. \end{abstract} \section{Introduction} Let $a=( a_n )_{n\geq 0}$ be a sequence of complex numbers. The {\it binomial transform} of the sequence $a$ is the sequence $T(a)= ( T(a)_n )_{n\geq 0}$ defined in \cite{P} by $$ T(a)_n =\sum_{i=0}^n (-1)^i \binom{ n}{ i} a_i, \quad n\geq 0. $$ The binomial transform is a linear involution and the original sequence $a$ can be recovered from the relation $$ a_n =\sum_{i=0}^n (-1)^i \binom{n }{ i} T(a)_i, \quad n\geq 0. $$ We say that a sequence of integers $a=( a_n )_{n\geq 0}$ is a {\it Dold sequence} \cite{JM} if \begin{equation}\label{eqdold} \sum_{k|n}\mu (k) a_{n/k} \equiv 0 \pmod{n}, \quad n\geq 1, \end{equation} where $\mu:\mathbb N\to \mathbb Z$ is the M\"{o}bius function given by $$ \mu (n)= \begin{cases} 1, & \text{if $n=1$;} \\ (-1)^k, & \text{if $n=p_1 \cdots p_k$, $p_i$, distinct primes;} \\ 0, & \text{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, \alpha$ such that $\gcd (p,m)=1$ we have $$ a_{mp^{\alpha}}\equiv a_{mp^{\alpha-1}}\pmod{p^{\alpha}}. $$ We will say that a sequence of integers $a$ is a {\it weak Dold sequence} if for every prime number $p$ $$ a_p \equiv a_1 \pmod{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 \cite{JM}. 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 {\it Lefschetz sequence} if there exist a compact ENR (i.e., Euclidean neighborhood retract) $X$ and a continuous map $f:X\to 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)=\sum_{k\geq 0} (-1)^k {\rm tr}\, H_k (f), $$ where $H_k (f):H_k (X)\to H_k (X)$ is the endomorphism induced by $f$ on the $k$-th singular homology of $X$ (with rational coefficients). One can prove \cite{JM} that a Dold sequence $a=( a_n )_{n\geq 1}$ is a Lefschetz sequence if and only if there are integer matrices $A\in M_k (\mathbb Z)$, $B\in M_m (\mathbb Z)$ such that $$ a_n ={\rm tr}\, A^n - {\rm tr}\, B^n, \quad n\geq 1. $$ In the sequel we will treat a Lefschetz sequence $a=( a_n)_{n\geq 1}$ as a sequence $a=( a_n )_{n\geq 0}$ with $$ a_0 ={\rm tr}\, A^0 - {\rm tr}\, B^0. $$ If $a$ is a Lefschetz sequence with $B=0$ then we call it a {\it sequence of traces} of integer matrix, i.e., $a_n={\rm 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~\ref{ds}). The proof of Theorem~\ref{ds} 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= \sum_{i=1}^n (-1)^i \binom{n}{i} {\rm tr}\, A^i= {\rm 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|\leq k \rho^n$, where $\rho$ is the spectral radius of $H(f)$ and $k$ is a dimension of $H(X)$. In particular, the sequence $a_n=\sum_{k|n} k^k$ cannot be obtained as a Lefschetz sequence although it is Dold sequence \cite{JM}. 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\neq 6$ then $T(a)$ is unbounded (Theorem~\ref{per6}). 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 \cite{SW,SWZ,MW,PW}. The above method gives a sufficient conditions for the existence of the compact invariant set $I$ for the Poincar\'e map $P$ such that $P$ restricted to $I$ is semi-conjugated to the shift map $\sigma: \Sigma_2\to \Sigma_2$ where $\Sigma_2=\{ 0,1\}^{\mathbb Z}$ i.e., there is a continuous surjective map $g:I\to \Sigma_2$ such that $g\circ P|_I=\sigma \circ g$. The important dynamical question is if for $n$-periodic sequence $c\in \Sigma_2$ there exists $n$-periodic point $x$ of the Poincar\'e map $P$ such that $x\in g^{-1}(c)$, i.e., trajectory of $x$ is coded by the sequence $c$. In the context of results in \cite{SWZ} it appears that there is a Dold sequence $a$ with the property that $T(a)_k\neq 0$ implies that $g^{-1}(c)$ contains $n$-periodic point of $P$ for every $n$-periodic sequence $c\in \Sigma_2$ with $k$-symbols $1$. Our Theorem~\ref{per6} guarantees the existence of infinitely many periodic points of the Poincar\'e 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 \cite{DHL,R}, the generalized $k$-Fibonacci sequences \cite{D1}, sequences generated by Lucas functions \cite{D,DHL}, and sequences generated by Tchebycheff polynomials of the first kind \cite{DHL,Gi}. In particular, the classical Lucas sequence $L$ given by $$ L_n= \left( \frac{1+\sqrt{5}}{2}\right)^n + \left( \frac{1-\sqrt{5}}{2}\right)^n, $$ is a Dold sequence (even sequence of traces with the matrix $ A= \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right] $) and the following congruences \begin{enumerate} \item if $p$ is odd prime then $L_{2p}\equiv 3$ (mod $p$), \item for $k\geq 1$ we have $L_{2^k}\equiv 3$ (mod $4$). \item if $r\geq 2$ then $L_{2^r}\equiv 7$ (mod $8$). \end{enumerate} considered by the authors in \cite{BS,KD,KY} easily follow by Eq.~(\ref{eqdold}). We will finish this paper with the results concerning the sequences of the form $$ a_n (l,r)= \sum_{s\equiv \modd{r} {l}} (-1)^s \binom{n }{ s}, \quad b_n (l,r)=l a_n (l,r),\quad n\geq 0. $$ where $l\geq 2$ and $r\in \{ 0,\ldots, l-1\}$ are fixed. The congruences related to these sequences were studied in \cite{S,ST}. As the application of Theorem~\ref{ds} we get that for $l\geq 2$ and $r\in \{ 0,\ldots, l-1\}$ the sequence $ b (l,r) $ is a Dold sequence exactly if one of the following conditions holds \begin{enumerate} \item $l\geq 2$ and $r=0$, \item $l=2r$ and $r\geq 1$. \end{enumerate} We also show that $a_n (l,0)=0$ if and only if $l$ is odd and $\frac{n}{l}\in 2\mathbb N+1$. It is easy to check that if $a$ is $l$-periodic then $T(a)_n=\sum_{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), \quad n\geq 0. $$ \section{Main results.} \begin{lemma} 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. \end{lemma} \begin{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,\quad T(a)_2=a_0-2a_1+a_2, $$ and $a_1\equiv \modd{a_2} {2}$ so $$ T(a)_2\equiv a_0+a_2\equiv a_0+a_1\equiv a_0-a_2 \equiv \modd{T(a)_1} {2} . $$ Let $p$ be odd prime. Then $$ T(a)_p=\sum_{i=0}^p (-1)^i \binom{p}{i}a_i \equiv a_0 -a_p \equiv a_0-a_1 \equiv \modd{T(a)_1} {p}, $$ because $p| \binom{p}{i}$ for $i=1,\ldots, p-1$. \end{proof} \begin{lemma}\label{dirichlet} Let $a$ be a $l$-periodic weak Dold sequence $(l\geq 2)$. If $\gcd (n,l)=1$ then $a_n=a_1$. \end{lemma} \begin{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\equiv \modd{a_1} {p}. $$ Hence $p| a_n-a_1$ and consequently $a_n=a_1$. \end{proof} \begin{corollary}\label{corperdold} Let $a$ be a $l$-periodic weak Dold sequence with $l$ prime. Then $$ T(a)_n= a_n (l,0) (a_0 -a_1), \quad n\geq 0, $$ where $a_n (l,0)= \sum_{s\equiv \modd{0} {l}} (-1)^s \binom{n}{ s}$. \end{corollary} \begin{proof} It follows by Lemma~\ref{dirichlet} that the $l$-periodic sequence $a$ has the form $$ a_1=\ldots =a_{l-1},\quad a_0=a_l, $$ hence \begin{align*} T(a)_n &=\left( \sum_{s\equiv \modd{0} {l}} (-1)^s \binom{n}{ s}\right) a_0 +\left( \sum_{s\not\equiv \modd{0} {l}} (-1)^s \binom{n}{ s}\right) a_1\\ &=a_n (l,0) (a_0-a_1) \end{align*} because $\sum_{s=0}^n (-1)^s \binom{n}{s}=0$. \end{proof} We recall the characterization of Dold sequences given in \cite{DHL}. Let us note that Dold sequence in \cite{DHL} is called a generalized Fermat sequence. Let $c= ( c_n )_{n\geq 1}$ be a sequence of integers. We say that sequence $a$ is {\it a Newton sequence} generated by $c$ if $$ a_n=c_1 a_{n-1}+c_2 a_{n-2}+\cdots + c_{n-1}a_1 +nc_n, \quad n\geq 1. $$ \begin{remark} Assume that $c$ is a finite sequence, i.e., there exists $m\geq 1$ such that $c_n=0$ for $n>m$. One can check \cite{DHL} that then $$ a_n={\rm tr}\, M_m^n, \quad n\geq 1 $$ where $M_m$ is the companion matrix of the polynomial $x^m - c_1 x^{m-1}- c_2 x^{m-2} -\cdots - c_{m-1}x -c_m$, i.e., $$ M_m =\left[ \begin{array}{ccccc} 0 & 0 & \cdots & 0 & c_m \\ 1 & 0 & \cdots & 0 & c_{m-1} \\ 0 & 1 & \cdots & 0 & c_{m-2} \\ \vdots & 0 & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & c_1 \\ \end{array} \right]\in M_{m}(\mathbb Z) $$ \end{remark} \begin{proposition} Let $a= ( a_n )_{n\geq 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$. \end{proposition} \begin{proof} It follows by \cite[Thm.~5, Thm.~6]{DHL}. \end{proof} \begin{lemma}\label{newton} Let $a=( a_n )_{n\geq 1}$ be a sequence of integers. Then $a$ is a Dold sequence if and only if for every $m\geq 1$ there exists a matrix $A_m \in M_m (\mathbb Z)$ such that $$ a_n={\rm tr}\, A_m^n, \quad 1\leq n\leq m. $$ \end{lemma} \begin{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\geq 1$ be fixed. Let us consider a finite sequence $c(m)$ such that $$ c(m)_n= \begin{cases} c_n, & \text{if $1\leq n\leq m$;} \\ 0, & \text{otherwise.} \end{cases} $$ Let $b$ be a Newton sequence generated by $c(m)$. Then $$ b_n ={\rm tr}\, M_m^n, \quad n\geq 1, $$ and $a_n=b_n$ for $1\leq n\leq 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\geq 1$ be fixed. We show that $$ \sum_{k|m}\mu (k)a_{m/k}\equiv 0 \pmod{m}. $$ By assumption there exists a matrix $A_m\in M_m (\mathbb Z)$ such that $$ a_n={\rm tr}\, M_m^n, \quad 1\leq n\leq m. $$ Let $b$ be a sequence defined by $b_n={\rm tr}\, A_m^n$, $n\geq 1$. Then $b$ is a Dold sequence and $a_n=b_n$ for $1\leq n\leq m$. In particular, $$ \sum_{k|m}\mu (k)a_{m/k}=\sum_{k|m}\mu (k)b_{m/k}\equiv \modd{0} {m} , $$ so the proof is complete. \end{proof} \begin{theorem}\label{ds} Assume that $a=( a_n )_{n\geq 0}$ is a sequence of integers. Then $a$ is a Dold sequence if and only if $T(a)$ is a Dold sequence. \end{theorem} \begin{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\geq 2$ be fixed. We have to show that $$ \sum_{k|m} \mu(k) T(a)_{m/k}\equiv 0 \pmod{m}. $$ By Lemma~\ref{newton} there exists a matrix $A_m\in M_m (\mathbb Z)$ such that $$ a_n ={\rm tr}\, A_m^n, \quad 1\leq n\leq m. $$ Let $\tilde{a}$ be a sequence defined by $$ \tilde{a}_n ={\rm tr}\, A_m^n. $$ Then $$ a_1=\tilde{a}_1, \quad a_m=\tilde{a}_m, \quad \tilde{a}_0=m, $$ and $T(\tilde{a})$ is a Dold sequence given by $$ T(\tilde{a})_n={\rm tr}\, (I-A_m)^n, \quad n\geq 0. $$ In particular, $$ \sum_{k|m} \mu(k) T(\tilde{a})_{m/k}\equiv 0 \pmod{m}. $$ Let $1\leq n\leq m$. Then $$ T(\tilde{a})_m=\sum_{i=0}^n (-1)^i \binom{n}{i} \tilde{a}_i =m-a_0 +\sum_{i=0}^n (-1)^i \binom{n}{i} a_i=m-a_0 +T(a)_m. $$ Consequently, we get that \begin{align*} \sum_{k|m} \mu(k) T(a)_{m/k} &= \sum_{k|m} \mu(k) T(\tilde{a})_{m/k}+ (m-a_0)\left( \sum_{k|m}\mu (k)\right) \\ &= \sum_{k|m} \mu(k) T(\tilde{a})_{m/k}\equiv 0 \pmod{m}, \end{align*} because $\sum_{k|m} \mu (k)=0$ for $m\geq 2$. The proof is complete since $m\geq 2$ was arbitrary. \end{proof} Let $a$ be a Lefschetz sequence with matrices $A$ and $B$. We call a complex number $\lambda \in \mathbb C$ {\it an essential eigenvalue} of the pair $(A,B)$ if the algebraic multiplicity of $\lambda$ as the eigenvalue of $A$ is different from the algebraic multiplicity of $\lambda$ as the eigenvalue of $B$. By $\sigma_{\rm ess}(A,B)$ we denote the set of all essential eigenvalues of $(A,B)$. Let $\rho_{\rm ess}:=\rho_{\rm ess}(A,B)$ be the {\it essential spectral radius} of $(A,B)$, i.e., $$ \rho_{\rm ess}=\max \{ |\lambda|: \lambda\in \sigma_{\rm ess}(A,B)\}. $$ \begin{remark} Assume that a Dold sequence $a=( a_n )_{n\geq 0}$ is bounded. It follows by \cite[Theorem 3.1.26]{JM} that $a$ is a periodic Lefschetz sequence with $l$-periodic matrices $A$ and $B$. We treat $a$ as the sequence $( a_n )_{n\geq 0}$ with $a_0={\rm tr}\, A^0-{\rm tr}\, B^0$. Then $a_0=a_l$ and binomial transform of $a$ is given by $$ T(a)_n={\rm tr}\, (I-A)^n -{\rm tr}\, (I-B)^n,\quad n\geq 0. $$ \end{remark} \begin{theorem}\label{per6} If $a$ is a Dold sequence and $a$, $T(a)$ are bounded then $( a_n )_{n\geq 1}$, $( T(a) )_{n\geq 1}$ are $6$-periodic. \end{theorem} \begin{proof} Since $a$ is bounded Dold sequence, it follows by \cite[Theorem 3.1.26]{JM} that $a$ is $l$-periodic Lefschetz sequence with $l$-periodic matrices $A$, $B$ (i.e., $A^l=I_k$, $A^l=I_m$). In particular, $$ \sigma (A), \sigma (B)\subset \{ 1,\omega, \ldots, \omega^{l-1}\}, $$ where $\omega=e^{\frac{ 2\pi i}{l}}$ is a primitive root of unity. We treat $a$ as a sequence $$ a_n ={\rm tr}\, A^n -{\rm tr}\, B^n, \quad n\geq 0, $$ so $$ T(a)_n ={\rm tr}\, (I-A)^n - {\rm tr}\, (I-B)^n, \quad n\geq 0. $$ Observe that $\lambda \in \sigma_{\rm ess} (A,B)$ if and only if $1-\lambda \in \sigma_{\rm ess}(I-A,I-B)$ and $T(a)$ is periodic, because it is a bounded Dold sequence. Let $1-\lambda \in \sigma_{\rm ess}(I-A,I-B)\cap \mathbb S^1$. Then $|\lambda|=|1-\lambda|=1$, so one can easily check that $\lambda=e^{\pm \frac{\pi i}{ 3}}$. Observe that then $1-\lambda =\overline{\lambda}$. It follows that $$ \sigma_{\rm ess} (A,B)\cap (\mathbb S^1 \setminus \{ 1\})= \sigma_{\rm ess}(I-A,I-B)\cap \mathbb S^1\subset \{ e^{\pm \frac{\pi i}{ 3}} \}. $$ Suppose that $\rho:=\rho_{\rm ess}(I-A,I-B)>1$. Then there exists exactly one pair $\lambda, \overline{\lambda}\in \{ 1,\omega, \ldots, \omega^{l-1}\}$ such that $$ |1-\lambda|=|1-\overline{\lambda}|=\rho. $$ Then $$ \lim_{n\to \infty}\frac{T(a)_n}{\rho^n}=g\neq 0, $$ so $T(a)$ is unbounded, a contradiction. So we get that $\rho \leq 1$. We show that $$ \sigma_{\rm ess}(I-A,I-B)\subset \{ 0, e^{\pm \frac{\pi i}{ 3}} \}. $$ We have that $$ T(a)_n=\sum_{1-\lambda\in \sigma_{\rm ess}(I-A,I-B)\cap \{ 0, e^{\pm \frac{\pi i}{ 3}} \}} (1-\lambda)^n + \sum_{ 1-\lambda\in \sigma_{\rm ess}(I-A,I-B)\cap \{ z: 0<|z|<1\} }(1-\lambda)^n, $$ so the sequence $$ \sum_{ 1-\lambda\in \sigma_{\rm ess}(I-A,I-B)\cap \{ z: 0<|z|<1\} }(1-\lambda)^n $$ is the periodic integer sequence that converge to $0$, so we get that $$\sigma_{\rm ess}(I-A,I-B)\cap \{ z: 0<|z|<1\} =\emptyset.$$ \end{proof} \begin{corollary} If $a$ is $l$-periodic (non-constant) Dold sequence with $l\neq 6$ then $T(a)$ is unbounded. \end{corollary} \section{Applications to binomial sums} Assume that $l\geq 2$ and $r\in \mathbb Z$. We define the $l$-periodic sequence $a[l,r]=( a_n [l,r] )_{n\geq 0}$ by $$ a_n [l,r]= \begin{cases} 1, & \text{if $n \equiv r$ (mod $l$);} \\ 0, & \text{otherwise.} \end{cases} $$ Then $a(l,r)=( a_n (l,r) )_{n\geq 0}= T(a[l,r])$ is its binomial transform where $$ a_n (l,r)= \sum_{ s\equiv r \pmod{l}}(-1)^s \binom{n}{s}, \quad n\geq 0. $$ We define $$ b[l,r]:=l a[l,r], \quad b (l,r):=la (l,r). $$ \begin{remark} It follows by Corollary \ref{corperdold} we have $$ T(a)= a (l,0) (a_0 -a_1), \quad n\geq 0, $$ if $a$ is $l$-periodic Dold sequence with $l$ prime. Moreover, by Eq.~(\ref{eqdold}) $$ a_0=a_l\equiv \modd{a_1} {l}, $$ so $T(a)=k b(l,0)$ for some $k\in \mathbb{Z}$. \end{remark} \begin{remark} The sequence $b(l,r)$ is particularly interesting from the point of view of applications in the detection of chaotic dynamics \cite{SW,SWZ}. 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\'e mapping associated with the periodic in time ordinary differential equations \cite{MW,PW}. More specifically, let $P$ be the Poincar\'e map for the planar periodic equation $$ \dot{z}=\overline{z}^k (1+|z|^2e^{i\kappa t}),\quad z\in \mathbb{C}. $$ For sufficiently small $\kappa>0$ there exist a compact invariant set $I$ for $P$ and a continuous surjective map $g:I\to \Sigma_2$ such that $$ g\circ (P|_I)=\sigma \circ g, $$ where $\sigma:\Sigma_2\to \Sigma_2$ is the shift map \cite{SWZ}. It follows by \cite{SWZ} that if $b_n (k+1,0)\neq 0$ and $c\in \Sigma_2$ is $m$-periodic sequence with $n$-symbols $1$ then the Poincar\'e map $P$ has $m$-periodic point $x\in I$ such that $g(x)=c$. \end{remark} In this section we apply Theorem~\ref{ds} to prove that for $l\geq 2$ and $r\in \{ 0,\ldots, l-1\}$ the sequence $ b (l,r) $ is a Dold sequence if and only if $l\geq 2$ and $r=0$ or $l=2r$ and $r\geq 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$. \begin{remark} Let us observe that $$ b_n (l,r)= \sum_{t=0}^{l-1}\omega^{-tr}(1-\omega^t)^n, \quad n\geq 0, $$ where $\omega = e^{\frac{2\pi i}{l}}$ is a primitive $l$-root of unity. Indeed, it is well-known that $$ \sum_{t=0}^{l-1} \omega^{ts}= \begin{cases} l, & \text{if $l|s$;} \\ 0, & \text{otherwise.} \end{cases} $$ so we get that \begin{align*} \sum_{t=0}^{l-1}\omega^{-tr}(1-\omega^t)^n &=\sum_{t=0}^{l-1}\omega^{-tr}\sum_{k=0}^{n}(-1)^{n-k} \binom{n}{n-k}\omega^{t(n-k)}\\ &=\sum_{k=0}^{n}(-1)^{n-k} \binom{n}{n-k} \left( \sum_{t=0}^{l-1} \omega^{t(n-k-r)}\right)\\ &=\sum_{s=0}^n (-1)^s \binom{n}{s}\left( \sum_{t=0}^{l-1}\omega^{t(s-r)}\right)=b_n (l,r). \end{align*} \end{remark} \begin{theorem}\label{main2} The sequence $b (l,0)=( b_n (l,0) )_{n\geq 0}$ is a sequence of traces. In particular, $b (l,0)$ is a Dold sequence. \end{theorem} \begin{proof} Let $l\geq 2$ and $\omega=e^{\frac{2\pi i }{l}}$. We consider the matrix $A_l\in M_{l}(\mathbb Z)$ given by $$ A_l=\left[ \begin{array}{ccccc} 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & 0 & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \\ \end{array} \right]\in M_{l}(\mathbb Z). $$ One can check that $A_l$ has eigenvalues $1,\omega, \ldots, \omega^{l-1}$, hence $$ {\rm tr}\, (I-A_l)^n=\sum_{t=0}^{l-1}(1-\omega^t)^n =b_n (l,0). $$ \end{proof} \begin{theorem}\label{key1} Let $l\geq 2$ and $r\in \{1,\ldots, l-1\}$. The sequence $b (l,r)$ is a Dold sequence if and only if $l=2r$. \end{theorem} \begin{lemma}\label{l1} If $l=2r$ then $b (2r,r)$ is a Dold sequence (even a Lefschetz sequence). \end{lemma} \begin{proof} For $l=2r$ and $\omega=e^{\frac{2\pi i}{l}}$ we have \begin{align*} b_n (2r,r)&=\sum_{t=0}^{l-1} \omega^{-tr}(1-\omega^t)^n= \sum_{t=0}^{l-1} (-1)^t (1-\omega^t)^n\\ &= \sum_{t\; {\rm even}} (1-\omega^t)^n - \sum_{t\; {\rm odd}} (1-\omega^t)^n. \end{align*} Let us observe that $1,\omega^2,\ldots, \omega^{l-2}$ are roots of the polynomial $\lambda^r-1=0$ and the eigenvalues of the matrix $$ A=\left[ \begin{array}{ccccc} 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & 0 & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \\ \end{array} \right]\in M_{r}(\mathbb Z) $$ and $\omega, \omega^3,\ldots, \omega^{l-1}$ are roots of the polynomial $\lambda^r+1=0$ and the eigenvalues of the matrix $$ B=\left[ \begin{array}{ccccc} 0 & 0 & \cdots & 0 & -1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & 0 & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \\ \end{array} \right]\in M_{r}(\mathbb Z) $$ hence $$ b_n (2r,r)={\rm tr}\, (I-A)^n -{\rm tr}\, (I-B)^n, $$ so $b (2r,r)$ is a Dold sequence (even Lefschetz sequence). \end{proof} \begin{remark}\label{bertrand} If $n>2$ then there exists a prime number $p2$ and $r\in \{ 1,\ldots, 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$. \end{lemma} \begin{proof} Assume that $l>2$. Since $b(l,r)=T(b[l,r])$, so by Theorem~\ref{ds} 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~\ref{dirichlet}, a contradiction. Let $r=1$. Then $b_1 [l,1]=l$ by definition. By Remark~\ref{bertrand} there is a prime number $p$ such that $p2$ and $r\in \{ 1,\ldots, l-1\}$. If $b (l,r)$ is a Dold sequence then $r>1$ and $r|l$. \end{lemma} \begin{proof} Assume that $b (l,r)=l a (l,r)$ is a Dold sequence. We may assume that $\gcd (r,l)>1$. In particular, $2\leq r 2$ and $r\in \{ 1,\ldots, l-1\}$. If $b (l,r)$ is a Dold sequence then $l=2r$. \end{lemma} \begin{proof} It follows by Theorem~\ref{ds} that $b [l,r]$ is a Dold sequence. By Lemma~\ref{key} 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\in \{ 1, \ldots, r(m+1)-1\}\setminus \{ r\}$. Let $p1$ and $k\geq 1$ are such that $$ a_{k+1} (l,r)\equiv \begin{cases} 1\pmod{q}, & \text{if $r\equiv 0\pmod{l}$;} \\ -1\pmod{q}, & \text{if $r\equiv 1\pmod{l}$;} \\ 0\pmod{q}, & \text{if $r\equiv s\in \{ 2,\ldots, l-1\}$.} \end{cases} $$ Then for every $r\in \mathbb Z$ we have $$ a_{n+k} (l,r)\equiv a_{n}(l,r) \pmod{q}, \quad n>0. $$ \end{theorem} \begin{proof} We have $$ a_{1} (l,r)= \begin{cases} 1, & \text{$r\equiv 0\pmod{l}$;} \\ -1, & \text{$r\equiv 1\pmod{l}$;} \\ 0, & \text{otherwise,} \end{cases} $$ so the result holds for $n=1$. Assume that it holds for some $n\geq 1$. Then by inductive step and Lemma~\ref{lem1} we have \begin{align*} a_{n+1+k} (l,r)&=a_{n+k} (l,r)-a_{n+k} (l,r-1)\\ &\equiv a_{n} (l,r)-a_{n} (l,r-1)=a_{n+1}(l,r) \pmod{q}. \end{align*} \end{proof} \begin{example}[Glaisher] Assume that $p$ is prime and $b\geq 1$ is such that $p^b\equiv 1$ (mod $l$). Then for $k=p^b-1$ and $q=p$ we get $$ a_{n+p^b-1} (l,r)\equiv a_{n}(l,r) \pmod{p}. $$ In particular, for $l=p-1$ and $b=1$ we get Glaisher's congruence $$ a_{n+p-1} (p-1,r)\equiv a_{n}(p-1,r) \pmod{p}, \quad n>0. $$ \end{example} \begin{example} Assume that $q>1$ is an integer relatively prime to $l\in \mathbb Z^+$. Let $ q=\prod_{s=1}^{t} p_s^{\alpha_s}, $ where $p_1,\ldots, p_t$ are distinct primes and $\alpha_s\in \mathbb Z^+$. Put $$ \nu_l (q)=LCM \left( p_1^{\alpha_1-1}(p_1^{\beta_1}-1),\ldots, p_t^{\alpha_t-1}(p_t^{\beta_t}-1)\right), $$ where $\beta_s$ is the smallest positive integer with $p_s^{\beta_s}\equiv 1$ (mod $m$). Then we have \cite{ST} $$ a_{1+\nu_l (q)} (l,r)\equiv \begin{cases} 1\pmod{q}, & \text{if $r\equiv 0\pmod{l}$;} \\ -1\pmod{q}, & \text{if $r\equiv 1\pmod{l}$;} \\ 0\pmod{q}, & \text{if $r\equiv s\in \{ 2,\ldots, l-1\}$.} \end{cases} $$ \end{example} \begin{lemma}\label{lem2} For $n\geq 0$ and $k\in \mathbb Z$ we have \begin{enumerate} \item $b_{2n} (l,n+k)=b_{2n} (l,n-k)$, \item $b_{2n+1} (l,n+k+1)=-b_{2n+1} (l,n-k)$. \end{enumerate} \end{lemma} \begin{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, & \text{$r=kl$;} \\ 0, & \text{otherwise.} \end{cases} $$ For $n\geq 1$ we get \begin{align*} b_{2n} (l,n+k) &=\sum_{t=0}^{l-1} \omega^{-t(n+k)}(1-\omega^t)^{2n}= \sum_{t=0}^{l-1} \omega^{-t(n+k)}(1-2\omega^t+\omega^{2t})^{n}\\ &=\sum_{t=0}^{l-1} \omega^{-t(n+k)}(\omega^t \overline{\omega}^t-2\omega^t+\omega^{2t})^{n}= \sum_{t=0}^{l-1} \omega^{-tk}(\omega^t + \overline{\omega}^t-2)^{n}. \end{align*} Since $b_{2n} (l,n+k)\in \mathbb Z$ and $\omega^t + \overline{\omega}^t-2\in \mathbb R$, so $$ b_{2n} (l,n+k)=\overline{b_l (2n,n+k)}=\sum_{t=0}^{l-1} \omega^{tk}(\omega^t + \overline{\omega}^t-2)^{n}=b_{2n} (l,n-k). $$ By Lemma~\ref{lem1} and just proved formula we get \begin{align*} 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), \end{align*} so the result follows. \end{proof} \begin{corollary} For $n\geq 0$ we have $b_n (l,n)=(-1)^n b_n (l,0)$. \end{corollary} \begin{lemma}\label{lem4} If $l$ is even then $(-1)^r b_n (l,r)>0$ for $n\geq 0$. \end{lemma} \begin{proof} If $l$ is even then \begin{align*} (-1)^r b_n (l,r)&=(-1)^r l\sum_{s\equiv r \pmod{l}}(-1)^s \binom{n}{s}=(-1)^rl\sum_{s\equiv r \pmod{l}}(-1)^r \binom{n}{s}\\ &= l\sum_{s\equiv r \pmod{l}} \binom{n}{s}>0. \end{align*} \end{proof} \begin{lemma}\label{lem3} If $l$ is odd and $\frac{n-2r}{l}\in 2\mathbb N+1$ then $b_n (l,r)=0$. \end{lemma} \begin{proof} Assume that $\frac{n-2r}{l}=2k+1$. It follows that $n-1$ is even, so by Lemma~\ref{lem2} with $k = r-\frac{n-1}{2}$ we get that $$ b_{n-1} (l,r) = b_{n-1} (l,n-1-r). $$ By Lemma~\ref{lem1} we have \begin{align*} 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) \end{align*} hence by Lemma~\ref{lem2} we get \begin{align*} 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. \end{align*} \end{proof} We will finish this paper with the result obtained in \cite{PW}. \begin{theorem}\label{PW} Assume that $l$ is odd. Then for $n\geq l-1$ $$ (-1)^r b_n (l,r) \begin{cases} =0, & \text{if $\frac{n-2r}{l}\in 2\mathbb N+1$;} \\ >0, & \text{if $\frac{n-2r}{l}\in (4k-1,4k+1)$;} \\ <0, & \text{if $\frac{n-2r}{l}\in (4k+1,4k+3)$.} \end{cases} $$ \end{theorem} \begin{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\in \{ 0,\ldots, l-1\}$ is such that $s\equiv 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\Leftrightarrow \frac{r-s}{l}\in 2\mathbb N\Leftrightarrow \left[\frac{r}{l}\right]\in 2\mathbb N $$ $$ \frac{r}{l}\in [2m,2m+1)\Leftrightarrow \frac{l-1-2r}{l}\in \left( -4m-1-\frac{1}{l},-4m +1-\frac{1}{l}\right]. $$ Since $l-1$ is even, so $$ \frac{l-1-2r}{l}\notin (-4m-1-\frac{1}{l},-4m-1+\frac{1}{l}), $$ hence $$ \frac{l-1-2r}{l}\in \left( -4m-1-\frac{1}{l},-4m +1-\frac{1}{l}\right]\Leftrightarrow \frac{l-1-2r}{l}\in ( -4m-1,-4m +1). $$ Similarly, $$ (-1)^r b_{l-1} (l,r)<0\Leftrightarrow \frac{l-1-2r}{l}\in \left( -4m+1-\frac{1}{l},-4m+3-\frac{1}{l}\right] $$ $$ \Leftrightarrow \frac{l-1-2r}{l}\in ( -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~\ref{lem3} that $b_n (l,r)=0$. Let $\frac{n-2r}{l}\in (4k-1,4k+1)$. Then the numbers $$ \frac{(n-1)-2(r-1)}{l}=\frac{n-2r}{l}+\frac{1}{l},\quad \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) \geq 0,\quad (-1)^{r} b_{n-1} (l,r)\geq 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}\in (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. $$ \end{proof} \begin{corollary} Let $l\geq 2$. Then $b_n (l,0)=0$ if and only if $l$ is odd and $\frac{n}{l}\in 2\mathbb N+1$. \end{corollary} \bibliographystyle{amsplain} \begin{thebibliography}{10} \bibitem {BS} 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., {\it Recent Researches in Applied Mathematics and Informatics}, WSEAS Press, 2011, pp.~129--133. \bibitem {C} L. Carlitz, A special congruence, {\it Proc. Amer. Math. Soc.} {\bf 4} (1953), 933--936. \bibitem {CKR} I. Chalendar and K. Kellay, T. Ransford, Binomial sums, moments and invariant subspaces, {\it Israel J. Math.} {\bf 115} (2000), 303--320. \bibitem {D} L. E. Dickson, {\it History of the Theory of Numbers}, Vol.~I, AMS Chelsea Publ., 1999. \bibitem{D1} B.-S. Du, A simple method which generates infinitely many congruence identities, {\it Fibonacci Quart.} {\bf 27} (1989), 116--124. \bibitem {DHL} B.-S. Du, S.-S. Huang, and M.-C. Li, Generalized Fermat, Double Fermat and Newton Sequences {\it J. Number Theory} {\bf 98} (2003), 172--183. \bibitem {F} J. Franks, {\it Homology and Dynamical Systems}, CBMS Regional Conference Series in Mathematics, No.~49, American Mathematical Society, 1982. \bibitem {GL} I. M. Gessel and T. Lengyel, On the order of Stirling numbers and alternating binomial coefficient sums, {\it Fibonacci Quart.} {\bf 39} (2001), 444--454. \bibitem{Gi} F. S. Gillespie, A generalization of Fermat's little theorem, {\it Fibonacci Quart.} {\bf 27} (1989), 109-115. \bibitem {G} A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers, in {\it Organic Mathematics}, CBMS Conf. Proc., {\bf 20}, American Math. Society, 1997, pp.~253--276. \bibitem {JM} J. Jezierski and W. Marzantowicz, {\it Homotopy Methods in Topological Fixed and Periodic Point Theory}, Springer, 2006. \bibitem {KD} R. Keskin and B. Demirturk, Fibonacci and Lucas congruences and its applications, {\it Acta Math. Sin (Engl. Ser.)} {\bf 27} (2011), 725--736. \bibitem {KY} R. Keskin and Z. Yosma, On Fibonacci and Lucas numbers of the form $cx^2$, {\it J. Integer Seq.} {\bf 14} (2011), Article 11.9.3. \bibitem {MR} J. Mashreghi and T. Ransford, Binomial sums and functions of exponential type, {\it Bull. Lond. Math. Soc.} {\bf 37} (2005), 15--24. \bibitem{MW} W. Marzantowicz and K. W\'ojcik, Periodic segment implies infinitelly many periodic solutions, {\it Proc. Amer. Math. Soc.} {\bf 135} (2007), 2637--2647. \bibitem{P} H. Prodinger, Some information about binomial transform, {\it Fibonacci Quart.} {\bf 32} (1994), 412--415. \bibitem {PW} L. Pieni\c{a}\.zek and K. W\'ojcik, Complicated dynamics in non-autonomous ODE's, {\it Univ. Iag. Acta Math.} {\bf 41} (2003), 163--179. \bibitem {R} A. Rotkiewicz, Problems on Fibonacci numbers and their generalizations, in G. E. Bergum, A. N. Philippou, and A. F. Horadam, eds., {\it Fibonacci Numbers and Their Applications}, D. Reidel Publishing Company, 1986, pp.~241--255. \bibitem {SW} R. Srzednicki and K. W\'{o}jcik, A geometric method for detecting chaotic dynamics, {\it J. Differential Equations} {\bf 135} (1997), 66--82. \bibitem {SWZ} R. Srzednicki, K. W\'ojcik, and P. Zgliczy\'nski, Fixed point results based on Wa\.zewski method, in R. Brown, M. Furi, L. G\'orniewicz, and B. Jiang, eds., {\it Handbook of Topological Fixed Point Theory}, Kluwer, 2004, pp.~903--941. \bibitem {S} Zhi-Wei Sun, On the sum $\sum_{k\equiv r\, \pmod{m}}\binom{n}{k}$ and related congruences, {\it Israel J. Math.} {\bf 128} (2002), 135--156. \bibitem {ST} Zhi-Wei Sun and R. Tauraso, Congruences for sums of binomial coefficients, {\it J. Number Theory} {\bf 126} (2007), 287--296. \bibitem {We} C. S. Weisman, Some congruences for binomial coefficients, {\it Michigan Math. J.} {\bf 24} (1977), 141--151. \bibitem {W} H. S. Wilf, {\it Generatingfunctionology}, 2nd edition, Academic Press, 1994. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 11A07. \noindent \emph{Keywords: } binomial transform, trace, Lefschetz number, integer matrix, congruence. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 18 2014; revised versions received September 21 2014; December 13 2014. Published in {\it Journal of Integer Sequences}, December 14 2014. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .