\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}
\usepackage{enumitem}

\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}}}

\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 $p$-adic Properties of Lengyel's Numbers
}
\vskip 1cm
\large
D. Barsky\\
7 rue La Condamine\\
75017 Paris\\
France\\
\href{mailto:barsky.daniel@orange.fr}{\texttt{barsky.daniel@orange.fr}}\\
\ \\
J.-P. B\'ezivin\\
1, All\'ee Edouard Quincey\\
94200, Ivry-sur-Seine\\
France\\
\href{mailto:jp.bezivin@orange.fr}{\texttt{jp.bezivin@orange.fr}} \\
\end{center}

\vskip .2 in

\def\Q{\mathbb Q}
\def\C{\mathbb C}
\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\K{\mathbb K}
\def\R{\mathbb R}
\def\P{\mathbb P}
\def\L{\mathbb L}
\def\modd#1 #2{#1\ ({\rm mod}\ #2)}

\def\ds{\displaystyle}

\vskip .2 in

\begin{abstract}
Lengyel introduced a sequence of numbers $Z_n$, defined combinatorially,
that satisfy a recurrence where the coefficients are 
Stirling numbers of the second kind. He proved some $2$-adic properties
of these numbers. In this paper, we give another recurrence for the
sequence $Z_n$, where the coefficients are
Stirling numbers of the first kind. Using
this formula, we give another proof of Lengyel's lower bound on the
$2$-adic valuation of the $Z_n$. We also resolve some
conjectures of Lengyel about the sequence $Z_n$.

We  also define
\begin{enumerate}[label=(\alph*)]
\item A new sequence $Y_n$ analogous to $Z_n$,
exchanging the role of Stirling numbers of the 
first and second kind. We study its $2$-adic properties.
\item Another sequence similar to Lengyel's sequence, 
and we study its $p$-adic properties for $p\geq 3$. 
\end{enumerate}
\end{abstract}

\section{Introduction and notation\label{sec0}} 
In the text  $|.|$ denotes the  $p$-adic absolute value on  $\Q$, and $v_p$ denotes the corresponding $p$-adic valuation. Let  $\Q_p$ be the $p$-adic completion of $\Q$ and let $\C_p$ be the $p$-adic completion of an algebraic closure of $\Q_p$. For all the $p$-adic background, we refer to Amice \cite{AM}; in particular for a polynomial $P(x)\in \C_p[x]$ and
for $r\in\R_+$, we write  $\vert P\vert(r):=\sup_{\substack{x\in\C_p\\ \vert x\vert \leq r}}\vert P(x)\vert$. 

For an integer $n$, let  $S_p(n)$ be the sum of the digits of the $p$-adic expansion of $n$. Throughout this article, we use the following well-known formula (cf.\ Amice \cite[p.~102]{AM}):
\begin{equation}
 v_p(n!)=\frac{n-S_p(n)}{p-1}\, .\label{E0}
 \end{equation}
Lengyel \cite{LE} studied the  $2$-adic properties of the sequence
defined by  $Z_1=1$ and
\begin{equation}
Z_n=\sum_{k=1}^{n-1} S(n,k)Z_k \label{eq1}
 \end{equation}
 for $n \geq 2$,
where the  $S(n,k)$ are Stirling numbers of the second kind.  (See Lengyel  \cite{LE} for the combinatorial properties of the $Z_n$). This sequence appears in Sloane's database \cite{OEIS} as \seqnum{A005121}.  In particular Lengyel showed the following results:

\begin{theorem}\label{th1} The $Z_n$ satisfy
\begin{enumerate}[label=(\alph*)]
\item $\ds v_2(Z_{2^n+L})\geq n$ for
$n\geq 1$ and $L\geq 0$;
\item $\ds v_2(Z_k)\geq \lfloor\log_2(k)\rfloor -1$
for $k\geq 1$.  
 \end{enumerate}
 \end{theorem}

Lengyel also proposed some conjectures about these numbers;
first \cite[Conjecture 2]{LE}:
\begin{conjecture}\label{conj1} For $n\geq 3$, let $Z_n$ be given by
\eqref{eq1}. Then $\ds v_2(Z_{2^n})=n$. \end{conjecture}

He also proposed \cite[Conjecture 4]{LE}:
\begin{conjecture}\label{conj2} For all $n\geq 2$ we have
\begin{equation*}
{\rm max}\{k \, | \, v_2(Z_k)=n \}=3\cdot 2^{n-1} \, .
\end{equation*}
\end{conjecture}

\section{The results}
In this paper, we reprove the results of Lengyel by another method.
This method allows us to prove the above two conjectures. More
precisely we get the following theorems:

\begin{theorem}\label{th2} The lower bound
\begin{equation*}
v_2(Z_n)\geq \log_2(n)-1 
\end{equation*}
holds for all $n\geq 1$.
\end{theorem}

\begin{remark} The inequality in Theorem~\ref{th2} implies the
assertion  (a) of Theorem~\ref{th1} when $L\geq 1$, and the assertion
(b) of Theorem~\ref{th1}.
\end{remark}

\begin{theorem}\label{th3} If $t\geq 3$, then
\begin{equation*}
v_2(Z_{2^t})=t \, .
\end{equation*}
\end{theorem}
\begin{remark} This theorem proves Conjecture~\ref{conj1}; in addition,
it completes the assertion (a) of Theorem \ref{th1}, by showing that the
case $L=0$ of the assertion (a) holds.

\end{remark}

\begin{theorem}\label{th4} For all $t\geq 2$, we have
\begin{equation*}
{\rm max}\{k \, | \, v_2(Z_k)=t \}=3\cdot 2^{t-1} 
\end{equation*}
\end{theorem}
\noindent which proves Conjecture~\ref{conj2}.
\medskip

We also introduce a new sequence $Y_n$ by permuting the Stirling numbers of the first and second kind.  More precisely, let $Y_n$ be the sequence of integers defined by $Y_1=1$ and 
\begin{equation*}
Y_n=\sum_{m=1}^ {n-1}s(n,m)Y_m \, .
\end{equation*}
for $n \geq 2$.
Let $s(n,k)$ be, as usual, $s(n,k)$ the Stirling numbers of the first
kind. For properties of the Stirling numbers, we refer to Comtet
\cite[Chapter 5.5, pp.~212--219]{CO}.

We prove the following theorem for the sequence $Y_n$:

\begin{theorem}\label{th5} Let $Y_n$ be as above. Then
\begin{enumerate}[label=(\alph*)]
\item All the $Y_n$ are odd;
\item For $n\geq 1$, we have $v_2(Y_n+1)=1$ if and only if $n$ is congruent to $0$ or $1$ modulo $3$.
\end{enumerate}
\end{theorem}

We also get some results for a sequence similar to Lengyel's sequence
for primes $p\geq 3$. Define the sequence $Z_n^{\langle p \rangle}$ by
$Z_0^{\langle p \rangle}=0$, $Z_1^{\langle p \rangle}=1$,  and
\begin{align*}
(p-1)Z_n^{\langle p \rangle} & =\sum_{k=1}^{n-1}S(n,k)Z_k^{\langle p \rangle} \\
\intertext{or} 
pZ_n^{\langle p \rangle} & =\sum_{k=1}^{n}S(n,k)Z_k^{\langle p \rangle} 
\end{align*}
for $n \geq 2$.
(Note that $Z_n^{\langle p \rangle}$ is not an integer, but only a $p$-integer).

We prove the following result below:

\begin{theorem}\label{th6} The $p$-adic valuation of the  $Z_n^{\langle p \rangle}$ satisfies
\begin{enumerate}[label=(\alph*)]
\item $\ds v_p(Z_n^{\langle p \rangle})\geq \log_p(n)-1$ for $n \geq 1$;
\item $v_p(Z_n^{\langle p \rangle})=t-1$ for $n = p^t$;
\item $v_p(Z_n^{\langle p \rangle}) \geq t$ for
$n \geq p^t + 1$.
\end{enumerate}
\end{theorem}

\begin{remark} Note that property (c) is an immediate consequence of
property (a). Hence we have only to show that  (a) and (b) 
hold.
\end{remark}

