Largest Values of the Stern Sequence, Alternating Binary Expansions and

Continuants

Roland Paulin Max-Planck-Institut für Mathematik Vivatsgasse 7 D-53111, Bonn Germany

                paulinroland@gmail.com

Abstract

We study the largest values of the rth row of Stern’s diatomic array. In particular, we prove some conjectures of Lansing. Our main tool is the connection between the Stern sequence, alternating binary expansions, and continuants. This allows us to reduce the problem of ordering the elements of the Stern sequence to the problem of ordering continuants. We describe an operation that increases the value of a continuant, allowing us to reduce the problem of largest continuants to ordering continuants of very special shape. Finally, we order these special continuants using some identities and inequalities involving Fibonacci numbers.

1 Introduction

The Stern sequence \underline{A002487} is defined as follows: s(0) = 0, s(1) = 1, s(2n) = s(n) and s(2n+1) = s(n)+s(n+1) for every n ≥ 0. Stern’s diatomic array consists of rows indexed by 0, 1, 2, …, where if r ≥ 0, then the rth row is s(2^{r}), s(2^{r} + 1), …, s(2^{r+1}). Stern’s diatomic array can also be constructed in the following way. Start with the 0th row 1, 1. If r ≥ 1, then to construct the rth row, copy the previous row, and between every two consecutive numbers x, y, write their sum x + y. This array was first studied by Stern [7]. Lehmer [4] summarized several properties of this array. Recently Defant [1] gave upper bounds for the elements of the Stern sequence.

For r ≥ 0 and m ≥ 1, let L_{m}(r) denote the mth largest distinct value of the rth row of Stern’s diatomic array. If there are fewer than m distinct values in the rth row, then we just take L_{m}(r) = −∞. Lucas [5] has observed that the largest value in the rth row is L_{1}(r) = F_{r+2}, where F_{n} denotes the nth Fibonacci number. Lansing [3] determined the second and third largest values L_{2}(r) and L_{3}(r), and formulated the following conjectures about the L_{m}(r)’s. Her Conjecture 7 [3] says that if m ≥ 1 and r ≥ 4m − 2, then

L_{m}(r) = L_{m}(r − 1) + L_{m}(r − 2).

Her Conjecture 9 [3] says that if m ≥ 2 and r ≥ 4m − 4, then

L_{m}(r) = L_{m−1}(r) − F_{r−(4m−5)} = F_{r+2} − ∑_{j=2}^{m} F_{r−(4j−5)}.

The following theorem is our main result. It gives a formula for L_{m}(r) for certain values of r and m, and it implies the two conjectures of Lansing stated above.

Theorem 1. If r ∈ ℤ_{≥0}, then

\{L_{1}(r), …, L_{⌈ \frac{r}{2} ⌉}(r)\} = \{F_{r+2} − F_{i}F_{j}; i, j ∈ ℤ_{≥0}, i + j = r − 1\}.

More explicitly, if 1 ≤ m ≤ ⌈\frac{r}{2}⌉, then

L_{m}(r) = F_{r+2} − F_{2m−2−b}F_{r−2m+1+b},

where

b = b(m, r) = \begin{cases}0, & if m ≤ ⌊\frac{r+3}{4}⌋ or 2 | r; \\ 1, & if m > ⌊\frac{r+3}{4}⌋ and 2 ∤ r. \end{cases}

We show now that Theorem 1 implies the two conjectures stated above.

Proof of Conjecture 7 [3]. Let m ≥ 1 and r ≥ 4m − 2. Then m ≤ ⌊\frac{(r−1)+3}{4}⌋, so L_{m}(r) = F_{r+2} − F_{2m−2}F_{r−2m+1} and L_{m}(r − 1) = F_{r+1} − F_{2m−2}F_{r−2m} by Theorem 1. If r ≥ 4m − 1, then m ≤ ⌊\frac{(r−2)+3}{4}⌋, while if r = 4m − 2, then 2 | r − 2, so either way L_{m}(r − 2) = F_{r} − F_{2m−2}F_{r−2m−1}. The conjecture now follows from

F_{r+2} − F_{2m−2}F_{r−2m+1} = (F_{r+1} − F_{2m−2}F_{r−2m}) + (F_{r} − F_{2m−2}F_{r−2m−1}).

Proof of Conjecture 9 [3]. It is enough to prove L_{m−1}(r) − L_{m}(r) = F_{r−(4m−5)}, because L_{1}(r) = F_{r+2}. Now m − 1 ≤ ⌊\frac{r+3}{4}⌋, and either 2 | r = 4m − 4, or m ≤ ⌊\frac{r+3}{4}⌋. So L_{m−1}(r) = F_{r+2} − F_{2m−4}F_{r−2m+3} and L_{m}(r) = F_{r+2} − F_{2m−2}F_{r−2m+1} by Theorem 1. Hence

L_{m−1}(r) − L_{m}(r) = F_{2m−2}F_{r−2m+1} − F_{2m−4}F_{r−2m+3} = (−1)^{2m−4}F_{2}F_{r−(4m−5)} = F_{r−(4m−5)}

by Lemma 3.

Here is a brief description of the contents of the paper. In Section 2 we state some basic results about Fibonacci numbers, alternating binary expansions and continuants. In Section 3 we describe the connection between the Stern sequence, alternating binary expansions and continuants. Using this description we reduce the problem of comparing the elements of the Stern sequence to the problem of comparing continuants, which is the subject of Section 4. (For earlier work on comparing continuants, see Ramharter’s paper [6].) Using some identities involving Fibonacci numbers, we finish the proof of Theorem 1 in Section 5. Finally, in Section 6 we discuss possible extensions of our results.

2 Preliminaries

