Jacobsthal Numbers and Alternating Sign Matrices

Darrin D. Frey and James A. Sellers

Department of Science and Mathematics Cedarville College Cedarville, OH 45314

Email addresses: freyd@cedarville.edu and sellersj@cedarville.edu

Abstract

Let A(n) denote the number of n × n alternating sign matrices and J_{m} the m^{th} Jacobsthal number. It is known that

A(n) = ∏_{ℓ=0}^{n−1} \frac{(3ℓ + 1)!}{(n + ℓ)!}.

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.

2000 Mathematics Subject Classification: 05A10, 15A15 Keywords: alternating sign matrices, Jacobsthal numbers

1 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 × n alternating sign matrix is an n × n matrix of 1s, 0s and −1s such that

• the sum of the entries in each row and column is 1, and

• the signs of the nonzero entries in every row and column alternate.

Alternating sign matrices include permutation matrices, in which each row and column contains only one nonzero entry, a 1.

For example, the seven 3 × 3 alternating sign matrices are

( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ) , ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} ) ,

( \begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} ) , ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 1 & 0 \\ 1 & −1 & 1 \\ 0 & 1 & 0 \end{matrix} ) .

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 [1] chronicles these endeavors and discusses the underlying mathematics in a very readable way. See also the survey article [2] by Bressoud and Propp.

As noted in [1], a formula for A(n) is given by

A(n) = ∏_{ℓ=0}^{n−1} \frac{(3ℓ + 1)!}{(n + ℓ)!}.  (1)

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 \underline{A005130} in [8]). Other sequences related to alternating sign matrices can also be found in [8].

n  A(n)  Prime Factorization of A(n)
1  1  1
2  2  2
3  7  7
4  42  2 · 3 · 7
5  429  3 · 11 · 13
6  7436  2^{2} · 11 · 13^{2}
7  218348  2^{2} · 13^{2} · 17 · 19
8  10850216  2^{3} · 13 · 17^{2} · 19^{2}
9  911835460  2^{2} · 5 · 17^{2} · 19^{3} · 23
10  129534272700  2^{2} · 3 · 5^{2} · 7 · 17 · 19^{3} · 23^{2}
11  31095744852375  3^{2} · 5^{3} · 7 · 19^{2} · 23^{3} · 29 · 31
12  12611311859677500  2^{2} · 3^{3} · 5^{4} · 19 · 23^{3} · 29^{2} · 31^{2}
13  8639383518297652500  2^{2} · 3^{5} · 5^{4} · 23^{2} · 29^{3} · 31^{3} · 37
14  9995541355448167482000  2^{4} · 3^{5} · 5^{3} · 23 · 29^{4} · 31^{4} · 37^{2}
15  19529076234661277104897200  2^{4} · 3^{3} · 5^{2} · 29^{4} · 31^{5} · 37^{3} · 41 · 43
16  64427185703425689356896743840  2^{5} · 3^{2} · 5 · 11 · 29^{3} · 31^{5} · 37^{4} · 41^{2} · 43^{2}
17  358869201916137601447486156417296  2^{4} · 3 · 7^{2} · 11 · 29^{2} · 31^{4} · 37^{5} · 41^{3} · 43^{3} · 47
18  3374860639258750562269514491522925456  2^{4} · 7^{3} · 13 · 29 · 31^{3} · 37^{6} · 41^{4} · 43^{4} · 47^{2}
19  53580350833984348888878646149709092313244  2^{2} · 7^{3} · 13^{2} · 31^{2} · 37^{6} · 41^{5} · 43^{5} · 47^{3} · 53
20  1436038934715538200913155682637051204376827212  2^{2} · 7^{4} · 13^{2} · 31 · 37^{5} · 41^{6} · 43^{6} · 47^{4} · 53^{2}
21  64971294999808427895847904380524143538858551437757  7^{5} · 13 · 37^{4} · 41^{6} · 43^{7} · 47^{5} · 53^{3} · 59 · 61
22 4962007838317808727469503296608693231827094217799731304 2^{3} · 3 · 7^{6} · 37^{3} · 41^{5} · 43^{7} · 47^{6} · 53^{4} · 59^{2} · 61^{2}

Table 1: Values of A(n)

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 Jacobsthal numbers \{J_{n}\} (sequence \underline{A001045} in [8]). They are defined by the recurrence

J_{n+2} = J_{n+1} + 2J_{n} ,  (2)

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 [3], [4], [5] and [6].

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.

2 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) = ∏_{ℓ=0}^{n−1} (3ℓ + 1)!  and  D(n) = ∏_{ℓ=0}^{n−1} (n + ℓ)! .

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 [7, Theorem 2.29].

Lemma 2.1. The number of factors of a prime p in N! is equal to

∑_{k≥1} ⌊\frac{N}{p^{k}} ⌋ .

It follows that the number of factors of 2 in N(n) is