\section{Use of the Stirling numbers of the first kind \label{sec1}} 

We now show  that the $Z_n$ satisfy another recurrence relation:
 \begin{proposition}\label{pr1} The $Z_n$ satisfy 
 \begin{align}\label{E1} & Z_n= s(n,1)-2\sum_{m=1}^{n-1}s(n,m)Z_m, \quad n\geq 2\, ;\\  \label{E2} & Z_n=-s(n,1)-2\sum_{m=2}^{n-1}s(n,m)Z_m,\quad n\geq 3\, .\end{align}
 \end{proposition}
 \begin{proof}
According to Comtet \cite[Formula (6f), p.~144]{CO}, the Stirling numbers of the first and second kind satisfy the formulae
\begin{equation*}
\sum_{k=0}^nS(n,k)s(k,m) =\delta_{m,n}\, ,\text{ and }\sum_{k=0}^ns(n,k)S(k,m) =\delta_{m,n}\, ,
\end{equation*}
where $\delta_{m,n}$ is the usual Kronecker symbol. These relations are equivalent to the following Stirling inversion formula:
\begin{equation}
\forall\, n\in\N \ \Big( f_n=\sum_{m=1}^n s(n,m)g_m\Longleftrightarrow g_n=\sum_{m=1}^nS(n,m)f_m\Big)\, . \label{E2-1}
\end{equation}
Applying this inversion formula to the recurrence relation for the $Z_n$, we obtain
\begin{equation*}
Z_n=\sum_{k=1}^{n-1}S(n,k)Z_k\Leftrightarrow 2Z_n=\sum_{m=1}^n S(n,m)Z_m+ \sum_{m=1}^nS(n,m)s(m,1)\, ,
\end{equation*}
which can also be written 
\begin{equation*}
Z_n=\sum_{m=1}^{n} S(n,m) \frac{Z_m+s(n,1)}{2}\, .
\end{equation*}
Next, by Stirling inversion we get
\begin{equation*}
 \frac{Z_n+s(n,1)}{2}=\sum_{m=1}^n  s(n,m)Z_m\Leftrightarrow  \frac{-Z_n+s(n,1)}{2}=\sum_{m=1}^{n-1}  s(n,m)Z_m\, ,
\end{equation*}
which is the desired result.
\end{proof}

\begin{remark}\label{rem1} 
Actually using exactly the same method, we get the following relation for the sequence $Z_n^{\langle p \rangle}$ and $n \geq 2$:
\begin{equation}
Z_n^{\langle p \rangle}=s(n,1)-\frac{p}{p-1}\sum_{m=1}^{n-1} s(n,m)Z_m\, .\label{E3}
\end{equation}
Since  $s(n,1)=(-1)^{n-1}(n-1)!$ is a $p$-adic unit for  $n=1,\ldots, p$,  we get as an immediate consequence that $Z_n^{\langle p \rangle}$ is a $p$-adic unit for the same values of $n$. 
\end{remark}

\section{Some \texorpdfstring{$p$-adic}{$p$-adic\label{sec2}} properties of Stirling numbers of the first kind}
In this section, we prove some lemmas for the Stirling numbers of the first kind.
\begin{lemma}\label{lem1} For $n\geq m\geq 1$, we get the lower bound
\begin{equation*}
v_p(s(n,m))\geq \Big\lfloor \frac{n-1}{p}\Big\rfloor+1-m\, .
\end{equation*}
\end{lemma} 
\begin{proof}[Proof]Note that the inequality is trivial if $\ds \Big\lfloor \frac{n-1}{p}\Big\rfloor+1-m \leq 0$. 
The Stirling numbers of the first kind (cf.\  \cite[Formula (5e),
p.~213]{CO}) are defined as follows:

\begin{equation*}
P_n(x)=(x)_n:=\sum_{m=1}^n s(n,m)x^m\, . 
\end{equation*}
Take $x\in \C_p$ with $|x|=r$ with $\ds \frac{1}{p}<r<1$. Then $| x-k |=1$ if $k$  is not divisible by  $p$ and $ | x-k|=r$ otherwise. This shows that $\ds |P_n|(r)={\rm max}\{|s(n,m)|r^m\}$ is equal to $r^M$, where $\ds M=\Big\lfloor \frac{n-1}{p}\Big \rfloor +1$ is the number of $k$, $0\leq k\leq n-1$, that are divisible by $p$. Hence $\ds |s(n,m)|r^m\leq r^M$, and $\ds |s(n,m)|\leq r^{M-m}$.

The continuity of the map $r\mapsto \lvert P_n\rvert(r)$, \cite[Cor. 4.2.7, p.~122]{AM},  allows us to choose $\ds r=\frac{1}{p}$ in the previous inequality, which gives the desired lower bound. 
 \end{proof}
 
\begin{lemma}\label{lem2} If $t\geq 2$, and $n=p^t$, it follows that
\begin{equation*}
P_n(x)\equiv \modd{x^{p^{t-1}}(x^{p-1}-1)^{p^{t-1}}} {p} \, . 
\end{equation*}
Therefore $s(n,m)$ is divisible by $p$ if $m\leq p^{t-1}-1$, and $s(p^t, p^{t-1})$ is not divisible by $p$.
\end{lemma}
\begin{proof}[Proof]By hypothesis, we have  $n\geq p^2$. 
Let $r\in \{0,\cdots,p-1\}$. The number of integers  $k$ such that $0\leq k\leq n-1$ and $k\equiv \modd{r} {p}$ is $\ds \Big\lfloor \frac{n-1-r}{p}\Big\rfloor +1=p^{t-1}$. Hence it is independent of  $r$. It follows that
\begin{equation*}
P_n(x)\equiv \prod_{r=0}^{p-1}(x-r)^{p^{t-1}} \mod p\, . 
\end{equation*}
But $\ds \prod_{r=0}^{p-1}(x-r) \equiv \modd{x^p-x=x(x^{p-1}-1)} {p}$. The proof is now complete (the last two assertions are clear).
\end{proof}

Now, we examine the value of $s(n,k)$ modulo $4$, for specific values of $n$.
 \begin{lemma}\label{lem3} Let $t\geq 5$, and $n=2^t$.  Then
\begin{equation*}
\sum_{k=0}^n s(n,k)x^k=P_n(x)=x^{2^{t-1}} (x^2-1)^{2^{t-2}} \pmod{4} \, .
\end{equation*}
 \end{lemma}
 \begin{proof}We know that $P_n(x)=x(x-1)\cdots (x-n+1)$. Let $r$ be such that $0\leq r \leq 3$. There are $\ds M_r=\Big\lfloor \frac{n-r-1 }{4}\Big\rfloor +1$ values $k$, $0\leq k \leq n-1$ such that $k\equiv \modd{r} {4}$. Since $n=2^t$, we  immediately see that $M_r$ is in fact independent of $r$. Hence $M_r$ is equal to $2^{t-2}$. Thus, modulo $4$, the polynomial $P_n$ is congruent to $\ds \prod_{r=0}^3(x-r)^{2^{t-2}}$.
 
We first consider the factor $\ds (x-2)^{2^{t-2}}$. 
Since $(x-2)^2 \equiv \modd{x^2} {4}$, and  $t\geq 5$, or equivalently
$t-2\geq 3$, we see that
\begin{equation*}
(x-2)^{2^{t-2}} \equiv x^{2^{t-2}}\pmod{4}\, .
\end{equation*}
Since $3$ is congruent to $-1$ modulo $4$, we have
\begin{equation*}
P_n(x) \equiv x^{2^{t-1}}(x^2-1)^{2^{t-2}} \pmod{4} \, .
 \end{equation*}
The  proof of the lemma is complete.
\end{proof}

\begin{lemma}\label{lem4} Let $n=2^t$ with $t\geq 5$. Then, for  all $m$, $1\leq m\leq 2^t-1$, $m\neq 3  \cdot 2^{t-2}$ and $m\neq2^{t-1}$, it follows that
\begin{equation*}
s(2^t,m)\equiv 0 \pmod 4\, . 
\end{equation*}
In addition, $s(2^t, 2^{t-1}+2^{t-2})\equiv \modd{0} {2}$, and $s(2^t,2^{t-1})\equiv \modd{1} {4}$.
\end{lemma}