In this section we introduce some notation, and state some basic results about Fibonacci numbers, alternating binary expansions and continuants. Let F_{n} denote the nth Fibonacci number for every n ∈ ℤ. So F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for every n ∈ ℤ. Note that ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{n} = ( \begin{matrix}F_{n+1} & F_{n} \\ F_{n} & F_{n−1} \end{matrix} ) for every n ∈ ℤ. The following basic lemma describes the sign of the Fibonacci numbers.

Lemma 2. If n ∈ ℤ, then F_{−n} = (−1)^{n+1}F_{n}. Hence

F_{n} \begin{cases}= 0, & if n = 0; \\ > 0, & if n > 0 or 2 ∤ n; \\ < 0, & if n < 0 and 2 | n. \end{cases}

Proof. The first part is easy to check by induction on n, and the second part follows from the first part.

The following lemma describes a useful identity, which allows us to compare F_{i}F_{j}’s with fixed i + j.

Lemma 3. If i, j, k, l ∈ ℤ and i + j = k + l, then

F_{i}F_{j} − F_{k}F_{l} = (−1)^{k}F_{i−k}F_{j−k}.

Hence if i + j = k + l, then F_{i}F_{j} = F_{k}F_{l} if and only if {i, j} = {k, l}.

Proof. If n, i, j ∈ ℤ, then

F_{n+i}F_{n+j} − F_{n}F_{n+i+j} = (−1)^{n}F_{i}F_{j}.

Dickson [2, p. 404] attributes this identity to A. Tagiuri. Substituting k, i − k and j − k into n, i and j, we obtain the stated identity. To prove the second part, note that by Lemma 2, if n ∈ ℤ, then F_{n} = 0 if and only if n = 0.

The following lemma describes the ordering of F_{i}F_{j}’s with i, j ≥ 0 and i + j fixed. We need this result to prove the second half of Theorem 1.

Lemma 4. Let n ∈ ℤ_{≥0}, then the set

{F_{i}F_{j}; i, j ∈ ℤ_{≥0}, i + j = n}

has cardinality ⌈\frac{n+1}{2}⌉, and if m ∈ \{1, …, ⌈\frac{n+1}{2}⌉\}, then the mth smallest element of this set is F_{2m−2−c}F_{n−(2m−2−c)}, where

c = \begin{cases}0, & if m ≤ ⌊\frac{n+4}{4}⌋ or 2 ∤ n; \\ 1, & if m > ⌊\frac{n+4}{4}⌋ and 2 | n. \end{cases}

Proof. The last part of Lemma 3 implies that the cardinality is ⌈\frac{n+1}{2}⌉. For m ∈ \{1, …, ⌈\frac{n+1}{2}⌉\} let c(m) be defined as c in the statement above, and let u(m) = 2m − 2 − c(m) and v(m) = n − (2m − 2 − c(m)). Then u(m), v(m) ≥ 0 and u(m) + v(m) = n, so F_{u(m)}F_{v(m)} is an element of the set. Let 1 ≤ m < m′ ≤ ⌈\frac{n+1}{2}⌉. All we need to prove is that F_{u(m)}F_{v(m)} < F_{u(m′)}F_{v(m′)}. The difference is

F_{u(m′)}F_{v(m′)} − F_{u(m)}F_{v(m)} = (−1)^{u(m)}F_{u(m′)−u(m)}F_{v(m′)−u(m)}

by Lemma 3. Here

u(m′) − u(m) = 2(m′ − m) − c(m′) + c(m) ≥ 2 − 1 > 0,

so F_{u(m′)−u(m)} > 0. Therefore we need to prove that (−1)^{c(m)}F_{v(m′)−u(m)} > 0. First suppose that 2 ∤ n. Then c(m) = c(m′) = 0, so v(m′) − u(m) = n − 2(m′ + m − 2) is odd, hence (−1)^{c(m)}F_{v(m′)−u(m)} > 0 by Lemma 2. So let 2 | n.

Suppose that m > ⌊\frac{n+4}{4}⌋. Then c(m) = c(m′) = 1, and m > ⌊\frac{n+4}{4}⌋ = ⌈\frac{n+2}{4}⌉, so m − 1 ≥ ⌈\frac{n+2}{4}⌉ ≥ \frac{n+2}{4} > \frac{n}{4}, hence

2 | v(m′) − u(m) = n − 2(m′ + m − 3) ≤ n − 2(2m + 1 − 3) = n − 4(m − 1) < 0.

Thus (−1)^{c(m)}F_{v(m′)−u(m)} > 0 by Lemma 2.

Finally, let m ≤ ⌊\frac{n+4}{4}⌋. Then c(m) = 0. If m′ > ⌊\frac{n+4}{4}⌋, then c(m′) = 1 and 2 ∤ v(m′) − u(m), so F_{v(m′)−u(m)} > 0. If m′ ≤ ⌊\frac{n+4}{4}⌋, then c(m′) = 0 and 4m′ − 4 ≤ n, so

v(m′) − u(m) = n − 2(m′ + m − 2) ≥ n − 2(2m′ − 3) > n − (4m′ − 4) ≥ 0,

hence F_{v(m′)−u(m)} > 0.

Now we turn to the discussion of alternating binary expansions. For d, l_{0} ∈ ℤ_{≥0}, l_{1}, …, l_{d} ∈ ℤ_{≥1} we define

A(l_{0}, …, l_{d}) = ∑_{i=0}^{d}(−1)^{d−i}2^{l_{0}+···+l_{i}}.

We call this an alternating binary expansion. The following lemma gives a bound for A(l_{0}, …, l_{d}).

Lemma 5. If d, l_{0} ∈ ℤ_{≥0} and l_{1}, …, l_{d} ∈ ℤ_{≥1}, then

