\documentclass[10pt]{article} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \usepackage{amsthm,amssymb} \usepackage{psfig,epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\D}{\displaystyle} \newcommand{\lrfloor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\lrpar}[1]{\left( #1 \right)} \newcommand{\pwp}[1]{ \frac{2^{#1}+1}{3}} \newcommand{\pwm}[1]{ \frac{2^{#1}-1}{3}} \newcommand{\jac}[1]{ \frac{2^{#1 +1}+(-1)^{#1}}{3}} \renewcommand{\lrpar}[1]{\left( #1 \right)} \renewcommand{\j}[1]{J_{#1}} \newcommand{\Nk}{N_k^{\#}(n)} \newcommand{\Dk}{D_k^{\#}(n)} \newcommand{\Nkjm}{N_k^{\#}(\j{m})} \newcommand{\Dkjm}{D_k^{\#}(\j{m})} \newcommand{\DD}[2]{D^{\#}_{#1}(#2)} \newcommand{\Nkl}{N_k^{\#}(2^{\ell})} \newcommand{\Dkl}{D_k^{\#}(2^{\ell})} \newcommand{\N}[2]{N^{\#}_{#1}(#2)} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newtheorem{Lemma}{Lemma}[section] \newtheorem{Theorem}[Lemma]{Theorem} \newtheorem{Prop}[Lemma]{Proposition} \newtheorem{Corollary}[Lemma]{Corollary} \newtheorem{Notation}[Lemma]{Notation} \newtheorem{Remark}[Lemma]{Remark} \newtheorem{Table}[Lemma]{Table} \renewcommand{\baselinestretch}{1.2} \renewcommand{\arraystretch}{.7} \makeatletter \def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\normalsize\bf}} \makeatother \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo23.eps} \vskip 1cm {\LARGE\bf Jacobsthal Numbers and Alternating Sign Matrices} \vskip 1.5cm %\author{\href{http://www.cedarville.edu/dept/sm/ddf_www.htm} \large Darrin D. Frey and James A. Sellers \\ \medskip %\href{http://www.cedarville.edu/dept/sm/jas_www.htm} Department of Science and Mathematics \\ Cedarville College \\ Cedarville, OH 45314 \\ \medskip Email addresses: \href{mailto:freyd@cedarville.edu}{freyd@cedarville.edu} and \href{mailto:sellersj@cedarville.edu}{sellersj@cedarville.edu} \vskip2.5cm \bf {Abstract} \end{center} {\em Let $A(n)$ denote the number of $n\times n$ alternating sign matrices and $J_m$ the $m^{th}$ Jacobsthal number. It is known that $$A(n) = \prod_{\ell =0}^{n-1}\frac{(3\ell +1)!}{(n+\ell )!}.$$ The values of $A(n)$ are in general highly composite. The goal of this paper is to prove that $A(n)$ is odd if and only if $n$ is a Jacobsthal number, thus showing that $A(n)$ is odd infinitely often. } \vspace*{+.1in} \noindent 2000 {\it Mathematics Subject Classification}: \ \ 05A10, 15A15 \noindent \emph{Keywords: alternating sign matrices, Jacobsthal numbers} \begin{section}{Introduction} In this paper we relate two seemingly unrelated areas of mathematics: alternating sign matrices and Jacobsthal numbers. We begin with a brief discussion of alternating sign matrices. An $n\times n$ alternating sign matrix is an $n\times n$ matrix of $1$s, $0$s and $-1$s such that \begin{itemize} \item the sum of the entries in each row and column is 1, and \item the signs of the nonzero entries in every row and column alternate. \end{itemize} Alternating sign matrices include permutation matrices, in which each row and column contains only one nonzero entry, a 1. For example, the seven $3\times 3$ alternating sign matrices are \[ \left( \begin{array}{ccc} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array} \right), \left( \begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{array} \right), \left( \begin{array}{ccc} 0 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{array} \right), \left( \begin{array}{ccc} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0 \end{array} \right), \] \[ \left( \begin{array}{ccc} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{array} \right), \left( \begin{array}{ccc} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array} \right), \left( \begin{array}{ccc} 0 & 1 & 0\\ 1 & -1& 1\\ 0 & 1 & 0 \end{array} \right)\,. \] The determination of a closed formula for $A(n)$ was undertaken by a variety of mathematicians over the last 25 years or so. David Bressoud's text \cite{Bressoud} chronicles these endeavors and discusses the underlying mathematics in a very readable way. See also the survey article \cite{notices} by Bressoud and Propp. As noted in \cite{Bressoud}, a formula for $A(n)$ is given by \begin{equation} \label{asmformula} A(n) = \prod_{\ell =0}^{n-1}\frac{(3\ell +1)!}{(n+\ell )!}. \end{equation} It is clear from this that, for most values of $n$, $A(n)$ will be highly composite. The following table shows the first few values of $A(n)$ (sequence \seqnum{A005130} in \cite{Sloane}). Other sequences related to alternating sign matrices can also be found in \cite{Sloane}. {\small \begin{center} \begin{tabular}{r|r|r} $n$ & \multicolumn{1}{c|}{$A(n)$} & \multicolumn{1}{c}{Prime Factorization of $A(n)$} \\ \hline 1 & 1 & 1\\ 2 & 2 & 2\\ 3 & 7 & 7\\ 4 & 42 & $2\cdot 3\cdot 7$\\ 5 & 429 & $ 3\cdot 11\cdot 13$\\ 6 & 7436 & $ 2^{2}\cdot 11\cdot 13^{2}$\\ 7 & 218348 & $ 2^{2}\cdot 13^{2}\cdot 17 \cdot 19$\\ 8 & 10850216 & $ 2^{3}\cdot 13\cdot 17^{2} \cdot 19^{2}$\\ 9 & 911835460 & $ 2^{2}\cdot 5\cdot 17^{2} \cdot 19^{3}\cdot 23$\\ 10& 129534272700 & $ 2^{2}\cdot 3\cdot 5^{2} \cdot 7\cdot 17\cdot 19^{3}\cdot 23^{2}$\\ 11 & 31095744852375 & $ 3^{2}\cdot 5^{3}\cdot 7 \cdot 19^{2}\cdot 23^{3}\cdot 29\cdot 31$\\ 12 & 12611311859677500 & $ 2^{2}\cdot 3^{3}\cdot 5^{4} \cdot 19\cdot 23^{3}\cdot 29^{2} \cdot 31^{2}$ \\ 13 & 8639383518297652500 & $ 2^{2}\cdot 3^{5}\cdot 5^{4} \cdot 23^{2}\cdot 29^{3}\cdot 31^{3} \cdot 37$ \\ 14 & 9995541355448167482000 & $ 2^{4}\cdot 3^{5}\cdot 5^{3} \cdot 23\cdot 29^{4}\cdot 31^{4} \cdot 37^{2}$ \\ 15 & 19529076234661277104897200 & $ 2^{4}\cdot 3^{3}\cdot 5^{2} \cdot 29^{4}\cdot 31^{5}\cdot 37^{3} \cdot 41\cdot 43$ \\ 16 & 64427185703425689356896743840 & $ 2^{5}\cdot 3^{2}\cdot 5 \cdot 11\cdot 29^{3}\cdot 31^{5}\cdot 37^{4}\cdot 41^{2}\cdot 43^{2}$ \\ 17 & 358869201916137601447486156417296 & $ 2^{4}\cdot 3\cdot 7^{2} \cdot 11\cdot 29^{2}\cdot 31^{4}\cdot 37^{5}\cdot 41^{3}\cdot 43^{3}\cdot 47$ \\ 18 & 3374860639258750562269514491522925456 & $ 2^{4}\cdot 7^{3}\cdot 13 \cdot 29\cdot 31^{3}\cdot 37^{6}\cdot 41^{4}\cdot 43^{4}\cdot 47^{2}$ \\ 19 & 53580350833984348888878646149709092313244 & $ 2^{2}\cdot 7^{3}\cdot 13^{2} \cdot 31^{2}\cdot 37^{6}\cdot 41^{5} \cdot 43^{5}\cdot 47^{3}\cdot 53$ \\ 20 & 1436038934715538200913155682637051204376827212 & $ 2^{2}\cdot 7^{4}\cdot 13^{2} \cdot 31\cdot 37^{5}\cdot 41^{6} \cdot 43^{6}\cdot 47^{4}\cdot 53^{2}$ \\ 21 & 64971294999808427895847904380524143538858551437757 & $ 7^{5}\cdot 13\cdot 37^{4}\cdot 41^{6}\cdot 43^{7}\cdot 47^{5} \cdot 53^{3}\cdot 59\cdot 61$ \\ 22 & 4962007838317808727469503296608693231827094217799731304 & $ 2^{3}\cdot 3\cdot 7^{6} \cdot 37^{3}\cdot 41^{5}\cdot 43^{7}\cdot 47^{6}\cdot 53^{4}\cdot 59^{2}\cdot 61^{2}$ \\ \hline \end{tabular} \end{center} \smallskip \centerline{Table 1: Values of $A(n)$} } \bigskip Examination of this table and further computer calculations reveals that the first few values of $n$ for which $A(n)$ is odd are $$1, 3, 5, 11, 21, 43, 85, 171.$$ These appear to be the well--known {\it Jacobsthal numbers} $\{J_n\}$ (sequence \seqnum{A001045} in \cite{Sloane}). They are defined by the recurrence \begin{equation} \label{jacrecur} \j{n+2} = \j{n+1}+2\j{n} ~, \end{equation} with initial values $\j{0} = 1$ and $\j{1}=1.$ This sequence has a rich history, especially in view of its relationship to the Fibonacci numbers. For examples of recent work involving the Jacobsthal numbers, see \cite{Horadam1}, \cite{Horadam2}, \cite{Horadam3} and \cite{Horadam4}. The goal of this paper is to prove that this is no coincidence: for a positive integer $n$, $A(n)$ is odd if and only if $n$ is a Jacobsthal number. \end{section} \begin{section}{The Necessary Machinery} To show that $A(\j{m})$ is odd for each positive integer $m$, we will show that the number of factors of 2 in the prime decomposition of $A(\j{m})$ is zero. To accomplish this, we develop formulas for the number of factors of 2 in $$N(n) = \prod_{\ell =0}^{n-1}{(3\ell +1)!} \qquad\mbox{and}\qquad D(n) = \prod_{\ell =0}^{n-1}{(n+\ell)!}~.$$ Once we prove that the number of factors of 2 is the same for $N(\j{m})$ and $D(\j{m})$, but not the same for $N(n)$ and $D(n)$ if $n$ is not a Jacobsthal number, we will have our result. We will make frequent use of the following lemma. For a proof, see for example \cite[Theorem 2.29]{Long}. \begin{Lemma} \label{pinnfact} The number of factors of a prime $p$ in $N!$ is equal to $$\sum\limits_{k\geq 1} \lrfloor{\frac{N}{p^k}}.$$ \end{Lemma} It follows that the number of factors of 2 in $N(n)$ is $$ N^{\#}(n) = \sum_{\ell =0}^{n-1}\sum_{k\geq 1} \lrfloor{\frac{3\ell +1}{2^k}} = \sum_{k\geq 1} N_k^{\#}(n) $$ where \begin{equation} \label{Nkformula} N_k^{\#}(n) = \sum_{\ell =0}^{n-1}\lrfloor{\frac{3\ell +1}{2^k}}. \end{equation} Similarly, the number of factors of 2 in $D(n)$ is given by $$ D^{\#}(n) = \sum_{\ell =0}^{n-1}\sum_{k\geq 1} \lrfloor{\frac{n+\ell}{2^k}} = \sum_{k\geq 1} D_k^{\#}(n) $$ where \begin{equation} \label{Dkformula} D_k^{\#}(n) = \sum_{\ell =0}^{n-1}\lrfloor{\frac{n+\ell}{2^k}}. \end{equation} For use below we note that the recurrence for the Jacobsthal numbers implies the following explicit formula (cf. \cite{Tucker}). \begin{Theorem} The $m^{th}$ Jacobsthal number $\j{m}$ is given by \begin{equation}\label{Eq4a} \j{m} = \frac{2^{m+1} + (-1)^m}{3}. \end{equation} \end{Theorem} \end{section} \begin{section}{Formulas for $N_k^{\#}(n)$ and $D_k^{\#}(n)$} \begin{Lemma} The smallest value of $\ell$ for which $$\D \lrfloor{\frac{3\ell + 1}{2^k}} =m,$$ where $m$ and $k$ are positive integers and $k \geq 2$, is $$ \left\{ \begin{array}{lcr} \frac{m}{3}2^k & & \quad\mbox{if}\quad m \equiv 0 \pmod 3\\ \frac{m-1}{3}2^k+\j{k-1} & & \quad\mbox{if}\quad m \equiv 1 \pmod 3\\ \frac{m-2}{3}2^k+\j{k} & & \quad\mbox{if}\quad m \equiv 2 \pmod 3. \end{array} \right. $$ \label{smallest} \end{Lemma} \begin{proof} Suppose $m\equiv 0 \pmod 3$ and $\D \ell = \frac{m}{3}2^k$. Then $$\lrfloor{\frac{3\ell + 1}{2^k}} = \lrfloor{\frac{3\lrpar{\frac{m}{3}2^k} + 1}{2^k}} = \lrfloor{\frac{m2^k}{2^k}+\frac{1}{2^k}} = m,$$ and no smaller value of $\ell$ yields $m$ since the numerators differ by multiples of three. If $m \equiv 1 \pmod 3$ and $\D \ell = \frac{m-1}{3}2^k+\j{k-1}$, then \begin{eqnarray*} \lrfloor{\frac{3\ell + 1}{2^k}} &=& \lrfloor{\frac{3\lrpar{\frac{m-1}{3}2^k+\j{k-1}} + 1}{2^k}}\\ &=& \lrfloor{\frac{(m-1)2^k+3\lrpar{\frac{2^k+(-1)^{k-1}}{3}}+1}{2^k}}\\ &=& \lrfloor{\frac{(m-1)2^k+2^k+(-1)^{k-1}+1}{2^k}}\\ &=& m, \ \ \mbox{if $k \geq 2$,} \end{eqnarray*} and no smaller value of $\ell$ yields $m$. If $m \equiv 2 \pmod 3$ and $\D \ell = \frac{m-2}{3}2^k+\j{k}$, then \begin{eqnarray*} \lrfloor{\frac{3\ell + 1}{2^k}} &=& \lrfloor{\frac{3\lrpar{\frac{m-2}{3}2^k+\j{k}} + 1}{2^k}}\\ &=& \lrfloor{\frac{(m-2)2^k+3\lrpar{\frac{2^{k+1}+(-1)^k}{3}}+1}{2^k}}\\ &=& \lrfloor{\frac{(m-2)2^k+2^{k+1}+(-1)^k+1}{2^k}}\\ &=& m, \end{eqnarray*} and no smaller value of $\ell$ yields $m$. \end{proof} \begin{Lemma} \label{2klemma} For any positive integer $k$, $\D \j{k-1} + \j{k} = 2^k.$ \end{Lemma} \begin{proof} Immediate from (\ref{Eq4a}). \end{proof} \begin{Lemma} \label{sum} For any positive integer $k$, $$\D \sum_{v=0}^{2^k-1}\lrfloor{\frac{3v+1}{2^k}} = 2^k.$$ \end{Lemma} \begin{proof} The result is immediate if $k=1$. If $k \geq 2$, then by Lemma~\ref{smallest}, $\j{k-1}$ is the smallest value of $v$ for which $\D \lrfloor{\frac{3v+1}{2^k}} = 1$ and $\j{k}$ is the smallest value of $v$ for which $\D \lrfloor{\frac{3v+1}{2^k}} = 2$. Thus \begin{eqnarray*} \sum_{v=0}^{2^k-1}\lrfloor{\frac{3v+1}{2^k}} &=& 0\times \j{k-1} + 1\times[(\j{k}-1)-(\j{k-1}-1)]+ 2\times[{(2^k-1)-(\j{k}-1)}]\\ &=& \j{k} - \j{k-1} + 2(2^k-\j{k})\\ &=& 2^{k+1}-2^k \ \ \mbox{by Lemma~\ref{2klemma}}\\ &=& 2^k~. \end{eqnarray*} \end{proof} \begin{Theorem} \label{Nkform} Let $n = 2^kq+r$, where $q$ is a nonnegative integer and $0\leq r<2^k.$ Then \begin{equation} \label{Nkformula2} N_k^{\#}(n) = \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+tail(n) \end{equation} where \begin{equation} \label{Nktail} tail(n) = \left\{ \begin{array} {l@{\ \ \mbox{if}\quad}l} 3qr & 0\leq r\leq \j{k-1} \\ 3qr+(r-\j{k-1}) & \j{k-1}< r\leq\j{k} \\ (3q+2)r-2^k & \j{k} < r<2^k. \end{array} \right. \end{equation} \end{Theorem} \begin{proof} To analyze the sum $$\D \Nk = \sum_{\ell = 0}^{n-1}\lrfloor{\frac{3\ell+1}{2^k}}$$ we let $\ell = 2^ku+v$, where $0 \leq v < 2^k$. Then $$\lrfloor{\frac{3\ell +1}{2^k}} = \lrfloor{\frac{3(2^ku+v)+1}{2^k}} = \lrfloor{\frac{2^k(3u)}{2^k}+\frac{3v+1}{2^k}} = 3u + \lrfloor{\frac{3v+1}{2^k}}.$$ \nopagebreak Thus \begin{eqnarray*} \sum_{\ell = 0}^{2^kq-1}\lrfloor{\frac{3\ell +1}{2^k}} &=& \sum_{u=0}^{q-1}\sum_{v=0}^{2^k-1}\lrpar{3u+\lrfloor{\frac{3v+1}{2^k}}}\\ &=& \sum_{u=0}^{q-1}\lrpar{(3u)2^k+\sum_{v=0}^{2^k-1}\lrfloor{\frac{3v+1}{2^k}}}\\ &=& \sum_{u=0}^{q-1}((3u)2^k+2^k) \ \ \ \ \mbox{by Lemma~\ref{sum}}\\ &=& 2^k\sum_{u=0}^{q-1}(3u+1)\\ &=& 2^k\lrpar{3\lrpar{\frac{(q-1)q}{2}}+q}\\ &=& 2^kq\lrpar{3\lrpar{\frac{n-r-2^k}{2^{k+1}}}+1}\\ &=& \lrpar{\frac{q}{2}}(3(n-r-2^k)+2^{k+1})\\ &=& \lrpar{\frac{n-r}{2^{k+1}}}(3(n-r)-2^k). \end{eqnarray*} If $r=0$, we have our result. If $r>0$ and $k=1$, then $r=1$ and we have one extra term in our sum, namely, $$\D \lrfloor{\frac{3(2q)+1}{2}}=3q$$ and again we have our result since $r=1$. If $r>0$ and $k \geq 2$, then by Lemma~\ref{smallest}, $2^kq$ is the smallest value of $\ell$ for which $\D \lrfloor{\frac{3\ell +1}{2^k}} = 3q$, $2^kq+\j{k-1}$ is the smallest value of $\ell$ for which $$\D \lrfloor{\frac{3\ell +1}{2^k}}=3q+1,$$ and $2^kq+\j{k}$ is the smallest value of $\ell$ for which $$\D \lrfloor{\frac{3\ell +1}{2^k}}=3q+2.$$ Hence $$\sum_{\ell = 2^kq}^{2^kq+r-1}\lrfloor{\frac{3\ell +1}{2^k}} = \left\{ \begin{array}{lcl} \D 3qr & & \quad\mbox{if }\quad r \leq \j{k-1}\\ \D 3q\j{k-1}+(3q+1)(r-\j{k-1}) & & \quad\mbox{if } \j{k-1} < r \leq \j{k}\\ \D 3q\j{k-1}+(3q+1)(\j{k}-\j{k-1})+(3q+2)(r-\j{k}) & & \quad\mbox{if } \j{k} < r < 2^k. \end{array} \right.$$ So, if $n = 2^kq+r$ where $0 \leq r < 2^k$, \begin{eqnarray*} \Nk &=& \sum_{\ell = 0}^{n-1}\lrfloor{\frac{3\ell +1}{2^k}}\\ &=& \sum_{\ell = 0}^{2^kq-1}\lrfloor{\frac{3\ell +1}{2^k}} + \sum_{\ell = 2^kq}^{2^kq+r-1}\lrfloor{\frac{3\ell +1}{2^k}}\\ &=& \lrpar{\frac{n-r}{2^{k+1}}}(3(n-r)-2^k) + tail(n), \end{eqnarray*} where $$tail(n) = \left\{ \begin{array}{lcl} \D 3qr & & \quad\mbox{if }\quad r \leq \j{k-1}\\ \D 3q\j{k-1}+(3q+1)(r-\j{k-1}) & & \quad\mbox{if } \j{k-1} < r \leq \j{k}\\ \D 3q\j{k-1}+(3q+1)(\j{k}-\j{k-1})+(3q+2)(r-\j{k}) & & \quad\mbox{if } \j{k} < r < 2^k.\\ \end{array} \right.$$ The second expression in $tail(n)$ is clearly equal to $3qr+r-\j{k-1}$. For the third expression, we have \begin{eqnarray*} 3q\j{k-1}+(3q+1)(\j{k}-\j{k-1})+(3q+2)(r-\j{k}) &=& 3qr+\j{k}-\j{k-1}+2r-2\j{k}\\ &=& (3q+2)r-2^k \ \ \mbox{by Lemma~\ref{2klemma}.} \end{eqnarray*} \end{proof} \begin{Theorem} \label{Dkform} Let $n = 2^kq+r$ where $q$ is a nonnegative integer and $0\leq r<2^k.$ Then we have \begin{equation} \label{Dkformula2} D_k^{\#}(n) = \left\{ \begin{array} {l@{\ \ \mbox{if}\quad}l} \D\left(\frac{n-r}{2^{k+1}}\right)(3(n+r)-2^k) & 0\leq r \leq 2^{k-1} \\ \D\left(\frac{n-(2^k-r)}{2^{k+1}}\right)(3(n-r)+2^{k+1}) & 2^{k-1} < r < 2^{k}.\\ \end{array} \right. \end{equation} \end{Theorem} \begin{proof} We may write $$D_k^{\#}(n) = \sum_{\ell = 0}^{2n-1}\lrfloor{\frac{\ell}{2^k}} - \sum_{\ell = 0}^{n-1}\lrfloor{\frac{\ell}{2^k}}.$$ In both sums, $$\D \lrfloor{\frac{\ell}{2^k}} = s\,,$$ if $2^{k}s \leq \ell < 2^{k}(s+1)$, so if $n = 2^kq+r$, where $0 < r \leq 2^k$, we have \begin{eqnarray*} \sum_{\ell = 0}^{n-1}\lrfloor{\frac{\ell}{2^k}} &=& 2^k [1+2+ \cdots + q-1] + qr \\ &=& q\lrpar{\frac{n+r-2^k}{2}}. \end{eqnarray*} If $0 \j{k-1}$ (in the notation of Theorem~\ref{Nkform}), $$N_k^{\# (2)}(n) > D_k^{\# (1)}(n) .$$ \end{Lemma} \begin{proof} \begin{eqnarray*} N_k^{\# (2)}(n) &=& \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+3qr+(r-J_{k-1})\\ &>& \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+3qr \ \ \mbox{since $r > \j{k-1}$}\\ &=& N_k^{\# (1)}(n)\\ &=& D_k^{\# (1)}(n) \ \ \mbox{ by Lemma~\ref{nk1=dk1}}. \end{eqnarray*} This proves our result. \end{proof} \begin{Lemma} For all integers $k$ and all integers $n$ such that $r \leq \j{k}$ (in the notation of Theorem~\ref{Nkform}), $$N_k^{\# (2)}(n) \geq D_k^{\# (2)}(n).$$ \end{Lemma} \begin{proof} We see that $r \leq \j{k} = 2^k - \j{k-1}$ by Lemma~\ref{2klemma}. Thus, $2^kq+r \leq 2^k(q+1)-\j{k-1}$. This implies $n \leq 2^k(q+1)-J_{k-1}$, so $2n-2^k(q+1) \leq n-J_{k-1}$. Hence, \begin{eqnarray*} \displaystyle N_k^{\# (2)}(n) &=& \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+3qr+(r-J_{k-1}) \\ &=& \frac{q}{2}(3(2^kq)-2^k)+3q(n-2^kq)+n-2^kq-J_{k-1} \\ &=& q^2(-3(2^{k-1}))+q(-3(2^{k-1})+3n)+n-J_{k-1} \\ &\geq& q^2(-3(2^{k-1}))+q(-3(2^{k-1})+3n)+2n-2^k(q+1) \ \ \mbox{by the above argument}\\ &=& \frac{2n-2^k-2^kq}{2^{k+1}}(3(2^kq)+2^{k+1})\\ &=& D_k^{\# (2)}(n). \end{eqnarray*} \end{proof} \begin{Lemma} \label{nk3=dk2} For all positive integers $n$ and $k$, $N_k^{\# (3)}(n) = D_k^{\# (2)}(n)$. \end{Lemma} \begin{proof} \begin{eqnarray*} N_k^{\# (3)}(n) &=& \lrpar{\frac{n-r}{2^{k+1}}}(3(n-r)-2^k)+(3q+2)r-2^k\\ &=& \lrpar{\frac{q}{2}}(3(2^kq)-2^k)+3q(n-2^kq)+2(n-2^kq)-2^k\\ &=& \frac{n-2^k+n-2^kq}{2^k+1}(3(2^kq)+2^{k+1})\\ &=& D_k^{\# (2)}(n). \end{eqnarray*} \end{proof} \begin{Remark} \label{remark} To summarize, Lemmas~\ref{nk1=dk1} through \ref{nk3=dk2} tell us that for any positive integer $n$, $$\Nk \geq \Dk.$$ \end{Remark} For Propositions~\ref{firstprop} through \ref{lastprop} we make the assumption that $\j{\ell} < n < \j{\ell +1}$ for some positive integer $\ell$. \begin{Prop} \label{firstprop} For $\ell$ and $n$, as given above, $\N{\ell +1}{n} = n - J_{\ell}$. \end{Prop} \begin{proof} By Lemma~\ref{smallest}, \begin{eqnarray*} \sum_{i=0}^{n-1}\lrfloor{\frac{3i+1}{2^{\ell+1}}} &=& 0\times(\j{\ell}) + 1\times((n-1)-(\j{\ell}-1))\\ &=& n-\j{\ell}. \end{eqnarray*} \end{proof} \begin{Prop} \label{secondprop} $D_k^{\#}(n) = 0$ if $n < 2^{k-1}$. In particular, $D_{\ell + 1}^{\#}(n) = 0$ if $n < 2^{\ell}$. \end{Prop} \begin{proof} If $n < 2^k$ then, in the notation of Theorem~\ref{Dkform}, $n=r$ and $q=0$, so by Theorem~\ref{Dkform}, $D_k^{\#}(n) = 0$. \end{proof} \begin{Prop} \label{thirdprop} $\D D^{\#}_{\ell +1}(n) = 2(n-2^{\ell})$ if $2^{\ell} \leq n < J_{\ell +1}$. \end{Prop} \begin{proof} If $2^{\ell} \leq n < J_{\ell +1}$ then, in the notation of Theorem~\ref{Dkform}, $q=0$ and $r = n$. Since $n \geq 2^{\ell}$, we are in the second case of Theorem~\ref{Dkform} so $$ D^{\#}_{\ell +1}(n) = \frac{n-2^{\ell +1}+n}{2^{\ell +2}}(0+2^{\ell +2})\\ = 2(n-2^{\ell}). $$ \end{proof} \begin{Prop} \label{lastprop} For $n$ and $\ell$ as given above, $2(n-2^{\ell}) < n-\j{\ell}$. \end{Prop} \begin{proof} We begin by showing that $\j{\ell +1}-2^{\ell} = 2^{\ell} - \j{\ell}$. We have \begin{eqnarray*} \j{\ell +1}-2^{\ell} &=& \frac{2^{\ell+2}+(-1)^{\ell +1}}{3}-2^{\ell}\\ &=& 2^{\ell}-\jac{\ell}\\ &=& 2^{\ell}-\j{\ell}, \end{eqnarray*} and hence \begin{eqnarray*} 2(n-2^{\ell}) &=& n-2^{\ell}+n-2^{\ell}\\ &<& n-2^{\ell}+\j{\ell +1}-2^{\ell}\\ &=& n-2^{\ell}+2^{\ell}-\j{\ell} \ \ \mbox{from the above argument}\\ &=& n-\j{\ell} \end{eqnarray*} so we have our result. \end{proof} We are now ready to prove our theorem. \begin{Theorem} $A(n)$ is even if $n$ is not a Jacobsthal number. \label{conversethm} \end{Theorem} \begin{proof} Our goal is to show that there is some $k$ such that $\Nk$ is strictly greater than $\Dk$ since, by Remark~\ref{remark}, we have shown that $\Nk \geq \Dk$ for all positive integers $k$ and $n$. Given $n$, not a Jacobsthal number, there exists a positive integer $\ell$ such that $\j{\ell} < n < \j{\ell + 1}$. Then $N_{\ell +1}^{\#}(n) = n - \j{\ell}$ by Proposition~\ref{firstprop}, and since $n > \j{\ell}$, $N_{\ell +1}^{\#}(n) > 0$. On the other hand, by Proposition~\ref{secondprop}, if $n< 2^{\ell}$, then $D_{\ell +1}^{\#}(n)=0$. If $2^{\ell} \leq n < \j{\ell +1}$, then by Proposition~\ref{thirdprop}, $D_{\ell +1}^{\#}(n) = 2(n-2^{\ell})$ which is strictly less than $n - \j{\ell} = N_{\ell +1}^{\#}(n)$ by Proposition~\ref{lastprop}. Hence, in every case, $N_{\ell +1}^{\#}(n)$ is strictly greater than $D_{\ell +1}^{\#}(n)$ so there is at least one factor of two in $A(n)$ and we have our result. \end{proof} \end{section} \begin{section}{A Closing Remark} We close by noting that we can prove a stronger result than Theorem~\ref{conversethm}. If $J_{\ell} < n < J_{\ell +1}$, then $$\N{\ell +1}{n} - \DD {\ell +1}{n} = \left\{ \begin{array}{lcl} n-J_{\ell} & \mbox{if} & J_{\ell} < n \leq 2^{\ell}\\ J_{\ell +1} -n & \mbox{if} & 2^{\ell} \leq n < J_{\ell +1}\\ \end{array} \right.$$ by Propositions~\ref{firstprop}, \ref{secondprop}, \ref{thirdprop} and Lemma~\ref{2klemma}. Let $ord_2(n)$ be the highest power of 2 that divides $n$. By Remark~\ref{remark}, $\Nk - \Dk \geq 0$ for all $n$ and for all $k$, so that $$ord_2(A(n)) \geq \left\{ \begin{array}{lcl} n-J_{\ell} & \mbox{if} & J_{\ell} < n \leq 2^{\ell}\\ J_{\ell +1} -n & \mbox{if} & 2^{\ell} \leq n < J_{\ell +1}\\ \end{array}, \right.$$ which strengthens Theorem~\ref{conversethm}. Finally, we see that $ord_2(A(2^{\ell})) = J_{\ell -1}$ since, for all $k < \ell + 1, \Nkl = N_k^{\# (1)}(2^{\ell}) = D_k^{\# (1)}(2^{\ell}) = \Dkl$, and $2^{\ell}-J_{\ell} = J_{\ell +1}-2^{\ell} = J_{\ell - 1}$. So, for example, we know that $A(2^{10})$ is divisible by $2^{J_9}$, which equals $2^{341}$, and that $A(2^{10})$ is not divisible by $2^{342}.$ \end{section} \begin{section}{Acknowledgements} The authors gratefully acknowledge the excellent technical help of Robert Schumacher in the preparation of this document. \end{section} \begin{thebibliography}{99} \bibitem{Bressoud} D. M. Bressoud, ``Proofs and Confirmations: The story of the alternating sign matrix conjecture'', Cambridge University Press, 1999. \bibitem{notices} D. M. Bressoud and J. Propp, How the Alternating Sign Matrix Conjecture Was Solved, \emph{Notices of the American Mathematical Society}, \textbf{46} (6) (1999), 637-646. \bibitem{Horadam1} A. F. Horadam, Jacobsthal Representation Numbers, \emph{Fibonacci Quarterly}, \textbf{34} (1) (1996), 40-53. \bibitem{Horadam2} A. F. Horadam, Jacobsthal Representation Polynomials, \emph{Fibonacci Quarterly}, \textbf{35} (2) (1997), 137-148. \bibitem{Horadam3} A. F. Horadam, Rodriques' Formulas for Jacobsthal-Type Polynomials, \emph{Fibonacci Quarterly}, \textbf{35} (4) (1997), 361-370. \bibitem{Horadam4} A. F. Horadam and P. Filipponi, Derivative Sequences of Jacobsthal and Jacobsthal-Lucas Polynomials, \emph{Fibonacci Quarterly}, \textbf{35} (4) (1997), 352-357. \bibitem{Long} C. T. Long, ``Elementary Introduction to Number Theory'', 3rd edition, Waveland Press, Inc., Prospect Heights, IL, 1995. \bibitem{Sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim $njas/sequences/}{http://www.research.att.com/~njas/sequences/}. \bibitem{Tucker} A. Tucker, ``Applied Combinatorics'', 3rd edition, John Wiley \& Sons, 1995. \end{thebibliography} \vspace*{+.5in} \centerline{\rule{6.5in}{.01in}} \vspace*{+.1in} \noindent {\small (Concerned with sequences \htmladdnormallink{A001045}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001045}, \htmladdnormallink{A001859}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001859} and \htmladdnormallink{A005130}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005130}.) } \centerline{\rule{6.5in}{.01in}} \vspace*{+.1in} \noindent Received Jan. 13, 2000; published in Journal of Integer Sequences June 1, 2000. \centerline{\rule{6.5in}{.01in}} \vspace*{+.1in} \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www. research.att.com/~njas/sequences/JIS/}. \centerline{\rule{6.5in}{.01in}} \end{document}