\begin{proof} From Formula \eqref{E0} it follows that
\begin{equation*}
v_2\bigg({2^{t-2} \choose j}\bigg)=S_2(j)+S_2(2^{t-2}-j)-1 \, .
\end{equation*}
If $j\neq 0$  and not equal to $2^{t-2}$, then $S_2(j)+S_2(2^{t-2}-j) \geq 2$. If $S_2(j)+S_2(2^{t-2}-j)=2$ then $j=2^{t-3}$, because it implies that both $j$ and $2^{t-2}-j$ are powers of  $2$ and hence equal (their sum is $2^{t-2}$). 
Using the modulo $4$ formula given above for the polynomial $P_n(x)$, and the binomial theorem for the factor $(x^2-1)^{2^{t-2}}$,  we obtain
\begin{equation*}
P_n(x)\equiv x^{2^t}- {2^{t-2} \choose 2^{t-3}}x^{2^{t-1}+2^{t-2}}+x^{2^{t-1}} \pmod 4 \, .
\end{equation*}
Since the $2$-adic valuation of $\ds {2^{t-2} \choose 2^{t-3}}$ is
equal to $1$, the lemma is proved.
\end{proof}

\begin{lemma}\label{lem5} Let $t\geq 5$, and $n=3\cdot 2^t$. The following congruence holds:
\begin{equation*}
P_n(x)\equiv \sum_{k=0}^n s(n,k)x^k=x^{3\cdot 2^{t-1}}(x^2-1)^{3\cdot 2^{t-2}} 
\pmod 4 \, .
\end{equation*}
\end{lemma}

\begin{proof}Let $r\in  \{0,\cdots,3\}$. The number of  $k$ such that $0\leq k\leq n-1$ and $k\equiv \modd{r} {4}$ is  $\ds \Big\lfloor \frac{n-1-r}{4}\Big\rfloor +1$ which is $3\cdot 2^{t-2}$ for all $r$. Hence
\begin{equation*}
P_n(x)\equiv \prod_{r=0}^3(x-r)^{3\cdot 2^{t-2}} \equiv (\prod_{r=0}^3 (x-r)^{2^{t-2}})^3 \pmod4 \, . 
\end{equation*}
From the proof of Lemma~\ref{lem3} it follows that
\begin{equation*}
 \prod_{r=0}^3 (x-r)^{2^{t-2}}\equiv x^{2^{t-1}}(x^2-1)^{2^{t-2}} \pmod 4 \, .
 \end{equation*}
The proof is now complete.
\end{proof}

\begin{lemma}\label{lem6} 
Let $t\geq 5$, $n=3\cdot 2^t$, and $1\leq m\leq n$.  Then
\begin{enumerate}[label=(\alph*)]
\item $s(n,m)$ is divisible by $4$ for $m\not \in \{2^{t+1}+2^{t-1}, 2^{t+1},  3\cdot 2^{t-1}, 3\cdot 2^{t-1}+2^{t-2}, 3\cdot 2^t-2^{t-2}, 3\cdot 2^t\}$;
\item $s(n,m)$ is even, but not divisible by $4$, for $m=3\cdot 2^{t}-2^{t-2}$ and $m=3\cdot 2^{t-1}+2^{t-2}$;
\item $s(n,m)$ is odd for $m=2^{t+1}+2^{t-1}$, $m=2^{t+1}$, $m=3\cdot 2^{t-1}$ and $m=3\cdot 2^t$.
\end{enumerate}
In particular, $s(n,3\cdot 2^{t-1})$ is odd, and $s(n,3\cdot 2^t-1)$, $s(n,3\cdot 2^t-2)$, and all the $s(n,j)$ for $j\leq 3\cdot 2^{t-1}-1$ are divisible by $4$.
\end{lemma}

\begin{proof}We know that $P_n(x) \equiv x^{3\cdot 2^{t-1}}(x^2-1)^{3\cdot 2^{t-2}} \pmod{4}$ by Lemma \ref{lem5}. By the binomial theorem we get
\begin{equation*}
(x^2-1)^{3\cdot 2^{t-2}}=\sum_{j=0}^{3\cdot 2^{t-2}}(-1)^j {3\cdot 2^{t-2} \choose j} x^{2(3\cdot 2^{t-2}-j)} \, .
\end{equation*}
From Formula~\eqref{E0} we know that the $2$-adic valuation of $\ds {q \choose j}$ is $S_2(j)+S_2(q-j)-S_2(q)$. We have $3\cdot 2^{t-2}=2^{t-1}+2^{t-2}$, and hence $S_2(3\cdot 2^{t-2})=2$. To prove the lemma it suffices
 \begin{enumerate}[label=(\arabic*)]
\item To find all the integers  $j$ such that
\begin{equation}
0\leq j\leq 3\cdot 2^{t-2}, \text{ and }  T:=S_2(j)+S_2(3\cdot 2^{t-2}-j)-2=\begin{cases} 0;\\ 1.\end{cases}\label{E4}
\end{equation} 
\item To show that they are precisely  the integers given in (b) and (c).
\end{enumerate}

First suppose that $T=0$. We have the trivial solutions of equation \eqref{E4}  $j=0$ and $j=3\cdot 2^{t-2}$. Now we can assume $1\leq j\leq 3\cdot 2^{t-2}-1$.  Hence $S_2(j)=S_2(3\cdot 2^{t-2}-j)=1$ (because $S_2(n)\geq 1$), It follows that $j$ and $3\cdot 2^{t-2}-j$ are powers of $2$, say $2^ {\alpha}$ and $2^{\beta}$. Equality $3\cdot 2^{t-2}=2^{\alpha}+2^{\beta}$ immediately shows  that $\alpha=t-2$ and $\beta=t-1$, or vice-versa. We have found $4$ values of  $j$: 
\begin{equation*}
j=0,\ j=2^{t-2},\ j=2^{t-1}\text{ and }j=3\cdot 2^{t-2}\, .
\end{equation*}
 After  multiplying  by $x^{3\cdot 2^{t-1}}$, we see that they are the values given in assertion (c). 

Now suppose that  $T=1$. From the first case we know that  $1\leq j\leq 3\cdot 2^{t-2}-1$. From equation \eqref{E4} it follows that $S(j)=1$ or $S(3\cdot 2^{t-2}-j)=2$ or vice-versa. This leads to study a relation of the form $2^{\alpha}+(2^{\beta}+2^{\gamma})=3\cdot 2^{t-2}$, with $\beta<\gamma$.  We leave to the reader to show that it implies $\alpha=\beta=t-3$  and  $\gamma=t-1$. Hence the two solutions $j=2^{t-3}$ and $j=3 \cdot 2^{t-2}-2^{t-3}$. After multiplying by $x^{3 \cdot 2^{t-1}}$ we see that these values are exactly the values in assertion (b). 

For all other values of $1\leq m \leq 3\cdot 2^t$ $s(n,m)\equiv 0\pmod{4}$. The lemma is proved.
\end{proof}

\section{A lemma about sums of binomial coefficients\label{sec3}}

We also need a lemma about sums of binomials.
\begin{lemma}\label{lem7}
Let $j$ be a primitive third root of unity,  $r\in \{0,1,2\}$, and $n=3k+r$. 

For $s\in \{0,1,2\}$ define
\begin{equation*}
\Gamma_{s,r,k}=\sum_{\substack{0\leq l\leq n; \\ l\equiv \modd{s} {3}}} {n \choose l} \, . 
\end{equation*}
It follows that
\begin{equation*}
3\Gamma_{s,r,k}=2^n+(-1)^n (j^{s+r}+j^{2(s+r)})\, . 
\end{equation*}
As a consequence, we get
\begin{itemize}
\item If $r+s$ is not divisible by $3$, then
\begin{equation*}
3\Gamma_{s,r,k}=2^n+(-1)^{n+1}\, .  
\end{equation*}
\item If $r+s$ is divisible by $3$, then
\begin{equation*}
3\Gamma_{s,r,k}=2^n+2(-1)^{n} \, . 
\end{equation*}
\end{itemize}
\end{lemma}