2^{l_{0}+···+l_{d}−1} ≤ A(l_{0}, …, l_{d}) ≤ 2^{l_{0}+···+l_{d}}.

If d > 0, then A(l_{0}, …, l_{d}) < 2^{l_{0}+···+l_{d}}.

Proof. We prove by induction on d. For d = 0 this is trivial, so suppose that d ≥ 1 and that the statement is true for smaller values of d. Let k_{i} = l_{0} + ⋯ + l_{i} for every i ∈ {0, 1, …, d}. Then 0 ≤ k_{0} < k_{1} < ⋯ < k_{d}, and A(l_{0}, …, l_{d}) = 2^{k_{d}} − 2^{k_{d−1}} + 2^{k_{d−2}} − ⋯ + (−1)^{d}2^{k_{0}} = 2^{k_{d}} − A(l_{0}, …, l_{d−1}). Here 0 < 2^{k_{d−1}−1} ≤ A(l_{0}, …, l_{d−1}) ≤ 2^{k_{d−1}} ≤ 2^{k_{d}−1} by the induction hypothesis, so 2^{k_{d}−1} ≤ A(l_{0}, …, l_{d}) < 2^{k_{d}}.

The following lemma describes the number of alternating binary expansions of a positive integer.

Lemma 6. Every n ∈ ℤ_{≥1} has exactly two alternating binary expansions, and exactly one of these has the form n = A(l_{0}, 1, l_{2}, …, l_{d}), where l_{0} ∈ ℤ_{≥0} and d, l_{2}, …, l_{d} ∈ ℤ_{≥1}. If n is a power of 2, then d = 1 and the other expansion is n = A(l_{0}), while otherwise d ≥ 2 and the other expansion is A(l_{0}, l_{2} + 1, l_{3}, …, l_{d}).

Proof. It is easy to check that A(l_{0}, 1) = A(l_{0}) = 2^{l_{0}} and A(l_{0}, 1, l_{2}, …, l_{d}) = A(l_{0}, l_{2} + 1, l_{3}, …, l_{d}) for d ≥ 2. Hence it is enough to prove that every n ∈ ℤ_{≥1} has exactly one alternating binary expansion of the form n = A(l_{0}, …, l_{d}) such that d ≥ 1 and l_{1} = 1. We prove by induction on n. Let k be the unique positive integer such that 2^{k−1} ≤ n < 2^{k}. Let k_{i} = l_{0} + ⋯ + l_{i} for i ∈ {0, …, d}. Then 2^{k_{d}} ≤ n < 2^{k_{d}} by Lemma 5, so k_{d} = k. Moreover n = 2^{k} − A(l_{0}, …, l_{d−1}), so n′ = A(l_{0}, …, l_{d−1}) = 2^{k} − n. If d = 1, then l_{0} = k − 1 and n = A(l_{0}, 1) = 2^{k−1}. Now let d ≥ 2. Then A(l_{0}, …, l_{d−1}) < 2^{k_{d−1}} ≤ 2^{k−1} by Lemma 5, so 2^{k−1} < n < 2^{k} and n′ < 2^{k−1} < n. By the induction hypothesis, there is a unique expansion n′ = A(l_{0}, …, l_{d−1}) with l_{1} = 1, where furthermore l_{0} + ⋯ + l_{d−1} ≤ k − 1, because n′ < 2^{k−1}. Then l_{d} = k − (l_{0} + ⋯ + l_{d−1}) ∈ ℤ_{≥1} is also determined.

Now we will recall some basic facts about continuants. Continuants are polynomials in several variables, which come up often when working with continued fractions. We define the dth continuant K_{d}(X_{1}, …, X_{d}) ∈ ℤ[X_{1}, …, X_{d}] for every d ∈ ℤ_{≥0}, by the following recursion: K_{0} = 1, K_{1}(X_{1}) = X_{1}, and

K_{d}(X_{1}, …, X_{d}) = X_{d}K_{d−1}(X_{1}, …, X_{d−1}) + K_{d−2}(X_{1}, …, X_{d−2})

for every d ≥ 2. We can safely write K(X_{1}, …, X_{d}) instead of K_{d}(X_{1}, …, X_{d}), because d is anyway determined by the number of variables. If \underline{X} = (X_{1}, …, X_{d}), then we will also use the notation K(\underline{X}) = K(X_{1}, …, X_{d}). The continuants are related to continued fractions by the following identity:

[a_{0}, a_{1}, …, a_{d}] = a_{0} + \frac{1}{a_{1} + _{\frac{1}{...+ \frac{1}{a_{d}}}}} = \frac{K(a_{0}, …, a_{d})}{K(a_{1}, …, a_{d})}

for every d ≥ 0.

The following lemma gives maybe the most practical description of continuants, using 2 × 2 matrices. Lemma 7. If d ≥ 2, then

(\begin{matrix}K_{d}(X_{1}, …, X_{d}) & K_{d−1}(X_{1}, …, X_{d−1}) \\ K_{d−1}(X_{2}, …, X_{d}) & K_{d−2}(X_{2}, …, X_{d−1}) \end{matrix}) = (\begin{matrix}X_{1} & 1 \\ 1 & 0 \end{matrix}) ⋯ (\begin{matrix}X_{d} & 1 \\ 1 & 0 \end{matrix}) .

So if d ≥ 0, then K_{d}(X_{1}, …, X_{d}) = M_{1,1}, where M = ( \begin{matrix}X_{1} & 1 \\ 1 & 0 \end{matrix} ) ⋯ ( \begin{matrix}X_{d} & 1 \\ 1 & 0 \end{matrix} ).