N^{#}(n) = ∑_{ℓ=0}^{n−1} ∑_{k≥1} ⌊\frac{3ℓ + 1}{2^{k}}⌋ = ∑_{k≥1} N_{k}^{#}(n)

where

N_{k}^{#}(n) = ∑_{ℓ=0}^{n−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋ .  (3)

Similarly, the number of factors of 2 in D(n) is given by

D^{#}(n) = ∑_{ℓ=0}^{n−1} ∑_{k≥1} ⌊\frac{n + ℓ}{2^{k}}⌋ = ∑_{k≥1} D_{k}^{#}(n)

where

D_{k}^{#}(n) = ∑_{ℓ=0}^{n−1} ⌊\frac{n + ℓ}{2^{k}}⌋ .  (4)

For use below we note that the recurrence for the Jacobsthal numbers implies the following explicit formula (cf. [9]).

Theorem 2.2. The m^{th} Jacobsthal number J_{m} is given by

J_{m} = \frac{2^{m+1} + (−1)^{m}}{3} .  (5)

3 Formulas for N_{k}^{#}(n) and D_{k}^{#}(n)

Lemma 3.1. The smallest value of ℓ for which

⌊\frac{3ℓ + 1}{2^{k}}⌋ = m,

where m and k are positive integers and k ≥ 2, is

\frac{m}{3}2^{k}  if m ≡ 0 (mod 3)
\frac{m−1}{3}2^{k} + J_{k−1}  if m ≡ 1 (mod 3)
\frac{m−2}{3}2^{k} + J_{k}  if m ≡ 2 (mod 3).

Proof. Suppose m ≡ 0 (mod 3) and ℓ = \frac{m}{3}2^{k}. Then

⌊\frac{3ℓ + 1}{2^{k}}⌋ = ⌊\frac{3 (\frac{m}{3}2^{k}) + 1}{2^{k}}⌋ = ⌊\frac{m2^{k}}{2^{k}} + \frac{1}{2^{k}} ⌋ = m,

and no smaller value of ℓ yields m since the numerators differ by multiples of three. If m ≡ 1 (mod 3) and ℓ = \frac{m − 1}{3}2^{k} + J_{k−1}, then

⌊\frac{3ℓ + 1}{2^{k}}⌋ = ⌊\frac{3 (\frac{m−1}{3}2^{k} + J_{k−1}) + 1}{2^{k}}⌋
= ⌊\frac{(m − 1)2^{k} + 3 (\frac{2^{k}+(−1)^{k−1}}{3} ) + 1}{2^{k}} ⌋
= ⌊\frac{(m − 1)2^{k} + 2^{k} + (−1)^{k−1} + 1}{2^{k}}⌋
= m, if k ≥ 2,

and no smaller value of ℓ yields m.

If m ≡ 2 (mod 3) and ℓ = \frac{m − 2}{3}2^{k} + J_{k}, then

⌊\frac{3ℓ + 1}{2^{k}}⌋ = ⌊\frac{3 (\frac{m−2}{3}2^{k} + J_{k}) + 1}{2^{k}}⌋
= ⌊\frac{(m − 2)2^{k} + 3 (\frac{2^{k+1}+(−1)^{k}}{3} ) + 1}{2^{k}} ⌋
= ⌊\frac{(m − 2)2^{k} + 2^{k+1} + (−1)^{k} + 1}{2^{k}}⌋
= m,

and no smaller value of ℓ yields m.

Lemma 3.2. For any positive integer k, J_{k−1} + J_{k} = 2^{k}.

Proof. Immediate from (5).

Lemma 3.3. For any positive integer k,

∑_{v=0}^{2^{k}−1} ⌊\frac{3v + 1}{2^{k}}⌋ = 2^{k}.

Proof. The result is immediate if k = 1. If k ≥ 2, then by Lemma 3.1, J_{k−1} is the smallest value of v for which ⌊\frac{3v + 1}{2^{k}}⌋ = 1 and J_{k} is the smallest value of v for which ⌊\frac{3v + 1}{2^{k}}⌋ = 2. Thus

∑_{v=0}^{2^{k}−1} ⌊\frac{3v + 1}{2^{k}}⌋ = 0 × J_{k−1} + 1 × [(J_{k} − 1) − (J_{k−1} − 1)] + 2 × [(2^{k} − 1) − (J_{k} − 1)]
= J_{k} − J_{k−1} + 2(2^{k} − J_{k})
= 2^{k+1} − 2^{k} by Lemma 3.2
= 2^{k} .

Theorem 3.4. Let n = 2^{k}q + r, where q is a nonnegative integer and 0 ≤ r < 2^{k}. Then

N_{k}^{#}(n) = (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + tail(n)  (6)

where

tail(n) = \{ \begin{matrix}3qr  if & 0 ≤ r ≤ J_{k−1} \\ 3qr + (r − J_{k−1}) if & J_{k−1} < r ≤ J_{k} \\ (3q + 2)r − 2^{k} if & J_{k} < r < 2^{k}. \end{matrix}  (7)

Proof. To analyze the sum

N_{k}^{#}(n) = ∑_{ℓ=0}^{n−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋

we let ℓ = 2^{k}u + v, where 0 ≤ v < 2^{k}. Then

⌊\frac{3ℓ + 1}{2^{k}}⌋ = ⌊\frac{3(2^{k}u + v) + 1}{2^{k}}⌋ = ⌊\frac{2^{k}(3u)}{2^{k}} + \frac{3v + 1}{2^{k}}⌋ = 3u + ⌊\frac{3v + 1}{2^{k}}⌋ .

Thus

∑_{ℓ=0}^{2^{k}q−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋ = ∑_{u=0}^{q−1} ∑_{v=0}^{2^{k}−1} (3u + ⌊\frac{3v + 1}{2^{k}}⌋)
= ∑_{u=0}^{q−1} ((3u)2^{k} + ∑_{v=0}^{2^{k}−1} ⌊\frac{3v + 1}{2^{k}}⌋)
= ∑_{u=0}^{q−1}((3u)2^{k} + 2^{k}) by Lemma 3.3
= 2^{k} ∑_{u=0}^{q−1}(3u + 1)
= 2^{k} (3 (\frac{(q − 1)q}{2} ) + q)

= 2^{k}q (3 (\frac{n − r − 2^{k}}{2^{k+1}} ) + 1)
= (\frac{q}{2}) (3(n − r − 2^{k}) + 2^{k+1})
= (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}).

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,

⌊\frac{3(2q) + 1}{2}⌋ = 3q

and again we have our result since r = 1. If r > 0 and k ≥ 2, then by Lemma 3.1, 2^{k}q is the smallest value of ℓ for which ⌊\frac{3ℓ + 1}{2^{k}}⌋ = 3q, 2^{k}q + J_{k−1} is the smallest value of ℓ for which

⌊\frac{3ℓ + 1}{2^{k}}⌋ = 3q + 1,

and 2^{k}q + J_{k} is the smallest value of ℓ for which

⌊\frac{3ℓ + 1}{2^{k}}⌋ = 3q + 2.

Hence

∑_{ℓ=2^{k}q}^{2^{k}q+r−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋ = \{ \begin{matrix}3qr & if r ≤ J_{k−1} \\ 3qJ_{k−1} + (3q + 1)(r − J_{k−1}) & if J_{k−1} < r ≤ J_{k} \\ 3qJ_{k−1} + (3q + 1)(J_{k} − J_{k−1}) + (3q + 2)(r − J_{k}) & if J_{k} < r < 2^{k}. \end{matrix}

So, if n = 2^{k}q + r where 0 ≤ r < 2^{k},

N_{k}^{#}(n) = ∑_{ℓ=0}^{n−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋

= ∑_{ℓ=0}^{2^{k}q−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋ + ∑_{ℓ=2^{k}q}^{2^{k}q+r−1} ⌊\frac{3ℓ + 1}{2^{k}}⌋
= (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + tail(n),

where

tail(n) = \{ \begin{matrix}3qr & if r ≤ J_{k−1} \\ 3qJ_{k−1} + (3q + 1)(r − J_{k−1}) & if J_{k−1} < r ≤ J_{k} \\ 3qJ_{k−1} + (3q + 1)(J_{k} − J_{k−1}) + (3q + 2)(r − J_{k}) & if J_{k} < r < 2^{k}. \end{matrix}

The second expression in tail(n) is clearly equal to 3qr + r − J_{k−1}. For the third expression, we have

3qJ_{k−1} + (3q + 1)(J_{k} − J_{k−1}) + (3q + 2)(r − J_{k}) = 3qr + J_{k} − J_{k−1} + 2r − 2J_{k}
= (3q + 2)r − 2^{k} by Lemma 3.2.

Theorem 3.5. Let n = 2^{k}q + r where q is a nonnegative integer and 0 ≤ r < 2^{k}. Then we have

D_{k}^{#}(n) = \{ \begin{matrix}(\frac{n − r}{2^{k+1}} ) (3(n + r) − 2^{k})  if & 0 ≤ r ≤ 2^{k−1} \\ (\frac{n − (2^{k} − r)}{2^{k+1}}) (3(n − r) + 2^{k+1}) if & 2^{k−1} < r < 2^{k}. \end{matrix}  (8)

Proof. We may write

D_{k}^{#}(n) = ∑_{ℓ=0}^{2n−1} ⌊\frac{ℓ}{2^{k}} ⌋ − ∑_{ℓ=0}^{n−1} ⌊\frac{ℓ}{2^{k}} ⌋ .

In both sums,

⌊\frac{ℓ}{2^{k}} ⌋ = s ,

if 2^{k}s ≤ ℓ < 2^{k}(s + 1), so if n = 2^{k}q + r, where 0 < r ≤ 2^{k}, we have

∑_{ℓ=0}^{n−1} ⌊\frac{ℓ}{2^{k}} ⌋ = 2^{k}[1 + 2 + ⋯ + q − 1] + qr
= q (\frac{n + r − 2^{k}}{2} ) .

If 0 < r ≤ 2^{k−1}, then 2n − 1 = 2^{k}(2q) + (2r − 1), which means

∑_{ℓ=0}^{2n−1} ⌊\frac{ℓ}{2^{k}} ⌋ = 2^{k}[1 + 2 + ⋯ + (2q − 1)] + (2r − 1 + 1)(2q)
= q(2n + 2r − 2^{k}).

Hence in this case

D_{k}^{#}(n) = ∑_{ℓ=0}^{n−1} ⌊\frac{n + ℓ}{2^{k}}⌋
= ∑_{ℓ=0}^{2n−1} ⌊\frac{ℓ}{2^{k}} ⌋ − ∑_{ℓ=0}^{n−1} ⌊\frac{ℓ}{2^{k}} ⌋
= q(2n + 2r − 2^{k}) − q (\frac{n + r − 2^{k}}{2} )
= (\frac{n − r}{2^{k+1}} ) (3(n + r) − 2^{k}).

If 2^{k−1} < r ≤ 2^{k}, say, r = 2^{k−1} + s where 0 < s ≤ 2^{k−1}, then

2n − 1 = 2(2^{k}q + r) − 1
= 2^{k}(2q) + 2(2^{k−1} + s) − 1
= 2^{k}(2q + 1) + 2s − 1.

Thus

∑_{ℓ=0}^{2n−1} ⌊\frac{ℓ}{2^{k}} ⌋ = 2^{k}[1 + 2 + ⋯ + 2q] + (2s − 1 + 1)(2q + 1)
= (2q + 1)(n + r − 2^{k}).

So in this case

D_{k}^{#}(n) = ∑_{ℓ=0}^{n−1} ⌊\frac{n + ℓ}{2^{k}}⌋
= ∑_{ℓ=0}^{2n−1} ⌊\frac{ℓ}{2^{k}} ⌋ − ∑_{ℓ=0}^{n−1} ⌊\frac{ℓ}{2^{k}} ⌋
= (2q + 1)(n + r − 2^{k}) − q (\frac{n + r − 2^{k}}{2} )
= (\frac{n + r − 2^{k}}{2^{k+1}} ) (3(n − r) + 2^{k+1}).

The reader will note that in the statement of the theorem we have separated the cases according as 0 ≤ r ≤ 2^{k−1} and 2^{k−1} < r < 2^{k}, whereas in the proof the cases are 0 < r ≤ 2^{k−1} and 2^{k−1} < r ≤ 2^{k}. However, these are equivalent since \frac{n − 0}{2^{k+1}}(3(n + 0) − 2^{k}) = \frac{n − (2^{k} − 2^{k})}{2^{k+1}}(3(n − 2^{k}) + 2^{k+1}).

4 A(J_{m}) is odd

Now that we have closed formulas for N_{k}^{#}(n) and D_{k}^{#}(n) we can proceed to prove that A(J_{m}) is odd for all Jacobsthal numbers J_{m}.

Theorem 4.1. For all positive integers m, A(J_{m}) is odd.

Proof. The proof simply involves substituting J_{m} into (6) and (8) and showing that N_{k}^{#}(J_{m}) = D_{k}^{#}(J_{m}) for all k. This implies that N^{#}(J_{m}) = D^{#}(J_{m}), and so the number of factors of 2 in A(J_{m}) is zero. Our theorem is then proved.

We break the proof into two cases, based on whether the parity of k is equal to the parity of m.

• Case 1: The parity of m equals the parity of k. Then

2^{k}(J_{m−k} − 1) + J_{k} = 2^{k} (\frac{2^{m−k+1} + (−1)^{m−k}}{3} − 1) + \frac{2^{k+1} + (−1)^{k}}{3}
= \frac{2^{m+1} + 2^{k} − 3 · 2^{k} + 2^{k+1} + (−1)^{k}}{3} since (−1)^{m−k} = 1
= \frac{2^{m+1} + (−1)^{m}}{3} since (−1)^{k} = (−1)^{m}
= J_{m}

Thus, in the notation of Theorems 3.4 and 3.5, q = J_{m−k} − 1 and r = J_{k}. We now calculate N_{k}^{#}(J_{m}) and D_{k}^{#}(J_{m}) using Theorems 3.4 and 3.5.

N_{k}^{#}(J_{m}) = (\frac{J_{m} − J_{k}}{2^{k+1}} ) (3(J_{m} − J_{k}) − 2^{k})

+ 3(J_{m−k} − 1)J_{k} + (J_{k} − J_{k−1})

= \frac{1}{2^{k+1}} (\frac{2^{m+1} + (−1)^{m}}{3} − \frac{2^{k+1} + (−1)^{k}}{3} ) (3 (\frac{2^{m+1} + (−1)^{m}}{3} − \frac{2^{k+1} + (−1)^{k}}{3} ) − 2^{k})

+ (3J_{m−k} − 1)J_{k} − 2^{k} by Lemma 3.2

= \frac{1}{3 · 2^{k+1}} (2^{m+1} − 2^{k+1}) (2^{m+1} − 2^{k+1} − 2^{k})

+ (3 (\frac{2^{m−k+1} + (−1)^{m−k}}{3} ) − 1) (\frac{2^{k+1} + (−1)^{k}}{3} ) − 2^{k} since (−1)^{m} = (−1)^{k}

= \frac{1}{3} (2^{2m−k+1} − 2^{m+2} + 2^{k+1} − 2^{m} + 2^{k})

+ \frac{1}{3}(2^{m−k+1}(2^{k+1} + (−1)^{k}) − 3 · 2^{k}) since (−1)^{m−k} = 1

= \frac{1}{3} (2^{2m−k+1} − 2^{m} + (−1)^{k}2^{m−k+1})

after much simplification. Next, we calculate D_{k}^{#}(J_{m}), recalling that 2^{k−1} < r = J_{k} < 2^{k}.

D_{k}^{#}(J_{m}) = \frac{(J_{m} − 2^{k} + J_{k})}{2^{k+1}} (3(J_{m} − J_{k}) + 2^{k+1})
= \frac{1}{2^{k+1}} (\frac{2^{m+1} + (−1)^{m}}{3} + \frac{2^{k+1} + (−1)^{k}}{3} − 2^{k}) (3 (\frac{2^{m+1} + (−1)^{m}}{3} − \frac{2^{k+1} + (−1)^{k}}{3} ) + 2^{k+1})
= \frac{1}{3 · 2^{k+1}} (2^{m+1} + 2^{k+1} + 2(−1)^{k} − 3 · 2^{k}) (2^{m+1} − 2^{k+1} + 2^{k+1}) since (−1)^{m} = (−1)^{k}
= \frac{1}{3} (2^{2m−k+1} + 2^{m+1} + 2^{m−k+1}(−1)^{k} − 3 · 2^{m})
= \frac{1}{3} (2^{2m−k+1} − 2^{m} + (−1)^{k}2^{m−k+1})

after simplification. We see that N_{k}^{#}(J_{m}) = D_{k}^{#}(J_{m}).

• Case 2: The parity of m is not equal to the parity of k. Then

2^{k}(J_{m−k}) + J_{k−1} = 2^{k} (\frac{2^{m−k+1} + (−1)^{m−k}}{3} ) + \frac{2^{k} + (−1)^{k−1}}{3}
= \frac{2^{m+1} − 2^{k} + 2^{k} + (−1)^{k−1}}{3}
= J_{m}.

Thus, in the notation of Theorems 3.4 and 3.5, q = J_{m−k} and r = J_{k−1}. We now calculate N_{k}^{#}(J_{m}) and D_{k}^{#}(J_{m}) using Theorems 3.4 and 3.5.

N_{k}^{#}(J_{m}) = (\frac{J_{m} − J_{k−1}}{2^{k+1}} ) (3(J_{m} − J_{k−1}) − 2^{k})
+ 3J_{m−k}J_{k−1}

= \frac{1}{2^{k+1}} (\frac{2^{m+1} + (−1)^{m}}{3} − \frac{2^{k} + (−1)^{k−1}}{3} ) (3 (\frac{2^{m+1} + (−1)^{m}}{3} − \frac{2^{k} + (−1)^{k−1}}{3} ) − 2^{k})

+ 3 (\frac{2^{m−k+1} + (−1)^{m−k}}{3} ) (\frac{2^{k} + (−1)^{k−1}}{3} )

= \frac{1}{3 · 2^{k+1}} (2^{m+1} − 2^{k}) (2^{m+1} − 2 · 2^{k})

+ \frac{1}{3}((2^{m−k+1} − 1)(2^{k} + (−1)^{k−1})) since (−1)^{m} = (−1)^{k−1} and (−1)^{m−k} = −1

= \frac{1}{3}(2^{2m−k+1} − 2^{m+1} − 2^{m} + 2^{k} + 2^{m+1} − 2^{k} + 2^{m−k+1}(−1)^{k−1} + (−1)^{k})
= \frac{1}{3}(2^{2m−k+1} − 2^{m} + 2^{m−k+1}(−1)^{k−1} + (−1)^{k})

after much simplification. Again we find that N_{k}^{#}(J_{m}) = D_{k}^{#}(J_{m}).

Now we calculate D_{k}^{#}(J_{m}), recalling that 0 < r < 2^{k−1}.

D_{k}^{#}(J_{m}) = \frac{(J_{m} − J_{k−1})}{2^{k+1}}(3(J_{m} + J_{k−1}) − 2^{k})
= \frac{1}{2^{k+1}} (\frac{2^{m+1} + (−1)^{m}}{3} − \frac{2^{k} + (−1)^{k−1}}{3} ) (3 (\frac{2^{m+1} + (−1)^{m}}{3} + \frac{2^{k} + (−1)^{k−1}}{3} ) − 2^{k})
= \frac{1}{3 · 2^{k+1}} (2^{m+1} − 2^{k})(2^{m+1} + 2(−1)^{k−1}) since (−1)^{m} = (−1)^{k−1}
= \frac{1}{3}(2^{2m−k+1} − 2^{m} + 2^{m−k+1}(−1)^{k−1} + (−1)^{k})

after simplification. Again we find that N_{k}^{#}(J_{m}) = D_{k}^{#}(J_{m}).

This completes the proof that A(J_{m}) is odd for all Jacobsthal numbers J_{m}.

5 The Converse

We now prove the converse to Theorem 4.1. That is, we will prove that A(n) is even if n is not a Jacobsthal number. As a guide in how to proceed, we include a table of values for N_{k}^{#}(n) and D_{k}^{#}(n) for small values of n and k. This table suggests that N_{k}^{#}(n) ≥ D_{k}^{#}(n) for all positive integers n and k. It also suggests that for each value of n, there is at least one value of k for which N_{k}^{#}(n) is strictly greater than D_{k}^{#}(n) except when n is a Jacobsthal number. (The rows that begin with a Jacobsthal number are indicated in bold-face.)

\begin{matrix}n & N_{1}^{#}(n) & D_{1}^{#}(n) & N_{2}^{#}(n) & D_{2}^{#}(n) & N_{3}^{#}(n) & D_{3}^{#}(n) & N_{4}^{#}(n) & D_{4}^{#}(n) & N_{5}^{#}(n) & D_{5}^{#}(n) & N_{6}^{#}(n) & D_{6}^{#}(n) \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 5 & 5 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 10 & 10 & 4 & 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 16 & 16 & 7 & 7 & 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 6 & 24 & 24 & 11 & 10 & 4 & 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 7 & 33 & 33 & 15 & 15 & 6 & 6 & 2 & 0 & 0 & 0 & 0 & 0 \\ 8 & 44 & 44 & 20 & 20 & 8 & 8 & 3 & 0 & 0 & 0 & 0 & 0 \\ 9 & 56 & 56 & 26 & 26 & 11 & 11 & 4 & 2 & 0 & 0 & 0 & 0 \\ 10 & 70 & 70 & 33 & 32 & 14 & 14 & 5 & 4 & 0 & 0 & 0 & 0 \\ 11 & 85 & 85 & 40 & 40 & 17 & 17 & 6 & 6 & 0 & 0 & 0 & 0 \\ 12 & 102 & 102 & 48 & 48 & 21 & 20 & 8 & 8 & 1 & 0 & 0 & 0 \\ 13 & 120 & 120 & 57 & 57 & 25 & 25 & 10 & 10 & 2 & 0 & 0 & 0 \\ 14 & 140 & 140 & 67 & 66 & 30 & 30 & 12 & 12 & 3 & 0 & 0 & 0 \\ 15 & 161 & 161 & 77 & 77 & 35 & 35 & 14 & 14 & 4 & 0 & 0 & 0 \\ 16 & 184 & 184 & 88 & 88 & 40 & 40 & 16 & 16 & 5 & 0 & 0 & 0 \\ 17 & 208 & 208 & 100 & 100 & 46 & 46 & 19 & 19 & 6 & 2 & 0 & 0 \\ 18 & 234 & 234 & 113 & 112 & 52 & 52 & 22 & 22 & 7 & 4 & 0 & 0 \\ 19 & 261 & 261 & 126 & 126 & 58 & 58 & 25 & 25 & 8 & 6 & 0 & 0 \\ 20 & 290 & 290 & 140 & 140 & 65 & 64 & 28 & 28 & 9 & 8 & 0 & 0 \\ 21 & 320 & 320 & 155 & 155 & 72 & 72 & 31 & 31 & 10 & 10 & 0 & 0 \\ 22 & 352 & 352 & 171 & 170 & 80 & 80 & 35 & 34 & 12 & 12 & 1 & 0 \\ 23 & 385 & 385 & 187 & 187 & 88 & 88 & 39 & 37 & 14 & 14 & 2 & 0 \\ 24 & 420 & 420 & 204 & 204 & 96 & 96 & 43 & 40 & 16 & 16 & 3 & 0 \\ 25 & 456 & 456 & 222 & 222 & 105 & 105 & 47 & 45 & 18 & 18 & 4 & 0 \end{matrix}

Table 2: Values for N_{k}^{#}(n) and D_{k}^{#}(n)

(We note in passing that the values of N_{1}^{#}(n) form sequence \underline{A001859} in [8].)

In order to prove the first assertion (that N_{k}^{#}(n) ≥ D_{k}^{#}(n)), we separate the functions defined by the cases in equations (6) and (8) into individual functions denoted by N_{k}^{#(1)}(n), N_{k}^{#(2)}(n), …, D_{k}^{#(2)}(n). That is,

N_{k}^{#(1)}(n) := (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + 3qr
N_{k}^{#(2)}(n) := (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + 3qr + (r − J_{k−1})
N_{k}^{#(3)}(n) := (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + (3q + 2)r − 2^{k}
D_{k}^{#(1)}(n) := (\frac{n − r}{2^{k+1}} ) (3(n + r) − 2^{k})
D_{k}^{#(2)}(n) := (\frac{n − (2^{k} − r)}{2^{k+1}}) (3(n − r) + 2^{k+1})

For a given value of n, N_{k}^{#}(n) will equal N_{k}^{#(i)}(n) for some i ∈ {1, 2, 3} and D_{k}^{#}(n) will be D_{k}^{#(j)}(n) for some j ∈ {1, 2} depending on the value of r. Note that not all combinations of i and j are possible (for example, there is no value of n such that i = 1 and j = 2). In Lemmas 5.1 through 5.4 we show that N_{k}^{#(i)}(n) ≥ D_{k}^{#(j)}(n) for all possible combinations of i and j (that correspond to some integer n) which implies that N_{k}^{#}(n) ≥ D_{k}^{#}(n) for all positive integers n.

Lemma 5.1. For all integers n and k, N_{k}^{#(1)}(n) = D_{k}^{#(1)}(n).

Proof. We first note that, in the notation of Theorem 3.4, \frac{n − r}{2^{k+1}} = \frac{2^{k}q}{2^{k+1}} = \frac{q}{2}. Then

N_{k}^{#(1)}(n) = (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + 3qr

= (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k} + 3qr (\frac{2}{q})) since \frac{n − r}{2^{k+1}} = \frac{q}{2}
= (\frac{n − r}{2^{k+1}} ) (3n + 3r − 2^{k})
= D_{k}^{#(1)}(n).

Lemma 5.2. For all integers k and all integers n such that r > J_{k−1} (in the notation of Theorem 3.4),

N_{k}^{#(2)}(n) > D_{k}^{#(1)}(n).

Proof.

N_{k}^{#(2)}(n) = (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + 3qr + (r − J_{k−1})
> (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + 3qr since r > J_{k−1}
= N_{k}^{#(1)}(n)
= D_{k}^{#(1)}(n) by Lemma 5.1.

This proves our result. Lemma 5.3. For all integers k and all integers n such that r ≤ J_{k} (in the notation of Theorem 3.4),

N_{k}^{#(2)}(n) ≥ D_{k}^{#(2)}(n).

Proof. We see that r ≤ J_{k} = 2^{k} − J_{k−1} by Lemma 3.2. Thus, 2^{k}q + r ≤ 2^{k}(q + 1) − J_{k−1}. This implies n ≤ 2^{k}(q + 1) − J_{k−1}, so 2n − 2^{k}(q + 1) ≤ n − J_{k−1}. Hence,

N_{k}^{#(2)}(n) = (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + 3qr + (r − J_{k−1})
= \frac{q}{2}(3(2^{k}q) − 2^{k}) + 3q(n − 2^{k}q) + n − 2^{k}q − J_{k−1}
= q^{2}(−3(2^{k−1})) + q(−3(2^{k−1}) + 3n) + n − J_{k−1}
≥ q^{2}(−3(2^{k−1})) + q(−3(2^{k−1}) + 3n) + 2n − 2^{k}(q + 1) by the above argument
= \frac{2n − 2^{k} − 2^{k}q}{2^{k+1}} (3(2^{k}q) + 2^{k+1})
= D_{k}^{#(2)}(n).

Lemma 5.4. For all positive integers n and k, N_{k}^{#(3)}(n) = D_{k}^{#(2)}(n).

Proof.

N_{k}^{#(3)}(n) = (\frac{n − r}{2^{k+1}} ) (3(n − r) − 2^{k}) + (3q + 2)r − 2^{k}
= (\frac{q}{2}) (3(2^{k}q) − 2^{k}) + 3q(n − 2^{k}q) + 2(n − 2^{k}q) − 2^{k}
= \frac{n − 2^{k} + n − 2^{k}q}{2^{k} + 1} (3(2^{k}q) + 2^{k+1})
= D_{k}^{#(2)}(n).

Remark 5.5. To summarize, Lemmas 5.1 through 5.4 tell us that for any positive integer n,

N_{k}^{#}(n) ≥ D_{k}^{#}(n).

For Propositions 5.6 through 5.9 we make the assumption that J_{ℓ} < n < J_{ℓ+1} for some positive integer ℓ. Proposition 5.6. For ℓ and n, as given above, N_{ℓ+1}^{#}(n) = n − J_{ℓ}. Proof. By Lemma 3.1,

∑_{i=0}^{n−1} ⌊\frac{3i + 1}{2^{ℓ+1}}⌋ = 0 × (J_{ℓ}) + 1 × ((n − 1) − (J_{ℓ} − 1))
= n − J_{ℓ}.

Proposition 5.7. D_{k}^{#}(n) = 0 if n < 2^{k−1}. In particular, D_{ℓ+1}^{#}(n) = 0 if n < 2^{ℓ}. Proof. If n < 2^{k} then, in the notation of Theorem 3.5, n = r and q = 0, so by Theorem 3.5, D_{k}^{#}(n) = 0.

Proposition 5.8. D_{ℓ+1}^{#}(n) = 2(n − 2^{ℓ}) if 2^{ℓ} ≤ n < J_{ℓ+1}. Proof. If 2^{ℓ} ≤ n < J_{ℓ+1} then, in the notation of Theorem 3.5, q = 0 and r = n. Since n ≥ 2^{ℓ}, we are in the second case of Theorem 3.5 so

D_{ℓ+1}^{#}(n) = \frac{n − 2^{ℓ+1} + n}{2^{ℓ+2}}(0 + 2^{ℓ+2}) = 2(n − 2^{ℓ}).

Proposition 5.9. For n and ℓ as given above, 2(n − 2^{ℓ}) < n − J_{ℓ}. Proof. We begin by showing that J_{ℓ+1} − 2^{ℓ} = 2^{ℓ} − J_{ℓ}. We have

J_{ℓ+1} − 2^{ℓ} = \frac{2^{ℓ+2} + (−1)^{ℓ+1}}{3} − 2^{ℓ}
= 2^{ℓ} − \frac{2^{ℓ+1} + (−1)^{ℓ}}{3}
= 2^{ℓ} − J_{ℓ},

and hence

2(n − 2^{ℓ}) = n − 2^{ℓ} + n − 2^{ℓ}
< n − 2^{ℓ} + J_{ℓ+1} − 2^{ℓ}
= n − 2^{ℓ} + 2^{ℓ} − J_{ℓ} from the above argument
= n − J_{ℓ}

so we have our result.

We are now ready to prove our theorem.

Theorem 5.10. A(n) is even if n is not a Jacobsthal number.

Proof. Our goal is to show that there is some k such that N_{k}^{#}(n) is strictly greater than D_{k}^{#}(n) since, by Remark 5.5, we have shown that N_{k}^{#}(n) ≥ D_{k}^{#}(n) for all positive integers k and n.

Given n, not a Jacobsthal number, there exists a positive integer ℓ such that J_{ℓ} < n < J_{ℓ+1}. Then N_{ℓ+1}^{#}(n) = n−J_{ℓ} by Proposition 5.6, and since n > J_{ℓ}, N_{ℓ+1}^{#}(n) > 0. On the other hand, by Proposition 5.7, if n < 2^{ℓ}, then D_{ℓ+1}^{#}(n) = 0. If 2^{ℓ} ≤ n < J_{ℓ+1}, then by Proposition 5.8, D_{ℓ+1}^{#}(n) = 2(n − 2^{ℓ}) which is strictly less than n − J_{ℓ} = N_{ℓ+1}^{#}(n) by Proposition 5.9. Hence, in every case, N_{ℓ+1}^{#}(n) is strictly greater than D_{ℓ+1}^{#}(n) so there is at least one factor of two in A(n) and we have our result.

6 A Closing Remark

We close by noting that we can prove a stronger result than Theorem 5.10. If J_{ℓ} < n < J_{ℓ+1}, then

N_{ℓ+1}^{#}(n) − D_{ℓ+1}^{#}(n) = \{ \begin{matrix}n − J_{ℓ} & if & J_{ℓ} < n ≤ 2^{ℓ} \\ J_{ℓ+1} − n & if & 2^{ℓ} ≤ n < J_{ℓ+1} \end{matrix}

by Propositions 5.6, 5.7, 5.8 and Lemma 3.2.

Let ord_{2}(n) be the highest power of 2 that divides n. By Remark 5.5, N_{k}^{#}(n) − D_{k}^{#}(n) ≥ 0 for all n and for all k, so that

ord_{2}(A(n)) ≥ \{ \begin{matrix}n − J_{ℓ} & if & J_{ℓ} < n ≤ 2^{ℓ} \\ J_{ℓ+1} − n & if & 2^{ℓ} ≤ n < J_{ℓ+1} \end{matrix} ,

which strengthens Theorem 5.10.

Finally, we see that ord_{2}(A(2^{ℓ})) = J_{ℓ−1} since, for all k < ℓ + 1, N_{k}^{#}(2^{ℓ}) = N_{k}^{#(1)}(2^{ℓ}) = D_{k}^{#(1)}(2^{ℓ}) = D_{k}^{#}(2^{ℓ}), and 2^{ℓ} − J_{ℓ} = J_{ℓ+1} − 2^{ℓ} = J_{ℓ−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}.

7 Acknowledgements

The authors gratefully acknowledge the excellent technical help of Robert Schumacher in the preparation of this document.

References

[1] D. M. Bressoud, “Proofs and Confirmations: The story of the alternating sign matrix conjecture”, Cambridge University Press, 1999.

[2] D. M. Bressoud and J. Propp, How the Alternating Sign Matrix Conjecture Was Solved, Notices of the American Mathematical Society, 46 (6) (1999), 637-646.

[3] A. F. Horadam, Jacobsthal Representation Numbers, Fibonacci Quarterly, 34 (1) (1996), 40-53.

[4] A. F. Horadam, Jacobsthal Representation Polynomials, Fibonacci Quarterly, 35 (2) (1997), 137-148.

[5] A. F. Horadam, Rodriques’ Formulas for Jacobsthal-Type Polynomials, Fibonacci Quarterly, 35 (4) (1997), 361-370.

[6] A. F. Horadam and P. Filipponi, Derivative Sequences of Jacobsthal and Jacobsthal-Lucas Polynomials, Fibonacci Quarterly, 35 (4) (1997), 352-357.

[7] C. T. Long, “Elementary Introduction to Number Theory”, 3rd edition, Waveland Press, Inc., Prospect Heights, IL, 1995.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/∼njas/sequences/.

[9] A. Tucker, “Applied Combinatorics”, 3rd edition, John Wiley & Sons, 1995.

(Concerned with sequences A001045, A001859 and A005130.)

Received Jan. 13, 2000; published in Journal of Integer Sequences June 1, 2000.

Return to Journal of Integer Sequences home page.