\begin{proof} Write 
\begin{equation*}
(1+x)^n=\sum_{l=0}^n {n \choose l} x^l \, ,
\end{equation*}
and choose successively $x=1$, $x=j$, and $x=j^2$. It follows that
\begin{gather*} 
\Gamma_{0,r,k}+\Gamma_{1,r,k}+\Gamma_{2,r,k}=2^n\, ,\label{E4-1}\tag*{$(L_1)$} \\
 \Gamma_{0,r,k}+j\Gamma_{1,r,k}+j^2\Gamma_{2,r,k}=(1+j)^n\, ,\label{E4-2}\tag*{$(L_2)$}  \\
 \Gamma_{0,r,k}+j^2\Gamma_{1,r,k}+j\Gamma_{2,r,k}=(1+j^2)^n \, .\label{E4-3}\tag*{$(L_3)$} 
 \end{gather*}

Since $1+j+j^2=0$, we get,
when computing the quantities $L_1+L_2+L_3$, $L_1+j^2L_2+jL_3$, and $L_1+jL_2+j^2L_3$,
\begin{align*}
3\Gamma_{0,r,k} & =2^n+(1+j)^n+(1+j^2)^n=2^n+(-1)^n(j^{r}+j^{2r})\, , \\
3\Gamma_{1,r,k} & =2^n+j^2(1+j)^n+j(1+j^2)^n=2^n+(-1)^n(j^{1+r}+j^{2r+2})\, , \\
3\Gamma_{2,r,k} & =2^n+j(1+j)^n+j^2(1+j^2)^n=2^n+(-1)^n(j^{r+2}+j^{2r+1}) \, .
\end{align*}
The general formula follows.
\end{proof}

\begin{remark} Analogous results exist in, e.g., \cite{HO}.
\end{remark}

\section{Proof of  Theorem \ref{th2}}
\label{S6} 
We show the result by induction on $n$. For $n\leq 7$, we check that the lower bound holds using the explicit numerical values of the $Z_n$, cf.~\cite[p.~179]{LE}. Hence our induction hypothesis will be
\begin{equation}
\bigl(n\geq 7 \Rightarrow  v_2(Z_m)\geq \log_2(m)-1, \ 1\leq m\leq n-1\bigr) \, . \label{E7}\tag*{H(n)}
\end{equation}

We use Formula (\ref{E2}), valid for $n\geq 3$:
\begin{equation*}
Z_n=-s(n,1)-2\sum_{m=2}^{n-1}s(n,m)Z_m\, . \tag{\ref{E2}}
\end{equation*}
We will show that all the terms in the last expression have $2$-adic
absolute value $\leq 2^{-\log_2(n)+1}$; this will imply that this is also
the case for $Z_n$, and the result will be proved. We consider many
different cases.

\begin{enumerate}[label=\ref{S6}.\arabic*, font=\bfseries]
\item Let $m$ be such that $\ds 2\leq m\leq \Big\lfloor \frac{n-1}{2}\Big\rfloor +1$.
Using  Lemma \ref{lem1} and the induction hypothesis, we get
\begin{equation*}
 \big\vert s(n,m)Z_m \big\vert \leq 2^{-\log_2(m)+1- \big\lfloor \frac{n-1}{2}\big\rfloor -1+m}\, .
 \end{equation*}
We want to show that this last term is bounded by $2^{-\log_2(n)+2}$ (we have taken into account the factor $2$ in Formula \eqref{E2}). This is equivalent to showing that
\begin{equation*}
m-\log_2(m)\leq \Big\lfloor \frac{n-1}{2}\Big\rfloor -\log_2(n)+2 \, .
\end{equation*}
There are  two cases,  $n$ even or odd.
\begin{description}
\item{\emph{First case: $n$ even.}}
Let $n=2h$. As  $n\geq 7$, we have  $h\geq 4$. We also have $\ds \Big\lfloor \frac{n-1}{2}\Big\rfloor =h-1$; hence $m\leq h$. Since $\log_2(2h)=1+\log_2(h)$, we have to show that
\begin{equation*}
m-\log_2(m)\leq h-\log_2(h) \, ,
\end{equation*}
which holds because the function $x-\log_2(x)$ is increasing for $x\geq 2$.
\item{\emph{Second case: $n$ odd.}}
Let $n=2h+1$ (hence $h\geq 3$). We get $\ds \Big\lfloor \frac{n-1}{2}\Big\rfloor =h$; hence $2\leq m\leq h+1$. First, suppose that $m=h+1$. We have to show
\begin{equation*}
 h+1-\log_2(h+1)\leq h-\log_2(2h+1)+2
 \end{equation*}
 or $\log_2(2h+1)\leq \log_2(h+1)+1$ which is equivalent to showing $2h+1\leq 2h+2$ and hence is true.

Now we can  suppose that $2\leq m\leq h$. Since $h\geq 3$, we have $\ds 1+\frac{1}{2h}\leq \frac{7}{6}$, and hence
\begin{equation*}
1-\log_2(1+\frac{1}{2h})\geq 1-\log_2(\frac{7}{6})=\frac{\log(12)-\log(7)}{\log2}>0\, .
\end{equation*}
It suffices to show that
\begin{equation*}
m-\log_2(m)\leq h- \log_2(h) \, ,
\end{equation*}
which holds because  the function $x-\log_2(x)$ is increasing for $x\geq 2$, and $2\leq m\leq h$.
\end{description}
\item Now suppose that  $m$ verify $\ds \Big\lfloor \frac{n-1}{2}\Big\rfloor +2\leq m\leq n-1$. We have only at our disposal the induction hypothesis.

We have to show, taking into account the factor $2$, that $2^{-\log_2(m)+1}\leq 2^{-\log_2(n)+2}$, or $\log_2(n)\leq \log_2(m)+1$. This is equivalent to showing $n\leq 2m$. There are two cases:
\begin{enumerate}
\item If $n$ is even, $n=2h$, we have $\ds m\geq \Big\lfloor \frac{n-1}{2}\Big\rfloor +2=h+1$; hence $2m\geq 2h+2=n+2$.
\item  If $n$ is odd, $n=2h+1$, we have $\ds m\geq \Big\lfloor \frac{n-1}{2}\Big\rfloor +2=h+2$; hence $2m\geq 2h+4=n+3$.
\end{enumerate}
\item The only remaining term, $s(n,1)$, is equal to $(-1)^{n-1}(n-1)!$, cf.\ \cite[Formula (6b), p.~214]{CO}.
We want to show that, for all  $n\geq 7$,
\begin{equation*}
|(n-1)!|=2^{-n+1+S_2(n-1)} \leq 2^{-\log_2(n)+1} \, .
\end{equation*}
This is equivalent to showing that
\begin{equation*}
S_2(n-1)+\log_2(n)\leq n\, .
 \end{equation*}
For $m\geq 1$, we have $S_2(m)\leq 1+\log_2(m)$, it suffices then to show that $1+\log_2(n-1)+\log_2(n)\leq n$. This is equivalent to showing $n(n-1)\leq 2^{n-1}$. We prove this inequality by noticing that it holds for $n= 6$ and using an easy induction argument.\medbreak
\end{enumerate}
Now the proof of Theorem \ref{th2} is  complete.

\section{Proof of Theorem \ref{th3}\label{sec5}} 

We also use
induction. Looking at the numerical values of $Z_n$, we check the
equality for  $t=3$ and $t=4$. So suppose that equality $\ds
v_2(Z_{2^h})=h$ holds for $3\leq h\leq t-1$, and prove that $\ds
v_2(Z_{2^t})=t$. We can suppose  $t \geq 5$.