Proof. This easily follows from the defining recursion by induction on d.

The continuants have the following symmetry property. Lemma 8. K(X_{1}, …, X_{d}) = K(X_{d}, …, X_{1}) for every d ≥ 0.

Proof. Let M = ( \begin{matrix}X_{1} & 1 \\ 1 & 0 \end{matrix} ) ⋯ ( \begin{matrix}X_{d} & 1 \\ 1 & 0 \end{matrix} ), then

M^{T} = ( \begin{matrix}X_{d} & 1 \\ 1 & 0 \end{matrix} )^{T} ⋯ ( \begin{matrix}X_{1} & 1 \\ 1 & 0 \end{matrix} )^{T} = ( \begin{matrix}X_{d} & 1 \\ 1 & 0 \end{matrix} ) ⋯ ( \begin{matrix}X_{1} & 1 \\ 1 & 0 \end{matrix} ) ,

hence

K(X_{d}, …, X_{1}) = (M^{T})_{1,1} = M_{1,1} = K(X_{1}, …, X_{d})

by Lemma 7.

The following lemma states a few simple identities involving continuants. Lemma 9. If d ≥ 1, then

K(X_{1}, …, X_{d}) = K(X_{1} − 1, X_{2}, …, X_{d}) + K(X_{2}, …, X_{d}).

If d ≥ 2, then

K(1, X_{2}, …, X_{d}) = K(X_{2}, …, X_{d}) + K(X_{3}, …, X_{d}).

If d ≥ 1, then

K(1, X_{1}, X_{2}, …, X_{d}) = K(X_{1} + 1, X_{2}, …, X_{d})

and

K(X_{1}, …, X_{d−1}, X_{d}, 1) = K(X_{1}, …, X_{d−1}, X_{d} + 1).

Proof. The identities are trivial for d = 1, so assume that d ≥ 2. Using Lemma 8 and the defining recursion of the continuants, we obtain

K(X_{1}, …, X_{d}) = X_{1}K(X_{2}, …, X_{d}) + K(X_{3}, …, X_{d}).

Substituting X_{1} − 1 into X_{1}, we get

K(X_{1} − 1, X_{2}, …, X_{d}) = (X_{1} − 1)K(X_{2}, …, X_{d}) + K(X_{3}, …, X_{d}).

These two equations immediately imply the first part of the lemma. Substituting 1 into X_{1} in the first equation, we obtain the second part of the lemma.

The fourth identity follows from the third one by Lemma 8. Finally,

K(X_{1} + 1, X_{2}, …, X_{d}) = K(X_{1}, …, X_{d}) + K(X_{2}, …, X_{d}) = K(1, X_{1}, …, X_{d})

by the first two parts of the lemma.

3 Connecting the Stern sequence, alternating binary expansions and continuants

The following proposition describes the connection between the Stern sequence, alternating binary expansions and continuants. This result plays a central role in this paper: it allows us to reduce the problem of ordering the elements of the Stern sequence to the problem of ordering continuants.

Proposition 10. If d, l_{0} ∈ ℤ_{≥0} and l_{1}, …, l_{d} ∈ ℤ_{≥1}, then

s(A(l_{0}, l_{1}, …, l_{d})) = K(l_{1}, …, l_{d}).

Proof. We prove by induction on l_{0} + ⋯ + l_{d}. So let S ∈ ℤ_{≥0}, and suppose the statement is true if l_{0} + ⋯ + l_{d} < S. Now let l_{0} + ⋯ + l_{d} = S. If l_{0} > 0, then A(l_{0}, l_{1}, …, l_{d}) = 2^{l_{0}}A(0, l_{1}, …, l_{d}), so s(A(l_{0}, l_{1}, …, l_{d})) = s(A(0, l_{1}, …, l_{d})) = K(l_{1}, …, l_{d}) by the induction hypothesis. So assume that l_{0} = 0.

Let k_{i} = l_{0}+⋯+l_{i} for every i ∈ {0, …, d}, and let n = A(l_{0}, l_{1}, …, l_{d}) = ∑_{i=0}^{d}(−1)^{d−i}2^{k_{i}}. Note that k_{0} = l_{0} = 0, so k_{1} = l_{1}. Here n > 0 by Lemma 5, and n is odd, so n = 2m + 1 for some m ∈ ℤ_{≥0}. If d = 0, then n = 1, and s(1) = 1 = K(). So let d ≥ 1.

First suppose that l_{1} ≥ 2. If d is even, then m = A(l_{1} −1, l_{2}, …, l_{d}) and m+1 = A(0, l_{1} − 1, l_{2}, …, l_{d}), while if d is odd, then m+1 = A(l_{1} −1, l_{2}, …, l_{d}) and m = A(0, l_{1} −1, l_{2}, …, l_{d}). (Note that l_{1} − 1 ≥ 1.) So either way we get

s(n) = s(m) + s(m + 1) = s(A(0, l_{1} − 1, l_{2}, …, l_{d})) + s(A(l_{1} − 1, l_{2}, …, l_{d}))
= K(l_{1} − 1, l_{2}, …, l_{d}) + K(l_{2}, …, l_{d}) = K(l_{1}, …, l_{d})

using the induction hypothesis and Lemma 9.

Now suppose that l_{1} = 1. If d = 1, then n = A(0, 1) = 1 and s(n) = 1 = K(1). So let d ≥ 2. If d is odd, then m = A(l_{2}, …, l_{d}) and m + 1 = A(0, l_{2}, …, l_{d}), while if d is even, then m + 1 = A(l_{2}, …, l_{d}) and m = A(0, l_{2}, …, l_{d}). So either way we get