Again using Formula (\ref{E2}) with $n=2^t$, we get
\begin{equation*}
Z_{2^t}=-s(2^t,1)-2\sum_{m=2}^{2^t-1}s(2^t,m)Z_m\, . 
\end{equation*}
We will prove that all terms in Eq.~\eqref{E2}, with the exception of the term corresponding to  $m=2^{t-1}$, (note that $t-1\geq 4$; hence $m\neq 4$) have $2$-adic valuation $\geq t+1$. 
\begin{enumerate}[label=\ref{sec5}.\arabic*, font=\bfseries]
\item First, consider the valuation of the term $s(2^t,1)=(-1)^{2^t-1}(2^t-1)!$. From Formula \eqref{E0} it follows that
\begin{equation*}
v_2\bigl(s(2^t,1)\bigr)=2^t-1-S_2(2^t-1)=2^t-1-t \, .
\end{equation*}
We want to prove that $2^t-1-t\geq t+1$ or, replacing $t$ by $t-1$, $2^{t-1}\geq 1+t$; this last inequality holds for $t=3$, and also for $t\geq 3$ by an easy induction.
\item Now take  the term  $2s(2^t,m)Z_m$ with $2\leq m\leq 2^{t-1}-3$. Its valuation satisfies
\begin{equation*}
v_2\bigl(2s(2^t,m)Z_m\bigr)\geq 1+\Big\lfloor \frac{2^t-1}{2}\Big\rfloor +1-m+\log_2(m)-1=2^{t-1}-m+ \log_2(m)\, . 
\end{equation*}
As we want to prove that $v_2(2s(2^t,m)Z_m)\geq t+1$, it suffices to prove that
\begin{equation*}
m-\log_2(m)\leq 2^{t-1}-1-t \, . 
\end{equation*}
Since the function $x-\log_2(x)$ is increasing for $x\geq 2$, we only have  to prove  the inequality for $m=2^{t-1}-3$. This is equivalent to showing that $\log_2(2^{t-1}-3)\geq t-2$, or $2^{t-2}\geq 3$. This last inequality holds by the hypothesis on $t$.
\item Now take a term $2s(2^t,m)Z_m$ with $m=2^{t-1}-1$ or $2^{t-1}-2$. We have to prove
\begin{equation*}
v_2\bigl(2s(2^t,m)Z_m\bigr)=1+v_2\bigl(s(2^t,m)\bigr)+v_2(Z_m)\geq t+1\, . 
\end{equation*}
It follows from Lemma \ref{lem4} that $s(2^t, 2^{t-1}-1)$ and $s(2^t, 2^{t-1}-2)$ are divisible by $4$, and, since, for these two values, we have   $m=2^{t-2}+L$ with $L\geq 1$,  we know that $v_2(Z_m)\geq t-2$. Hence
\begin{equation*}
v_2\bigl(2s(2^t,m)Z_m\bigr)\geq 1+2+t-2=t+1\, . 
\end{equation*}
\item Now examine $2s(2^t,m)Z_m$ with $\ds 2^{t-1}+1\leq m \leq 2^t-1$ and $m\neq 2^{t-1}+2^{t-2}=3\cdot 2^{t-2}$. By Lemma \ref{lem4},  $s(2^t,m)$ is divisible by $4$ for these values of  $m$. Hence
\begin{equation*}
v_2\bigl(2s(2^t,m)Z_m\bigr)\geq 3+v_2(Z_m) \geq 2+\log_2(m) \, . 
\end{equation*}
It suffices to prove that $\log_2(m)\geq t-1$, or $m\geq 2^{t-1}$, which 
is true.
\item Now consider the term  $2s(2^t,m)Z_m$ with $m=2^{t-1}+2^{t-2}$.  By Lemma \ref{lem4}, we know that $s(2^t,m)$ is divisible by $2$ and that
\begin{equation*}
v_2(Z_m)\geq \log_2(m)-1=\log_2 (3\cdot 2^{t-2})-1=\log_2(3)+t-2-1>t-2\, , 
\end{equation*}
 hence $v_2(Z_m)\geq t-1$. Therefore
 \begin{equation*}
 v_2\bigl(2s(2^t,m)Z_m)\geq 1+1+t-1=t+1\, . 
 \end{equation*}
 \item We are only left with the term $2s(2^t,m)Z_m$ with $m=2^{t-1}$. By the induction hypothesis, we have $v_2(Z_m)=t-1$, and we know that $s(2^t, 2^{t-1})$ is odd by  Lemma \ref{lem4}. Hence the $2$-adic valuation of this term  is exactly $t$. 
  \end{enumerate}
We have proved that, in the expression \eqref{E2} of $Z_{2^t}$, only one term has valuation $t$ , all the others having valuation  $\geq t+1$; hence $v_2\bigl(Z_{2^t}\bigr)=t$. The proof is  complete.
 
 \section{Proof of Theorem \ref{th4}\label{sec6}}
First we show that the conjecture holds for $3\cdot 2^h$, with $2\leq
h\leq 4$, by numerical computations; then we proceed by induction.
Suppose the result true for $2\leq h\leq t-1$; let us prove it
for $t$. By the above, we can suppose that $t\geq 5$. We have to prove
two facts:
 \begin{enumerate}[label=(\alph*)]
\item For $m=3\cdot 2^t$,  $v_2(Z_m)=t+1$;
 \item For $m'>3\cdot 2^t$,  $v_2(Z_{m'})\geq t+2$.
 \end{enumerate}
 
\emph{First, let us prove  assertion (a)}. Of course we use  Formula~\eqref{E2}:
 \begin{equation*}
 Z_n=-s(n,1)-2\sum_{m=2}^{n-1}s(n,m)Z_m\, . 
 \end{equation*}
Take $n=3\cdot 2^t$. We will prove that all the terms in this expression are of $2$-adic valuation $\geq t+2$, with the exception of only one term.
\begin{enumerate}[label=\ref{sec6}.\arabic*, font=\bfseries]
\item First, look at $s(3\cdot 2^t,1)$. Its $2$-adic valuation is  $3\cdot 2^t-1-S_2(3\cdot 2^{t}-1)$. Since $3\cdot 2^t-1=2^{t+1}+2^{t-1}+\cdots+1$ we get  $S_2(3\cdot 2^t-1)=t+1$. We have to show that $3\cdot 2^t-1-t-1\geq t+2$. This inequality holds for $t=1$. The general case follows by an easy induction.
\item Now consider  $2s(3\cdot 2^t,m)Z_m$, with $2\leq m\leq 3\cdot 2^{t-1}-2$. Using Lemma \ref{lem1} and Theorem \ref{th2}, we easily see that its $2$-adic valuation is $\geq 3\cdot 2^{t-1}-m+\log_2(m)$. Hence we have  only to prove that $\ds 3\cdot 2^{t-1}-t-2\geq m-\log_2(m)$. The function $x-\log_2(x)$ being increasing it suffices to prove this last inequality for $m=3\cdot 2^{t-1}-2$. This is equivalent to showing that $\ds  \log_2\bigl(3\cdot 2^{t-1}-2\bigr)\geq t$, which is obvious since $3\cdot 2^{t-1}-2=2^{t}+(2^{t-1}-2)\geq 2^t$. 
\item Now take $m=3\cdot 2^{t-1}-1=2^t+(2^{t-1}-1)$. By Theorem \ref{th2}, $v_2(Z_m)>t-1$, therefore $v_2(Z_m)\geq t$. By Lemma \ref{lem6}, $v_2(s(3\cdot 2^t,m))\geq 2$, and we are done. 
\item Now suppose that $3\cdot 2^{t-1}+1\leq m\leq 3\cdot 2^t-1$, and $m\not \in \{ 2^{t+1}, 2^{t+1}+2^{t-1}, 3\cdot 2^{t-1},3\cdot 2^{t}-2^{t-2}, 3\cdot 2^{t-1}+2^{t-2} \}$. By Lemma \ref{lem6} it follows that $v_2(s(3\cdot 2^t,m))\geq 2$. On the other hand, $m=3\cdot 2^{t-1}+L=2^{t}+L'$ with $L' > 0$. Then $v_2(Z_m)\geq t$ and this ends the case.
\item Now examine the two cases $m_1=3\cdot 2^{t}-2^{t-2}$ and $m_2=3\cdot 2^{t-1}+2^{t-2}$. By Lemma \ref{lem6}, we know that $v_2(s(3\cdot 2^t,m))=1$ for these values of $m$. Since $m_1=2^{t+1}+(2^t-2^{t-2})$, $v_2(Z_{m_1})\geq t+1$ by Theorem \ref{th2}, and $v_2(Z_{m_2})\geq t+1$ by the induction hypothesis, because $m_2>3\cdot 2^{t-1}$, and this ends the case.
\item Now consider the two cases $m_3=2^{t+1}$ and $m_4=2^{t+1}+2^{t-1}$. By Lemma \ref{lem6} we know that $s(3\cdot 2^t,m_j)$ is odd for $j=3,4$. We have already proved that $v_2(Z_{m_3})=t+1$; hence $v_2(2s(n,m_3)Z_{m_3})=t+2$. It follows that $v_2(Z_{m_4})\geq t+1$, because $m_4=2^{t+1}+L$ with $L\geq 1$, and we get $v_2\bigl(2s(3\cdot 2^t,m_4)Z_{m_4}\bigr)\geq t+2$.
\item Only one value of $m$ remains, namely, $m=3\cdot 2^{t-1}$. We know that $s\bigl(3\cdot 2^t,3\cdot 2^{t-1}\bigr)$ is odd, and by the induction hypothesis we know that that $v_2(Z_m)=t$. The $2$-adic valuation of this term is $t+1$ and this is the only term with this property, all other terms having $2$-adic valuation $\geq t+2$.  
\end{enumerate}
Hence $v_2\bigl(Z_{3\cdot 2^t}\bigr)=t+1$, and this ends the first part of the proof of Theorem \ref{th4}.\medskip