s(n) = s(m) + s(m + 1) = s(A(0, l_{2}, …, l_{d})) + s(A(l_{2}, …, l_{d}))
= K(l_{2}, …, l_{d}) + K(l_{3}, …, l_{d}) = K(1, l_{2}, …, l_{d}) = K(l_{1}, …, l_{d})

using the induction hypothesis and Lemma 9.

For r ∈ ℤ let us define

E_{r} = {(l_{1}, …, l_{d}); d ∈ ℤ_{≥1}, l_{1}, …, l_{d} ∈ ℤ_{≥1}, l_{1} = l_{d} = 1, l_{1} + ⋯ + l_{d} = r + 1}

and

E′_{r} = {(l_{1}, …, l_{d}); d ∈ ℤ_{≥1}, l_{1}, …, l_{d} ∈ ℤ_{≥1}, l_{1} = l_{d} = 1, l_{1} + ⋯ + l_{d} ≤ r + 1}.

Using Lemmas 5, 6 and Proposition 10, we obtain the following corollary.

Corollary 11. If r ∈ ℤ_{≥0}, then the set of values of the rth row of Stern’s diatomic array is

\{s(n); 2^{r} ≤ n ≤ 2^{r+1}\} = \{K(\underline{l}); \underline{l} ∈ E′_{r}\}.

Proof. Suppose that \underline{l} ∈ E′_{r}. Let l_{0} = r + 1 − ∑_{i=1}^{r} l_{i} and n = A(l_{0}, …, l_{d}). Then 2^{r} ≤ n ≤ 2^{r+1} and s(n) = K(\underline{l}) by Lemma 5 and Proposition 10. So the left hand side contains the right hand side. Conversely, let n ∈ {2^{r}, …, 2^{r+1}}. If n = 2^{r} or n = 2^{r+1}, then s(n) = 1 = K(1). So suppose that 2^{r} < n < 2^{r+1}. According to Lemma 6, n has an alternating binary expansion n = A(l_{0}, …, l_{d}) with d ≥ 1 and l_{1} = 1. Here l_{1} + ⋯ + l_{d} ≤ l_{0} + ⋯ + l_{d} = r + 1 by Lemma 5, and s(n) = K(l_{1}, …, l_{d}) by Proposition 10. So if l_{d} = 1, then \underline{l} = (l_{1}, …, l_{d}) ∈ E′_{r} and s(n) = K(\underline{l}). If l_{d} > 1, then \underline{l}′ = (l_{1}, …, l_{d} − 1, 1) ∈ E′_{r} and s(n) = K(\underline{l}) = K(\underline{l′}) by Lemma 9. So the right hand side contains the left hand side.

This corollary implies that L_{m}(r) is the mth largest distinct value in \{K(\underline{l}); \underline{l} ∈ E′_{r}\}. So we need to compare the continuants K(\underline{l}), where \underline{l} ∈ E′_{r}.

4 Comparing continuants

The following proposition describes a simple operation on (l_{1}, …, l_{d}) that increases K(l_{1}, …, l_{d}). This operation is our main tool in comparing continuants.

Proposition 12. Let d, l_{1}, …, l_{d} ∈ ℤ_{≥1}, j ∈ {1, …, d}, and suppose that l_{j} = u + v for some u, v ∈ ℤ_{≥1}. Then

K(l_{1}, …, l_{d}) ≤ K(l_{1}, …, l_{j−1}, u, v, l_{j+1}, …, l_{d}),

where equality holds if and only if j = 1 and u = 1, or j = d and v = 1.

Proof. Lemma 7 implies that

K(l_{1}, …, l_{d}) = (P ( \begin{matrix}u+v & 1 \\ 1 & 0 \end{matrix} ) Q)_{1,1}

and

K(l_{1}, …, l_{j−1}, u, v, l_{j+1}, …, l_{d}) = (P ( \begin{matrix}u & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}v & 1 \\ 1 & 0 \end{matrix} ) Q)_{1,1},

where P = ( \begin{matrix}l_{1} & 1 \\ 1 & 0 \end{matrix} ) ⋯ ( \begin{matrix}l_{j−1} & 1 \\ 1 & 0 \end{matrix} ) and Q = ( \begin{matrix}l_{j+1} & 1 \\ 1 & 0 \end{matrix} ) ⋯ ( \begin{matrix}l_{d} & 1 \\ 1 & 0 \end{matrix} ). Using

( \begin{matrix}u & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}v & 1 \\ 1 & 0 \end{matrix} ) − ( \begin{matrix}u+v & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}(u−1)(v−1) & u−1 \\ v−1 & 1 \end{matrix} ) = ( \begin{matrix}u−1 \\ 1 \end{matrix} ) (v − 1, 1)

we obtain

Δ = K(l_{1}, …, l_{j−1}, u, v, l_{j+1}, …, l_{d}) − K(l_{1}, …, l_{d}) = (P ( \begin{matrix}u−1 \\ 1 \end{matrix} ) (v − 1, 1)Q)_{1,1}
= (P_{1,1}(u − 1) + P_{1,2})(Q_{1,1}(v − 1) + Q_{2,1}).

Here P_{1,1}, P_{1,2}, Q_{1,1}, Q_{2,1}, u − 1, v − 1 ≥ 0, so Δ ≥ 0. Note that det P, det Q ∈ {−1, 1}, since det ( \begin{matrix}X & 1 \\ 1 & 0 \end{matrix} ) = −1. So (P_{1,1}, P_{1,2}) ≠ (0, 0) and (Q_{1,1}, Q_{2,1}) ≠ (0, 0). Hence Δ = 0 if and only if u = 1 and P_{1,2} = 0, or v = 1 and Q_{2,1} = 0. It is easy to see that P_{1,2} = 0 if and only if j = 1, and similarly, Q_{2,1} = 0 if and only if j = d.