Now let us prove the second part of Theorem \ref{th4}.

Let $n$ be such that $n\geq 3\cdot 2^t+1$. We want to prove that $v_2(Z_n)\geq t+2$. We use the recurrence formula \eqref{E2} again:
\begin{equation*}
Z_n=-s(n,1)-2\sum_{m=2}^{n-1}s(n,m)Z_m\, .
\end{equation*}
It is enough to show that all the terms in this formula have $2$-adic valuation $\geq t+2$.
\begin{enumerate}[label=\ref{sec6}.\arabic*,resume,font=\bfseries]
\item First, consider the term $s(n,1)$. Its $2$-adic valuation is $n-1-S_2(n-1)$. Since $S_2(n-1)\leq 1+\log_2(n-1)$, we have to prove that $(n-1)-\log_2(n-1)\geq t+3$. It suffices to prove that $3\cdot 2^t-\log_2(3\cdot 2^t)\geq t+3$, and since $\ds \log_2(3)<2$, that $3\cdot 2^t\geq 2t+5$, or $3\cdot 2^{t-1}\geq t+3$. This last inequality holds for $t=2$, and hence for $t\geq 2$ by an easy induction.
\item Next, consider the case $2\leq m\leq 3\cdot 2^{t-1}-2$. Apply Lemma \ref{lem1} and Theorem \ref{th2}. Using  the following inequality, valid for $n\geq 3\cdot 2^t+1$, $\ds \Big\lfloor \frac{n-1}{2}\Big\rfloor \geq 3\cdot 2^{t-1}$, we have to prove 
\begin{align*}
 & 3\cdot 2^{t-1}+1-m+\log_2(m)\geq t+2\, ,\\
\intertext{or}\\
& 3\cdot 2^{t-1}-t-1\geq m-\log_2(m)\, .
\end{align*}
It suffices to prove this inequality for $m=3\cdot 2^{t-1}-2$. It is equivalent to showing that $\log(3\cdot 2^{t-1}-2)\geq t-1$, or  $3\cdot 2^{t-1}-2\geq 2^{t-1}$, which is clear. 
\item Now consider the case $m=3\cdot 2^{t-1}-1$. We have $\ds v_2(s(n,m))\geq \Big\lfloor \frac{n-1}{2}\Big\rfloor +1-m\geq 3\cdot 2^{t-1}+1-m$. Hence it suffices to prove
\begin{equation*}
1+3\cdot 2^{t-1}+1-3\cdot 2^{t-1}+1+v_2(Z_m)\geq t+2\, , 
\end{equation*}
 i.e., $3+v_2(Z_m)\geq t+2$. Since $m=2^t+(2^{t-1}-1)$ it follows that $v_2(Z_m)\geq t$. The assertion is proved.
\item  Consider the case $m=3\cdot 2^{t-1}$. By the induction hypothesis $v_2(Z_m)= t$  hence  $\ds v_2(s(n,m))\geq \Big\lfloor \frac{n-1}{2}\Big\rfloor +1-m\geq 3\cdot 2^{t-1}+1-m=1$. It follows that $v_2(2s(n,m)Z_m)\geq 1+1+t=t+2$.
\item Consider the last case, where $3\cdot 2^{t-1}+1\leq m< n$. By the induction hypothesis we have $v_2(Z_m)\geq t+1$. Hence $v_2(2s(n,m)Z_m)\geq t+2$.
\end{enumerate}
We have proved that all the terms in the formula giving  $Z_n$ have $2$-adic valuation  $\geq t+2$ therefore  $v_2(Z_n)\geq t+2$ for $n\geq 3\cdot 2^t+1$. The proof of Theorem~\ref{th4} is now complete.

\section{Proof of Theorem \ref{th5}\label{sec7}}
\begin{enumerate}[label=(\alph*)]
\item With exactly the same proof as in Proposition~\ref{pr1}, we prove another recurrence formula for the $Y_n$:
\begin{equation*}
Y_n=-S(n,1)+2\sum_{m=1}^n S(n,m)Y_m\, . 
\end{equation*}
Since $S(n,1)=1$, this gives
\begin{equation*}
Y_n=1-2\sum_{m=1}^{n-1}S(n,m)Y_m\, . 
\end{equation*}
Hence all the  $Y_n$ are odd.
\item We can suppose that $n\geq 2$.  By the 
Stirling inversion formula \eqref{E2-1}, it follows that
\begin{equation*}
2Y_n=\sum_{m=1}^n s(n,m)Y_m\, .
\end{equation*}
Taking $x=1$ in the formula
\begin{equation*}
x(x-1)\cdots (x-n+1)=\sum_{m=1}^n s(n,m)x^m\, , 
\end{equation*}
we get that $\ds \sum_{m=1}^n s(n,m)=0$. Hence it follows that
\begin{equation*}
2Y_n=\sum_{m=1}^n s(n,m)(Y_m+1)\, . 
\end{equation*}

By the above equality$\ds H_j=\frac{Y_j+1}{2}$ is an integer.
Hence we have
\begin{equation*}
Y_n=2H_n-1=\sum_{m=1}^n s(n,m)H_m \, 
\end{equation*}
and so
\begin{equation*}
H_n\equiv 1+\sum_{m=1}^{n-1}s(n,m)H_m \pmod 2\, . 
\end{equation*}
\end{enumerate}

Now we will prove by induction that $H_n$ is odd, for $n$
congruent to $0$ or $1$ modulo $3$, and even for $n$ congruent to $2$
modulo $3$. Clearly this will prove the result. We easily check  that
the preceding assertion holds for the first few values of the sequence
$H_n$.

By Lemma \ref{lem1} we know that $v_2(s(n,m))\geq M-m$, where $\ds M=\Big\lfloor \frac{n-1}{2}\Big\rfloor +1$. Therefore
\begin{equation*}
H_n\equiv 1+\sum_{m=M}^{n-1}s(n,m)H_m \pmod 2 \, . 
\end{equation*}
We also have
\begin{equation*}
x(x-1)\cdots (x-n+1)\equiv x^M(x-1)^{n-M} \pmod 2 \, . 
\end{equation*}
This implies that $\ds s(n,M+j)\equiv {n-M \choose j} \pmod{2}$. We therefore have
\begin{equation*}
H_n\equiv 1+\sum_{j=0}^{n-M-1} {n-M \choose j}H_{j+M} \pmod 2 \, . 
\end{equation*}
By the induction hypothesis, $H_{j+M}$ is zero modulo $2$ if $j+M$ is congruent to $2$ modulo $3$.  Hence
\begin{equation*}
H_n\equiv 1+\sum_{\substack{0\leq j\leq n-M-1\\ M+j\equiv \modd{0} {3}}} {n-M \choose j}+\sum_{\substack{0\leq j\leq n-M-1\\ M+j\equiv \modd{1} {3}}} {n-M \choose j}    \pmod 2 \, . 
\end{equation*}

Now write $n=6k+s$, $s\in \{0,1,2,3,4,5\}$, and check each case.\medbreak
\begin{enumerate}[label=\emph{Case s=}\arabic*:]
{\setlength\itemindent{1.4cm}
\item We have $M=3k$, $n-M=3k$. Hence
\begin{equation*}
H_n=1+\sum_{\substack{0\leq j\leq 3k-1\\ j \equiv \modd{0} {3}}} 
{3k \choose j}+\sum_{\substack{0\leq j\leq 3k-1\\ j\equiv \modd{1} {3}}} {3k \choose j} \pmod 2 \, , 
\end{equation*}
which can be written as follows:
\begin{equation*}
H_n\equiv \Gamma_{0,0,k}+\Gamma_{1,0,k} \pmod 2 \, . 
\end{equation*}
From case (b) of Lemma \ref{lem7} it follows that
\begin{equation*}
3(\Gamma_{0,0,k}+\Gamma_{1,0,k})=2^{3k+1}+(-1)^{3k}\, ,
\end{equation*}
hence $H_n$ is odd.
\item It follows that $M=3k+1$ and $n-M=3k$. Hence
\begin{equation*}
H_n \equiv 1+\sum_{\substack{0\leq j\leq 3k-1\\ j\equiv \modd{2} {3}}} {3k \choose j}+\sum_{\substack{0\leq j\leq 3k-1\\ j\equiv \modd{0} {3}}} {3k \choose j} \pmod 2 \, ,
\end{equation*}
which can be written as follows:
\begin{equation*}
H_n \equiv \Gamma_{2,1,k}+\Gamma_{0,1,k} \pmod 2 \, . 
\end{equation*}
By Lemma \ref{lem7}, we have
\begin{equation*}
 3(\Gamma_{2,1,k}+\Gamma_{0,1,k})=2^{3k+2}+(-1)^{3k+1}\, ,
 \end{equation*}
and hence $H_n$ is odd.
\item It follows that $M=3k+1$ and $n-M=3k+1$. Hence
\begin{equation*}
H_n \equiv 1+\sum_{\substack{0\leq j\leq 3k\\ j \equiv \modd{2} {3}}} {3k+1 \choose j}+\sum_{\substack{0\leq j\leq 3k\\ j \equiv \modd{0} {3}}} {3k+1 \choose j} \pmod 2 \, ,
\end{equation*}
which can be written as follows:
\begin{equation*}
H_nÊ\equiv 1+\Gamma_{2,1,k}+\Gamma_{0,1,k}  \pmod 2 \, . 
\end{equation*}
By Lemma \ref{lem7}
\begin{equation*}
3(\Gamma_{2,1,k}+\Gamma_{0,1,k})=2^{3k+2}+(-1)^{3k+1}
\end{equation*}
hence $H_n$ is even.
\item It follows that $M=3k+2$ and $n-M=3k+1$. Hence
\begin{equation*}
H_n \equiv 1+\sum_{\substack{0\leq j\leq 3k\\ j \equiv \modd{1} {3}}} {3k+1 \choose j}+\sum_{\substack{0\leq j\leq 3k\\ j \equiv \modd{2} {3}}} {3k+1 \choose j} \pmod 2 \, , 
\end{equation*}
which can be written as follows:
\begin{equation*}
H_n \equiv \Gamma_{1,1,k}+\Gamma_{2,1,k} \pmod 2 \, .
\end{equation*}
By Lemma \ref{lem7} we have
\begin{equation*}
3(\Gamma_{1,1,k}+\Gamma_{2,1,k})=2^{3k+2}+(-1)^{3k+1}\, ,
\end{equation*}
and hence $H_n$ is odd.
\item It follows that  $M=3k+2$ and $n-M=3k+2$. Hence
\begin{equation*}
H_n \equiv 1+\sum_{\substack{0\leq j\leq 3k+1\\ j \equiv \modd{1} {3}}} {3k+2 \choose j}+\sum_{\substack{0\leq j\leq 3k+1\\ j \equiv \modd{2} {3}}} {3k+2 \choose j} \pmod 2  \, , 
\end{equation*}
which can be written as follows:
\begin{equation*}
H_n \equiv 1+\Gamma_{1,2,k}+\Gamma_{2,2,k} \pmod 2 \, . 
\end{equation*}
By Lemma \ref{lem7} 
\begin{equation*}
3(\Gamma_{2,1,k}+\Gamma_{0,1,k})=2^{3k+3}+(-1)^{3k+2}\, ,
\end{equation*}
and hence $H_n$ is odd.
\item It follows that $M=3k+3$ and $n-M=3k+2$. Hence
\begin{equation*}
H_n \equiv 1+\sum_{\substack{0\leq j\leq 3k+1; \\ j\equiv \modd{0} {3}}} {3k+2 \choose j}+\sum_{\substack{0\leq j\leq 3k+1;\\  j \equiv \modd{1} {3}}} {3k+2 \choose j} \pmod 2 \, ,
\end{equation*}
which can be written as follows:
\begin{equation*}
H_n \equiv 1+\Gamma_{0,2,k}+\Gamma_{1,2,k} \pmod 2 \, . 
\end{equation*}
By Lemma \ref{lem7} we have
\begin{equation*}
3(\Gamma_{0,2,k}+\Gamma_{1,2,k})=2^{3k+3}+(-1)^{3k+2}\, ,
\end{equation*}
and hence $H_n$ is even.
}
\end{enumerate}
The proof of Theorem \ref{th5} is now complete.

\section{Proof of property (a) of Theorem \ref{th6} \label{sec10}} 
We use induction on  $n$. For $1\leq n\leq p$, the property holds, because $\log_p(n)-1\leq 0$. Now suppose the property holds for   $m\leq n-1$, we have to show the property for $n$. By the above, one can suppose that $n\geq p+1$.

It is enough to prove that all the terms in Formula \eqref{E3}
\begin{equation*} 
Z_n^{\langle p \rangle}=s(n,1)-\frac{p}{p-1}\sum_{m=1}^{n-1} s(n,m)Z_m^{\langle p \rangle} 
\end{equation*} 
have a $p$-adic valuation $\geq \log_p(n)-1$.
\begin{enumerate}[label=\ref{sec10}.\arabic*, font=\bfseries ]
\item Begin with $\ds s(n,1)=(-1)^{n-1}(n-1)!$. Its $p$-adic valuation is $\ds \frac{n-1-S_p(n-1)}{p-1}$. We have to prove that this quantity is  $\geq \log_p(n)-1$. Write $n-1=a_0+a_1p+\cdots+a_mp^m$, with $a_k\in \{0,\cdots,p-1\}$ and $a_m \not = 0$. We have $n\leq 1+(p-1)(1+p+\cdots+p^m)=p^{m+1}$; hence $\log_p(n)\leq m+1$. It suffices to prove
\begin{equation*}
a_1+a_2(1+p)+\cdots+a_m(1+p+\cdots+p^{m-1})\geq m\, . 
\end{equation*}
But in the sum $1+p+\cdots+p^{m-1}$, all terms are $\geq 1$, the second term is $\geq 3$, and  $a_m\geq 1$, and we are done.
\item Now let $m$ be such that $\ds 1\leq m\leq \Big\lfloor \frac{n-1}{p}\Big\rfloor +1$. One can neglect the factor $\ds \frac{1}{p-1}$. We have hence to prove
\begin{equation*}
v_p(ps(n,m)Z_m^{\langle p \rangle})=1+v_p(s(n,m))+v_p(Z_m^{\langle p \rangle})\geq \log_p(n)-1 \, .
\end{equation*}
Using Lemma \ref{lem1} and the induction hypothesis, it suffices to prove
\begin{align}
& 1+\Big\lfloor \frac{n-1}{p}\Big\rfloor +1-m +\log_p(m)-1\geq \log_p(n)-1\, , \notag\\
\intertext{or} \notag\\
& \Big\lfloor \frac{n-1}{p}\Big\rfloor +2-\log_p(n)\geq m-\log_p(m) \, . \label{E9}
\end{align}
There are two cases $\begin{cases} \text{(a):}&  n \text{ divisible by }p; \\ \text{b):} & n \text{ not divisible by }p.\end{cases}$
\begin{enumerate}
\item Suppose that $n$ is divisible by $p$. Let $n=kp$. It follows that $\ds \Big\lfloor \frac{n-1}{p}\Big\rfloor =k-1$; hence $1\leq m\leq k$. We then have to prove
\begin{equation*}
k-\log_p(k)\geq m-\log_p(m)\, , 
\end{equation*}
which holds because the function $x-\log_p(x)$ is increasing for $x\geq 1$. 
\item Suppose that $n$ is not divisible by $p$ Let $n=kp+r$, with $1\leq r\leq p-1$. it follows that $1\leq m\leq k+1$.  First examine the case $m=k+1$; we have to prove that
\begin{equation*}
k+2-\log_p(kp+r)\geq k+1-\log_p(k+1)\, , 
\end{equation*}
or  $p(k+1)\geq kp+r$, which is true.