We introduce some notation. Let

h(l_{1}, …, l_{d}) = ∑_{i=1}^{d}(l_{i} − 1) = l_{1} + ⋯ + l_{d} − d.

For r ∈ ℤ and a ∈ ℤ_{≥0} let

E_{r,a} = {(l_{1}, …, l_{d}) ∈ E_{r}; h(l_{1}, …, l_{d}) = a}

and

E′_{r,a} = {(l_{1}, …, l_{d}) ∈ E′_{r}; h(l_{1}, …, l_{d}) = a}.

Then E′_{r} = ⋃_{a≥0} E′_{r,a} = ⋃_{t≤r} ⋃_{a≥0} E_{t,a}.

For s, p_{0}, p_{1}, …, p_{s} ∈ ℤ_{≥0} let

w_{p_{0},...,p_{s}}(X_{1}, …, X_{s}) = (\underbrace{1, …, 1}_{p_{0}}, X_{1}, \underbrace{1, …, 1}_{p_{1}}, X_{2}, …, \underbrace{1, …, 1}_{p_{s−1}}, X_{s}, \underbrace{1, …, 1}_{p_{s}})

and

κ_{p_{0},...,p_{s}}(X_{1}, …, X_{s}) = K(w_{p_{0},...,p_{s}}(X_{1}, …, X_{s})).

For s = 0 we simply write

w_{p_{0}} = (\underbrace{1, …, 1}_{p_{0}})

and κ_{p_{0}} = K(w_{p_{0}}).

The idea is that starting from (l_{1}, …, l_{d}) ∈ E′_{r}, and using the operation of Proposition 12 several times, and also possibly increasing elements or adding new elements to (l_{1}, …, l_{d}), we can increase K(l_{1}, …, l_{n}) to K(w_{r+1}). If we stop a bit earlier, we get the largest continuants. The precise statement is described in the following proposition. Proposition 13. If r ∈ ℤ_{≥0} and \underline{l} ∈ E′_{r} \ (E_{r,0} ∪ E_{r,1}), then there is an \underline{m} ∈ E_{r−1,0} ∪ E_{r,2} such that K(\underline{l}) ≤ K(\underline{m}). Proof. We will use several times that if u_{1}, …, u_{d} ∈ ℤ_{≥1}, then

K(u_{1}, …, u_{d}) ≤ K(u_{1}, …, u_{d}, 1),

and if u′_{1}, …, u′_{d} ∈ ℤ_{≥1} and u_{i} ≤ u′_{i} for every i, then

K(u_{1}, …, u_{d}) ≤ K(u′_{1}, …, u′_{d}).

We prove by induction on h(\underline{l}). If h(\underline{l}) = 0, then \underline{l} = w_{d} for some d ≤ r, so we can take \underline{m} = w_{r} ∈ E_{r−1,0}. If h(\underline{l}) = 1, then \underline{l} = w_{p_{0},p_{1}}(2) for some p_{0}, p_{1} ∈ ℤ_{≥1} with p_{0} +p_{1} ≤ r −2, so we can take \underline{m} = w_{p_{0},r−2−p_{0}}(3) ∈ E_{r,2}. Finally, let h(\underline{l}) ≥ 2, and suppose that the statement is true for smaller values of h. Then there is a j ∈ {2, …, d − 1} such that l_{j} ≥ 2. Let

\underline{l′} = (l_{1}, …, l_{j−1}, l_{j} − 1, 1, l_{j+1}, …, l_{d}),

then \underline{l′} ∈ E′_{r}, and K(\underline{l}) ≤ K(\underline{l′}) by Proposition 12. Moreover h(\underline{l′}) = h(\underline{l}) − 1 ≥ 1, so \underline{l′} ∉ E_{r,0}. If \underline{l′} ∉ E_{r,1}, then by the induction hypothesis there is an \underline{m} ∈ E_{r−1,0} ∪ E_{r,2} such that K(\underline{l}) ≤ K(\underline{l′}) ≤ K(\underline{m}). So suppose that \underline{l′} ∈ E_{r,1}. Then \underline{l} ∈ E_{r,2}, so we can take \underline{m} = \underline{l}.

5 Fibonacci identities

Based on Proposition 13, our next goal is to calculate K(\underline{l}) for \underline{l} ∈ E_{r,0} ∪ E_{r,1} ∪ E_{r−1,0} ∪ E_{r,2}. If r ≥ 1, then E_{r,0} = {w_{r+1}}, E_{r−1,0} = {w_{r}},

E_{r,1} = {w_{p_{0},p_{1}}(2); p_{0}, p_{1} ∈ ℤ_{≥1}, p_{0} + p_{1} = r − 1},

and E_{r,2} = U_{r} ∪ V_{r}, where

U_{r} = {w_{p_{0},p_{1}}(3); p_{0}, p_{1} ∈ ℤ_{≥1}, p_{0} + p_{1} = r − 2}

and

V_{r} = {w_{p_{0},p_{1},p_{2}}(2); p_{0}, p_{2} ∈ ℤ_{≥1}, p_{1} ∈ ℤ_{≥0}, p_{0} + p_{1} + p_{2} = r − 3}.

In general κ_{p_{0},...,p_{s}}(X_{1}, …, X_{s}) = M_{1,1}, where

M = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{p_{0}} ( \begin{matrix}X_{1} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{p_{1}} ( \begin{matrix}X_{2} & 1 \\ 1 & 0 \end{matrix} ) ⋯ ( \begin{matrix}X_{s} & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{p_{s}} .

Note that ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{p} = ( \begin{matrix}F_{p+1} & F_{p} \\ F_{p} & F_{p−1} \end{matrix} ) for every p ∈ ℤ. Calculating the matrix products, we get

κ_{p_{0}} = F_{p_{0}+1},
κ_{p_{0},p_{1}}(2) = 2F_{p_{0}+1}F_{p_{1}+1} + F_{p_{0}+1}F_{p_{1}} + F_{p_{0}}F_{p_{1}+1},
κ_{p_{0},p_{1}}(3) = 3F_{p_{0}+1}F_{p_{1}+1} + F_{p_{0}+1}F_{p_{1}} + F_{p_{0}}F_{p_{1}+1},
κ_{p_{0},p_{1},p_{2}}(2, 2) =F_{p_{0}+1}F_{p_{1}}F_{p_{2}} + F_{p_{0}}F_{p_{1}+1}F_{p_{2}} + 2F_{p_{0}+1}F_{p_{1}+1}F_{p_{2}} + F_{p_{0}+1}F_{p_{1}−1}F_{p_{2}+1}

+ F_{p_{0}}F_{p_{1}}F_{p_{2}+1} + 4F_{p_{0}+1}F_{p_{1}}F_{p_{2}+1} + 2F_{p_{0}}F_{p_{1}+1}F_{p_{2}+1} + 4F_{p_{0}+1}F_{p_{1}+1}F_{p_{2}+1}.

In the following lemma we express these values in more useful forms.

Lemma 14. If p_{0}, p_{1}, p_{2} ∈ ℤ_{≥0}, then

κ_{p_{0},p_{1}}(2) = F_{p_{0}+p_{1}+3} − F_{p_{0}}F_{p_{1}} = F_{p_{0}+p_{1}+2} + F_{p_{0}+p_{1}} + F_{p_{0}−1}F_{p_{1}−1},
κ_{p_{0},p_{1}}(3) = F_{p_{0}+p_{1}+3} + F_{p_{0}+p_{1}+1} − 2F_{p_{0}+p_{1}−2} − 2F_{p_{0}−2}F_{p_{1}−2},
κ_{p_{0},p_{1},p_{2}}(2, 2) =(F_{p_{0}+p_{1}+p_{2}+4} + F_{p_{0}+p_{1}+p_{2}+2} − F_{p_{0}+p_{1}+p_{2}−4})

− (F_{p_{1}}(F_{p_{0}−1}F_{p_{2}−1} + 3F_{p_{0}−2}F_{p_{2}−1} + 3F_{p_{0}−1}F_{p_{2}−2}) + 2F_{p_{0}−2}F_{p_{1}+1}F_{p_{2}−2}).

Proof. If i, j ∈ ℤ, then

( \begin{matrix}F_{i+j+1} & F_{i+j} \\ F_{i+j} & F_{i+j−1} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{i+j} = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{i} ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{j} = ( \begin{matrix}F_{i+1} & F_{i} \\ F_{i} & F_{i−1} \end{matrix} ) ( \begin{matrix}F_{j+1} & F_{j} \\ F_{j} & F_{j−1} \end{matrix} ) ,

hence F_{i+j} = F_{i+1}F_{j} +F_{i}F_{j−1}. Applying this identity twice, we get that F_{i+j+k} = F_{i+j+1}F_{k} + F_{i+j}F_{k−1} = (F_{i+1}F_{j+1} + F_{i}F_{j})F_{k} + (F_{i+1}F_{j} + F_{i}F_{j−1})F_{k−1} for i, j, k ∈ ℤ. Using these identities, one can express every term in the statement of the Lemma as a polynomial of F_{p_{0}}, F_{p_{0}+1}, F_{p_{1}}, F_{p_{1}+1}, F_{p_{2}}, F_{p_{2}+1}. Comparing the obtained polynomials, one can check the stated identities. The calculations could be done by hand, but they are tedious. Instead we have used Mathematica [8] to carry out these symbolic calculations, this is done in the attached file.

Corollary 15. If r ≥ 6, then

max\{K(\underline{l}); \underline{l} ∈ E_{r,1}\} < F_{r+2} = κ_{r+1},
min\{K(\underline{l}); \underline{l} ∈ E_{r,1}\} = κ_{1,r−2}(2) = F_{r+1} + F_{r−1},
max\{K(\underline{l}); \underline{l} ∈ U_{r}\} = κ_{2,r−4}(3) = F_{r+1} + F_{r−1} − 2F_{r−4},
max\{K(\underline{l}); \underline{l} ∈ V_{r}\} = κ_{2,0,r−5}(2, 2) = F_{r+1} + F_{r−1} − F_{r−7}.

So if r ≥ 6, then

max\{K(\underline{l}); \underline{l} ∈ E_{r−1,0} ∪ E_{r,2}\} ≤ min\{K(\underline{l}); \underline{l} ∈ E_{r,1}\},

with strict inequality for r ≠ 7.

Proof. Let r ≥ 6. Recalling the description of E_{r,1}, U_{r} and V_{r}, we see that

\{K(\underline{l}); \underline{l} ∈ E_{r,1}\} = \{κ_{p_{0},p_{1}}(2); p_{0}, p_{1} ∈ ℤ_{≥1}, p_{0} + p_{1} = r − 1\},
\{K(\underline{l}); \underline{l} ∈ U_{r}\} = \{κ_{p_{0},p_{1}}(3); p_{0}, p_{1} ∈ ℤ_{≥1}, p_{0} + p_{1} = r − 2\},
\{K(\underline{l}); \underline{l} ∈ V_{r}\} = \{κ_{p_{0},p_{1},p_{2}}(2); p_{0}, p_{2} ∈ ℤ_{≥1}, p_{1} ∈ ℤ_{≥0}, p_{0} + p_{1} + p_{2} = r − 3\}.

Using Lemma 14 one can easily reduce the first part of the proposition to the following statements. If p_{0}, p_{1} ∈ ℤ_{≥1} and p_{0} + p_{1} = r − 1, then F_{p_{0}}F_{p_{1}} > 0 and F_{p_{0}−1}F_{p_{1}−1} ≥ 0. If p_{0}, p_{1} ∈ ℤ_{≥1} and p_{0} + p_{1} = r − 2, then 2F_{p_{0}−2}F_{p_{1}−2} ≥ 0. If p_{0}, p_{2} ∈ ℤ_{≥1}, p_{1} ∈ ℤ_{≥0} and p_{0}+p_{1}+p_{2} = r−3, then F_{p_{1}}(F_{p_{0}−1}F_{p_{2}−1}+3F_{p_{0}−2}F_{p_{2}−1}+3F_{p_{0}−1}F_{p_{2}−2})+2F_{p_{0}−2}F_{p_{1}+1}F_{p_{2}−2} ≥ 0. These statements follow from the facts that F_{n} > 0 for n ≥ 1, and F_{n} ≥ 0 for n ≥ −1.

Now we prove the last part. If \underline{l} ∈ E_{r−1,0}, then K(\underline{l}) = κ_{r} = F_{r+1} < F_{r+1} + F_{r−1}. Since E_{r,2} = U_{r} ∪ V_{r}, the statement follows from F_{r+1} + F_{r−1} − 2F_{r−4} < F_{r+1} + F_{r−1} and F_{r+1} + F_{r−1} − F_{r−7} ≤ F_{r+1} + F_{r−1}. Note that here F_{r−7} > 0 if r ≥ 6 and r ≠ 7.

Now we are ready to prove our main result.

Proof of Theorem 1. The second part of the theorem follows from the first part by Lemma 4. We prove now the first part. For r ∈ {0, 1, 2, 3, 4, 5} one could check the statement by hand. The attached Mathematica file contains a program that does this.

Suppose that r ≥ 6, and let m ≥ 1. By Corollary 11, L_{m}(r) is the mth largest distinct value in \{K(\underline{l}); \underline{l} ∈ E′_{r}\}. If \underline{l} ∈ E′_{r} \ (E_{r,0} ∪ E_{r,1}), then

K(\underline{l}) ≤ min(K(\underline{l′}); \underline{l′} ∈ E_{r,1})

by Proposition 13 and Corollary 15. Moreover

\{K(\underline{l}); \underline{l} ∈ E_{r,0}\} = \{F_{r+2}\}

and

\{K(\underline{l}); \underline{l} ∈ E_{r,1}\} = \{F_{r+2} − F_{i}F_{j}; i, j ∈ ℤ_{≥1}, i + j = r − 1\}

by Lemma 14. So {L_{1}(r), …, L_{|H|}(r)} = H, where

H = {F_{r+2} − F_{i}F_{j}; i, j ∈ ℤ_{≥0}, i + j = r − 1}.

Here |H| = ⌈\frac{r}{2}⌉ by Lemma 4.

6 Further research

Using our results, it would not be hard to describe the exact positions where the first ⌈\frac{r}{2}⌉ largest values in the rth row of Stern’s diatomic sequence appear.

To determine L_{m}(r) for 1 ≤ m ≤ ⌈\frac{r}{2}⌉, we needed to calculate and (sometimes) compare the values of K(\underline{l}) for \underline{l} ∈ E_{r,0} ∪ E_{r,1} ∪ E_{r,2}. To go a step further, i.e., to determine L_{m}(r) for some m > ⌈\frac{r}{2}⌉, we would probably need to calculate and compare the values of K(\underline{l}) for \underline{l} ∈ ⋃_{i=0}^{3} E_{r,i}. For example, we have ordered \{K(\underline{l}); \underline{l} ∈ E_{r,0} ∪ E_{r,1}\}, but we have not yet ordered \{K(\underline{l}); \underline{l} ∈ E_{r,2}\}.

Instead of studying Stern’s diatomic array, which starts with the 0th row 1, 1, we could study the following generalization. Start with the 0th row a, b, where a, b ∈ ℝ, and in each step construct a new row by copying the last row, and writing between each two consecutive elements their sum. One could try to understand the largest values in the rth row of this array.

7 Acknowledgments

The work presented here was carried out at the University of Salzburg, where I was supported by the Austrian Science Fund (FWF): P24574.

References

[1] C. Defant, Upper bounds for Stern’s diatomic sequence and related sequences, preprint,

   http://arxiv.org/abs/1506.07824, 2015.

[2] L. E. Dickson, History of the Theory of Numbers, Vol. I: Divisibility and Primality. Chelsea Publishing Co., 1966.

[3] J. Lansing, Largest values for the Stern sequence, J. Integer Seq., 17 (2014), Article 14.7.5.

[4] D. H. Lehmer, On Stern’s diatomic series, Amer. Math. Monthly, 36 (1929), 59–67.

[5] E. Lucas, Sur les suites de Farey, Bull. Soc. Math. France, 6 (1878), 118–119.

[6] G. Ramharter, Extremal values of continuants, Proc. Amer. Math. Soc., 89 (1983), 189– 201.

[7] M. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55 (1858), 193–220.

[8] Wolfram Research, Inc., Mathematica, Version 10.0, 2014.

2010 Mathematics Subject Classification: Primary 11A55; Secondary 11B39. Keywords: Stern sequence, alternating binary expansion, continuant.

(Concerned with sequence \underline{A002487}.)

Received September 13 2016; revised version received November 15 2016. Published in Journal of Integer Sequences, December 27 2016.

Return to Journal of Integer Sequences home page.