Hence we can  suppose $m\leq k$. Since $k+1-\log_p(k+1)\geq m-\log_p(m)$, It follows that relation \eqref{E9} is also satisfied in this case .
\end{enumerate}
\item Now suppose that $\ds \Big\lfloor \frac{n-1}{p}\Big\rfloor +2\leq m\leq n-1$.  Using the induction hypothesis again, $v_p(Z_m^{\langle p \rangle}) \geq \log_p(m)-1$, we get
\begin{equation*}
v_p(ps(n,m)Z_m^{\langle p \rangle})\geq 1+v_p(Z_m^{\langle p \rangle}) \geq \log_p(m)\, . 
\end{equation*}
We want to prove that $\log_p(m)\geq \log_p(n)-1$, or $p\cdot m\geq n$. Suppose on the contrary that $p\cdot m\leq n-1$. It follows that $\ds m\leq \Big\lfloor \frac{n-1}{p}\Big\rfloor $, in contradiction with hypothesis: $\ds m\geq \Big\lfloor \frac{n-1}{p}\Big\rfloor +2$. 
\end{enumerate}
The proof of property (a) of Theorem \ref{th6} is now complete.

\section{Proof of property  (b) of Theorem \ref{th6}\label{sec11}} We proceed by induction. We have seen (cf.\ Remark \ref{rem1}) that $Z_p^{\langle p \rangle}$ is a $p$-adic unit; hence $v_p(Z_p^{\langle p \rangle})=0$,
which is property (b) for $t=1$. 

Now suppose property  (b) satisfied for $n=p^k$, with $1\leq k\leq t-1$. We want to prove it for $n=p^t$. One can suppose that  $t\geq 2$. We use formula \eqref{E3} again:
\begin{equation*} 
Z_n^{\langle p \rangle}=s(n,1)-\frac{p}{p-1}\sum_{m=1}^{n-1} s(n,m)Z_m^{\langle p \rangle}\, . 
\end{equation*} 
We will prove that all terms in the above formula have $p$-adic valuation greater than $t$, with the only exception of the term with index $m=p^{t-1}$, which has $p$-adic valuation $t-1$.
\begin{enumerate}[label=\ref{sec11}.\arabic*, font=\bfseries]
\item First, consider the term $s(n,1)=(-1)^{n-1}(n-1)!$. Its $p$-adic valuation is 
\begin{equation*}
 \frac{n-1-S_p(n-1)}{p-1}=1+p+\cdots+p^{t-1}-t=(p-1)+\cdots +(p^{t-1}-1)\, .
 \end{equation*} All the terms in this sum are $\geq 1$, and for example the first one is $\geq 2$ and hence the sum is $\geq t$.
\item Now suppose that $1\leq m\leq p^{t-1}-2$. It follows that
\begin{equation*}
v_p(ps(n,m)Z_m^{\langle p \rangle})\geq 1+\Big\lfloor \frac{n-1}{p}\Big\rfloor +1-m+\log_p(m)-1\, .
\end{equation*}
It suffices to show that
\begin{equation*}\
\Big\lfloor \frac{n-1}{p}\Big\rfloor +1-t\geq m-\log_p(m)\, .
 \end{equation*}
Since $\ds \Big\lfloor \frac{n-1}{p}\Big\rfloor +1=p^{t-1}$, we have to prove 
\begin{equation*}
p^{t-1}-t\geq m-\log_p(m) \, .
\end{equation*}
Since the function $x-\log_p(x)$ is increasing for $x\geq 1$,
it suffices to show
\begin{equation*}
p^{t-1}-t\geq p^{t-1}-2-\log_p(p^{t-1}-2)\, , 
\end{equation*} 
or $p^{t-1}-2\geq p^{t-2}$, which is obvious.
\item Now consider the term of index $m=p^{t-1}-1$. By Lemma~\ref{lem2},
we know that
$s(n,m)=s\bigl(p^t,p^{t-1}-1\bigr)$ is divisible by $p$. It follows that
\begin{equation*}
v_p(p\cdot s\bigl(n,m\bigr)Z_m^{\langle p \rangle})\geq 1+1+v_p(Z_m^{\langle p \rangle})\geq 2+v_p(Z_m^{\langle p \rangle})\, . 
\end{equation*}
Since $m> p^{t-2}$, it also follows that $v_p(Z_m^{\langle p \rangle})> t-3$ by property (a) of Theorem \ref{th6}. Hence $v_p(Z_m^{\langle p \rangle})\geq t-2$ and we are done.
\item Now take $m$ such that $p^{t-1}+1 \leq m\leq 2^t-1$. By property (a) of Theorem \ref{th6}, we know that $v_p(Z_m^{\langle p \rangle})\geq t-1$ for such  $m$. It follows that
\begin{equation*}
v_p(p\cdot s(2^t,m)Z_m^{\langle p \rangle})\geq t\, , 
\end{equation*}
and we are done for this case also.
\item Now consider the value $m=p^{t-1}$. By the induction hypothesis,
it follows that $v_p(Z_m^{\langle p \rangle})=t-2$. By Lemma~\ref{lem2},
$s(n,m)=s\bigl(2^t,2^{t-1}\bigr))$ is not divisible by $p$.
It follows that the $p$-adic valuation of   $ps(n,m)Z_m^{\langle p
\rangle}$ is exactly $t-1$, and this is the only term in the sum with
this valuation, all the others have valuation  $\geq t$.

\end{enumerate}
Hence $v_p(Z_{p^t}^{\langle p \rangle})=t-1$. The proof of Theorem~\ref{th6} is now complete. 

\section{Acknowledgments} We thank the anonymous referee for her/his
careful reading, and for suggesting a more elegant proof of Proposition
\ref{pr1} and many other  improvements. We also thank Fred Weissler
for his help.

\begin{thebibliography}{9}
\bibitem{AM} Y. Amice, \emph{Les Nombres $p$-adiques}, Presses universitaires de France, 1975.
\bibitem{CO} L. Comtet, \emph{Advanced Combinatorics}, Reidel,
1974.
\bibitem{HO} F. T. Howard, Congruences for the
Stirling numbers and associated Stirling numbers. \emph{Acta Arith.}
{\bfseries 55} (1990), 29--41.  
\bibitem{LE} T. Lengyel, On some 2-adic
properties of a recurrence involving Stirling numbers.  
{\it p-Adic Numbers Ultrametric Anal. Appl.}
{\bf 4} (2012), 179--186.
\bibitem{OEIS} N. J. A. Sloane, 
\emph{The Online Encyclopedia of Integer Sequences},
\url{http://oeis.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip


\noindent 2010 \textit{Mathematics Subject Classification}: Primary 11B73;
Secondary 11F85.

\noindent \emph{Keywords:}  Lengyel's sequence, Stirling number,
congruence, $p$-adic property.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A005121}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 24 2014;
revised version received June 2 2014; June 16 2014. 
Published in {\it Journal of Integer Sequences}, June 17 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}