Largest Values for the Stern Sequence

Jennifer Lansing Department of Mathematics University of Illinois at Urbana Champaign 1409 W. Green St Urbana, IL 61801 USA

                 jlweber@illinois.edu

Abstract

In 1858, Stern introduced an array, later called the diatomic array. The array is formed by taking two values a and b for the first row, and each succeeding row is formed from the previous by inserting c + d between two consecutive terms with values c, d. This array has many interesting properties, such as the largest value in a row of the diatomic array is the (r + 2)-th Fibonacci number, occurring roughly one-third and two-thirds of the way through the row. In this paper, we show each of the second and third largest values in a row of the diatomic array satisfy a Fibonacci recurrence and can be written as a linear combination of Fibonacci numbers. The array can be written in terms of a recursive sequence, denoted s(n) and called the Stern sequence. The diatomic array also has the property that every third term is even. In function notation, we have s(3n) is always even. We introduce and give some properties of the related sequence defined by w(n) = s(3n)/2.

1 Historical background

The Stern sequence, denoted by s(n), satisfies the recurrences

s(2n) = s(n) and s(2n + 1) = s(n + 1) + s(n)

for n ≥ 1, with s(0) = 0 and s(1) = 1. The first few values of this sequence are

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, … This sequence has many properties, including s(n) is even if and only if 3 divides n, and

∑_{n=2^{r}}^{2^{r+1}−1} s(n) = 3^{r}.

In 1858, Stern [9] constructed an array by taking two values a and b, which give the first row, and then he formed the next row by rewriting the previous row and inserting the sum a + b between its summands. Stern studied the properties of this general array, but he also examined the case where a = b = 1. The numerous properties of this (1, 1) array, later called the diatomic array by Lehmer, are summarized by Lehmer [4]. The diatomic array is given in Table 1.

1  1
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1
1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1
1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 7 12 5 13 8 11 3 10 7 11 4 9 5 6 1

Table 1: Diatomic Array for s(n)

One of the most obvious properties of the diatomic array is the symmetry. In terms of the sequence notation, the symmetry is noted as

s(n) = s(n^{∗}) where n^{∗} := 3 · 2^{r} − n for 2^{r} ≤ n ≤ 2^{r+1}.  (1)

Stern also considered the array starting with (0, 1), given in Table 2, and this array looks more like the sequence s(n). In fact, the r-th row of the (0, 1) array is given by s(n) for 0 ≤ n ≤ 2^{r}, and the r-th row of the diatomic array is given by s(n) for 2^{r} ≤ n ≤ 2^{r+1}. For

0  1
0 1 1
0 1 1 2 1
0 1 1 2 1 3 2 3 1
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 3 3 7 4 5 1

Table 2: (0, 1) Array

more information, Reznick [7] gives many recurrence and regularity properties of the Stern sequence, and Northshield [6] also gives a nice history of the sequence. See also sequence \underline{A002487} in Sloane’s Online Encyclopedia of Integer Sequences [8].

2 Largest values

In 1878, Lucas [5] studied Stern’s diatomic array, and noted that the largest value in the r-th row is a Fibonacci number, occurring roughly at one-third and two-thirds of the way in the row. We now ask, what are the second and third largest values in a row of the diatomic array?

Definition 1. Let L_{m}(r) denote the m-th largest distinct value in the r-th row of the Stern sequence. The maximum of the r-th row is denoted by L_{1}(r), the second largest value is denoted by L_{2}(r), and so forth.

We restate Lucas’s theorem, which was also later proved by Lehmer [4].

Theorem 2. For all r ≥ 0, we have L_{1}(r) = F_{r+2}. Moreover, this maximum occurs for the values n_{r} = (4 · 2^{r} − (−1)^{r})/3, as well as n_{r}^{∗} = (5 · 2^{r} + (−1)^{r})/3 by symmetry.

This theorem is proved by an easy induction, which we omit. The relationship between the position of the maximum of the r-th row and that of the (r−1)-th row is quite important. We have

n_{r} = 2n_{r−1} − (−1)^{r},  (2)

which means the maximum for the r-th row will alternate between appearing on the left or right side of the previous maximum in the diatomic array. Similarly, n_{r}^{∗} = 2n_{r−1}^{∗} + (−1)^{r}, by the mirror symmetry of the second half of the row.

3 Second Largest Value for s(n)

Using Mathematica, we can easily compute the second largest value in a particular row of the diatomic array. The second largest values are given in Table 3, and they follow a Fibonacci recurrence relation, L_{2}(r) = L_{2}(r − 1) + L_{2}(r − 2), for r ≥ 6. However, starting in the 4th row, there are 4 occurrences of the second largest value. Two of them come from adding the second largest values from the two preceding rows, L_{2}(r − 1) + L_{2}(r − 2), while the other two come from a linear combination of previous maximum values, 2L_{1}(r − 2) + L_{1}(r − 4). The second way of obtaining the second largest value, from 2L_{1}(r − 2) + L_{1}(r − 4), will occur either 2 to the left or right of where L_{1}(r) occurs in the row. The Stern sequence achieves these second largest values for explicitly describable n.

Definition 3. For r ≥ 4, let

n_{2,1}(r) := \frac{17 · 2^{r−2} − (−1)^{r−1}}{3} and n_{2,2}(r) := \frac{16 · 2^{r−2} − 7(−1)^{r}}{3} .

By the symmetry defined earlier in (1), we have

n_{2,1}^{∗}(r) = \frac{19 · 2^{r−2} + (−1)^{r−1}}{3} and n_{2,2}^{∗}(r) = \frac{20 · 2^{r−2} + 7(−1)^{r}}{3} .

Table 3: Second Largest Values of s(n) in rows

\begin{matrix}row r & n & L_{2}(r) \\ 1 & 2, 4 & 1 \\ 2 & 6 & 2 \\ 3 & 9, 15 & 4 \\ 4 & 19, 23, 25, 29 & 7 \\ 5 & 45, 51 & 12 \\ 6 & 83, 91, 101, 109 & 19 \\ 7 & 173, 181, 203, 211 & 31 \\ 8 & 339, 363, 405, 429 & 50 \\ 9 & 685, 725, 811, 851 & 81 \\ 10 & 1363, 1451, 1621, 1709 & 131 \\ 11 & 2733, 2901, 3243, 3411 & 212 \\ 12 & 5459, 5803, 6485, 6829 & 343 \end{matrix}

Note that n_{2,1}(r) and n_{2,2}(r) coalesce at r = 5 so that there are only two occurrences of L_{2}(5).

We observe s(n_{2,1}(r)) and s(n_{2,1}^{∗}(r)) give the second largest value in the r-th row as a sum of preceding second largest values, and s(n_{2,2}(r)) and s(n_{2,2}^{∗}(r)) give the second largest value of the r-th row as a linear combination of previous maximum values. Also note n_{2,1}(r) has a similar recurrence relation as n_{r} in (2):

n_{2,1}(r) = \frac{17 · 2^{r−2} + 2(−1)^{r−1} − 3(−1)^{r−1}}{3} = 2n_{2,1}(r − 1) + (−1)^{r}.  (3)

We will also need

n_{2,2}(r) = 4n_{r−2} − (−1)^{r} = n_{r} − 2(−1)^{r},  (4)

and the last equality makes it explicit that the second way of obtaining the second largest value, from 2L_{1}(r − 2) + L_{1}(r − 4), will occur either two to the left or right of where L_{1}(r) occurs in the row.

Theorem 4. (i) L_{2}(r) = F_{r+2} − F_{r−3} = L_{1}(r) − F_{r−3}, for r ≥ 4.

(ii) s(n_{2,1}(r)) = s(n_{2,1}^{∗}(r)) = s(n_{2,2}(r)) = s(n_{2,2}^{∗}(r)) = L_{2}(r), for r ≥ 4.

(iii) For n_{2,1}(r) and n_{2,1}^{∗}(r), L_{2}(r) arises from the sum L_{2}(r − 1) + L_{2}(r − 2), for r ≥ 6.

(iv) For n_{2,2}(r) and n_{2,2}^{∗}(r), L_{2}(r) arises from the sum 2L_{1}(r − 2) + L_{1}(r − 4), for r ≥ 8.

Proof. The induction base is clear and easily verified. Assume (i)-(iv) hold for all rows before and including the r-th row, with r ≥ 8.

We first show that besides the maximum value, there is no element larger than L_{2}(r) + L_{2}(r − 1) in the (r + 1)-th row. If 2k ∈ [2^{r+1}, 2^{r+2}], then using the induction hypothesis from part (i), we find that for all the even values in the (r + 1)-th row

s(2k) = s(k) ≤ L_{1}(r) = F_{r+2} < F_{r+2} + 2F_{r−1} = F_{r+3} − F_{r−2} = L_{2}(r) + L_{2}(r − 1).

We now want to obtain a bound on the odd values in the (r+1)-th row, and more specifically s(4k ± 1). Now let k ∈ [2^{r−1}, 2^{r}] such that 4k ± 1 ∈ (2^{r+1}, 2^{r+2}). We examine some special cases first. If k = n_{r−1}, or k = n_{r−1}^{∗}, we have

s(2n_{r−1} − (−1)^{r}) = s(n_{r}) = L_{1}(r) = s(n_{r}^{∗}) = s(2n_{r−1}^{∗} + (−1)^{r}),

which implies s(2n_{r−1}+(−1)^{r}) < L_{1}(r) and s(2n_{r−1}^{∗}−(−1)^{r}) < L_{1}(r). Similarly, if k = 2n_{r−2} or k = 2n_{r−2}^{∗}, we have

s(2 · 2n_{r−2} + (−1)^{r}) = s(n_{r}) = L_{1}(r) = s(n_{r}^{∗}) = s(2 · 2n_{r−2}^{∗} − (−1)^{r}),

which means s(2 · 2n_{r−2} − (−1)^{r}) < L_{1}(r) and s(2 · 2n_{r−2}^{∗} + (−1)^{r}) < L_{1}(r). Except for these special cases where k = n_{r−1}, n_{r−1}^{∗}, 2n_{r−2}, or 2n_{r−2}^{∗}, we have s(2k ±1) < L_{1}(r), and therefore s(2k ± 1) ≤ L_{2}(r). Then we have

s(4k ± 1) = s(2k) + s(2k ± 1) = s(2k ± 1) + s(k) ≤ L_{2}(r) + L_{2}(r − 1).

We now examine the special cases more closely. If k = n_{r−1}, we have

s(4n_{r−1} − (−1)^{r}) = s(2n_{r−1}) + s(2n_{r−1} − (−1)^{r}) = s(n_{r−1}) + s(n_{r}) = L_{1}(r + 1),

but we can disregard this (largest) value, since we are looking for the second largest value. Now, we also have

s(4n_{r−1} + (−1)^{r}) = s(2n_{r−1}) + s(2n_{r−1} + (−1)^{r})
= s(n_{r−1}) + s(n_{r−1}) + s(n_{r−1} + (−1)^{r})
= 2s(n_{r−1}) + s(2n_{r−2} + 2(−1)^{r})
= 2s(n_{r−1}) + s(n_{r−2} + (−1)^{r})
= 2s(n_{r−1}) + s(2n_{r−3} − (−1)^{r} + (−1)^{r})
= 2s(n_{r−1}) + s(n_{r−3})
= 2L_{1}(r − 1) + L_{1}(r − 3).  (5)

Note that by symmetry we have s(4n_{r−1}^{∗} − (−1)^{r}) = 2L_{1}(r − 1) + L_{1}(r − 3) and s(4n_{r−1}^{∗} + (−1)^{r}) = L_{1}(r). Lastly, if k = 2n_{r−2} we have

s(4 · 2n_{r−2} ± 1) = 2s(n_{r−2}) + s(2n_{r−2} ± 1)

= \begin{cases}2s(n_{r−2}) + s(2n_{r−2} + (−1)^{r}) \\ 2s(n_{r−2}) + s(2n_{r−2} − (−1)^{r}) \end{cases}

= \begin{cases}2s(n_{r−2} + s(n_{r−1}) = 2L_{1}(r − 2) + L_{1}(r − 1) \\ 3s(n_{r−2}) + s(n_{r−4}) = 3L_{1}(r − 2) + L_{1}(r − 4) \end{cases}

< 2L_{1}(r − 1) + L_{1}(r − 3).

So now we only need compare 2L_{1}(r − 1) + L_{1}(r − 3) to L_{2}(r) + L_{2}(r − 1). However, using part (i) from the induction hypothesis, we have

L_{2}(r) + L_{2}(r − 1) = F_{r+2} − F_{r−3} + F_{r+1} − F_{r−4}
= F_{r+3} − F_{r−2} = L_{1}(r + 1) − L_{1}(r − 4)
= 2L_{1}(r − 1) + L_{1}(r − 3).

Thus, all elements in the (r + 1)-th row, besides the maximum, are less than or equal to L_{2}(r) + L_{2}(r − 1), and so we have

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

All that is left is to verify the second largest values occur for the n given earlier. Evaluating s(n_{2,1}(r + 1)) and using (3), we have

s(n_{2,1}(r + 1)) = s(2n_{2,1}(r) + (−1)^{r+1}) = s(n_{2,1}(r)) + s(n_{2,1}(r) − (−1)^{r})
= s(n_{2,1}(r)) + s(2n_{2,1}(r − 1))
= s(n_{2,1}(r)) + s(n_{2,1}(r − 1))
= L_{2}(r) + L_{2}(r − 1).

We also note that by (4) we have n_{2,2}(r + 1) = 4n_{r−1} + (−1)^{r}, and in (5) we see that s(4n_{r−1} + (−1)^{r}) also gives L_{2}(r). Therefore, the second largest values occur where we expect. Finally, by the symmetry of the Stern sequence in rows, we have

s(n_{2,1}^{∗}(r + 1)) = s(n_{2,1}(r + 1)) = L_{2}(r + 1) = s(n_{2,2}(r + 1)) = s(n_{2,2}^{∗}(r + 1)).

4 Third Largest Value for s(n)

The third largest values in a row for s(n), given in Table 4, also eventually satisfy a Fibonacci recurrence. This recurrence starts in the 10th row, and rows 8 and 9 give the two initial values. Similar to the second largest value in a row, there are 4 occurrences of the third Table 4: Third Largest Values of s(n) in rows

\begin{matrix}row r & n & L_{3}(r) \\ 1 & N/A & N/A \\ 2 & 4 & 1 \\ 3 & 10, 14 & 3 \\ 4 & 17, 22, 26, 31 & 5 \\ 5 & 37, 41, 55, 59 & 11 \\ 6 & 75, 87, 105, 117 & 18 \\ 7 & 165, 219 & 30 \\ 8 & 331, 347, 421, 437 & 49 \\ 9 & 693, 843 & 80 \\ 10 & 1355, 1387, 1685, 1717 & 129 \\ 11 & 2741, 2773, 3371, 3403 & 209 \\ 12 & 5451, 5547, 6741, 6837 & 338 \end{matrix}

largest value. By symmetry, two of them come from L_{3}(r − 1) + L_{3}(r − 2), and the other two come from the sum of (2L_{1}(r − 4) + L_{1}(r − 6)) + (3L_{1}(r − 4) + 2L_{1}(r − 6)), which adds to 5L_{1}(r − 4) + 3L_{1}(r − 6).

The values of n where the third largest values occur also follow a pattern, starting in the eighth row. For the outside left and right values, it appears that the next value is two times the previous value plus or minus 31. The inside right and left values follow the pattern, two times the previous value plus or minus one. Taking this recurrences and iterating them, we obtain the following apparent closed form for these values.

Definition 5. For r ≥ 8, let

n_{3,1}(r) := \frac{64 · 2^{r−4} − 31(−1)^{r}}{3} and n_{3,2}(r) := \frac{65 · 2^{r−4} + (−1)^{r}}{3} .

By symmetry, we have

n_{3,1}^{∗}(r) = \frac{80 · 2^{r−4} + 31(−1)^{r}}{3} and n_{3,2}^{∗}(r) = \frac{79 · 2^{r−4} − (−1)^{r}}{3} .

We will show that n_{3,1}(r), n_{3,1}^{∗}(r), n_{3,2}(r), and n_{3,2}^{∗}(r) give the third largest values for s(n) in the r-th row. It is useful to note

n_{3,1}(r) = \frac{4 · 2^{r} − (−1)^{r} − 30(−1)^{r}}{3} = n_{r} − 10(−1)^{r}.  (6)

This tells us that the first (and by symmetry, the last) occurrence of the third largest value in the row will be either 10 to the left or 10 to the right of the largest values, depending on the parity of the row. We also remark that n_{3,2}(r) satisfies the recurrence relations

n_{3,2}(r) = 2n_{3,2}(r − 1) + (−1)^{r} and n_{3,2}(r) − (−1)^{r} = 2n_{3,2}(r − 1).  (7)

Theorem 6. (i) L_{3}(r) = L_{2}(r) − F_{r−7} = F_{r+1} + 5F_{r−4} = L_{1}(r) − 3F_{r−5}, for r ≥ 8.

(ii) s(n_{3,1}(r)) = s(n_{3,1}^{∗}(r)) = s(n_{3,2}(r)) = s(n_{3,2}^{∗}(r)) = L_{3}(r), for r ≥ 8.

(iii) For n_{3,1}(r) and n_{3,1}^{∗}(r), L_{3}(r) arises from the sum 5L_{1}(r − 4) + 3L_{1}(r − 6), for r ≥ 8.

(iv) For n_{3,2}(r) and n_{3,2}^{∗}(r), L_{3}(r) arises from the sum L_{3}(r − 1) + L_{3}(r − 2), for r ≥ 10.

Proof. We proceed by induction. Again, the base case is easily verified. Assume the induction hypotheses hold for all values below r > 10. We will first verify that L_{3}(r) + L_{3}(r − 1) and 5L_{1}(r − 3) + 3L_{1}(r − 5) are achieved at the expected values. We will then show that all values in the (r + 1)-th row, except for L_{1}(r + 1) and L_{2}(r + 1), are less than or equal to L_{3}(r) + L_{3}(r − 1) = F_{r+2} + 5F_{r−3}.

We first verify that s(n_{3,2}(r + 1)) = L_{3}(r) + L_{3}(r − 1). Using (7), we have

s(n_{3,2}(r + 1)) = s(2n_{3,2}(r) − (−1)^{r}) = s(n_{3,2}(r)) + s(n_{3,2}(r) − (−1)^{r})
= L_{3}(r) + s(2n_{3,2}(r − 1))
= L_{3}(r) + L_{3}(r − 1).

Now considering s(n_{3,1}(r + 1)), and using (6) and (2) we have

s(n_{3,1}(r + 1)) = s(n_{r+1} + 10(−1)^{r}) = s(2n_{r} + (−1)^{r} + 10(−1)^{r})

= s(n_{r} + 5(−1)^{r}) + s(n_{r} + 5(−1)^{r} + (−1)^{r}) = s(2n_{r−1} − (−1)^{r} + 5(−1)^{r}) + s(2n_{r−1} + 6(−1)^{r} − (−1)^{r}) = s(n_{r−1} + 2(−1)^{r}) + s(n_{r−1} + 3(−1)^{r}) + s(n_{r−1} + 3(−1)^{r} − (−1)^{r}) = 2s(n_{r−1} + 2(−1)^{r}) + s(n_{r−1} + 3(−1)^{r}) = 2s(2n_{r−2} + (−1)^{r} + 2(−1)^{r}) + s(2n_{r−2} + (−1)^{r} + 3(−1)^{r}) = 2s(n_{r−2} + (−1)^{r}) + 2s(n_{r−2} + 2(−1)^{r}) + s(n_{r−2} + 2(−1)^{r}) = 2s(n_{r−3}) + 3s(2n_{r−3} + (−1)^{r}) = 2s(n_{r−3}) + 3s(n_{r−3}) + 3s(n_{r−3} + (−1)^{r}) = 5s(n_{r−3}) + 3s(2n_{r−4} + 2(−1)^{r}) = 5s(n_{r−3}) + 3s(n_{r−4} + (−1)^{r}) = 5s(n_{r−3}) + 3s(2n_{r−5}) = 5L_{1}(r − 3) + 3L_{1}(r − 5).

We also note by hypothesis (i), we have

L_{3}(r) + L_{3}(r − 1) = F_{r+3} − 3F_{r−4} = 5F_{r−1} + 3F_{r−3} = 5L_{1}(r − 3) + 3L_{1}(r − 5). (8)

We now show that all values in the (r + 1)-th row, except for L_{1}(r + 1) and L_{2}(r + 1), are less than or equal to L_{3}(r) + L_{3}(r − 1) = F_{r+2} + 5F_{r−3}. First note that for 2k ∈ [2^{r+1}, 2^{r+2}], we have

s(2k) = s(k) ≤ L_{1}(r) = F_{r+2} < F_{r+2} + 5F_{r−3} = L_{3}(r) + L_{3}(r − 1).

For the odd values in the (r + 1)-th row, we eliminate the cases that anything larger than L_{3}(r) + L_{3}(r − 1) can come from the first, second or third largest values and a neighbor. Now consider s(2k + 1) = s(k) + s(k + 1), and let b represent the larger of s(k) and s(k + 1), which comes from the r-th row, and c denote the smaller value coming from the (r − 1)-th row.

If b is L_{1}(r), then c is either L_{1}(r − 1) or L_{1}(r − 2). However, L_{1}(r) + L_{1}(r − 1) gives the largest value in the (r + 1)-th row, so we can ignore this value. Observe that

L_{1}(r) + L_{1}(r − 2) = F_{r+2} + F_{r} < F_{r+2} + 5F_{r−3}

is too small. So then it must be the case that b ≤ L_{2}(r). Now, there are 2 distinct ways of obtaining L_{2}(r). If b = L_{2}(r), then c could be L_{2}(r − 1) or L_{2}(r − 2). But L_{2}(r) + L_{2}(r − 1) gives L_{2}(r + 1) and we can ignore this value. We also have

L_{2}(r) + L_{2}(r − 2) = F_{r+2} − F_{r−3} + F_{r} − F_{r−4} = F_{r+2} + F_{r−2} + 2F_{r−4}
< F_{r+2} + 5F_{r−3} = L_{3}(r) + L_{3}(r − 1),

so this value is too small. But if b = 2L_{1}(r − 2) + L_{1}(r − 4), then c is L_{1}(r − 2) or L_{1}(r − 2) + L_{1}(r − 4), and we only need to consider the latter. We have

2L_{1}(r − 2) + L_{1}(r − 4) + L_{1}(r − 2) + L_{1}(r − 4) = 3F_{r} + 2F_{r−2}
< F_{r+2} + 5F_{r−3} = L_{3}(r) + L_{3}(r − 1),

which implies b ≤ L_{3}(r). If b = L_{3}(r), there are 2 distinct ways of obtaining L_{3}(r). If b = L_{3}(r), then c could be L_{3}(r−1) or L_{3}(r−2), but we can disregard these because we want to find something larger. If b = 5L_{1}(r−4)+3L_{1}(r−6), then c could be 2L_{1}(r−4)+L_{1}(r−6) or 3L_{1}(r − 4) + 2L_{1}(r − 6). We need only consider the latter, and we have

5L_{1}(r − 4) + 3L_{1}(r − 6) + 3L_{1}(r − 4) + 2L_{1}(r − 6) = 8F_{r−2} + 5F_{r−4}

< F_{r+2} + 5F_{r−3} = L_{3}(r) + L_{3}(r − 1),

which implies b < L_{3}(r). However c might be a large value in the (r − 1)-the row to make up for b being so small. Now, we know c < b < L_{3}(r), that c comes from the (r − 1)-th row, and that c > L_{3}(r − 1). If c = L_{1}(r − 1), then b could only be L_{1}(r − 2) + L_{1}(r − 3) (since we already eliminated b = L_{1}(r)). But then b + c = 2L_{1}(r − 1) + L_{1}(r − 3) = L_{2}(r + 1), and we can also ignore this value. Then c must be L_{2}(r − 1), and the only possibility for b is L_{2}(r − 1) + L_{2}(r − 3) (as we already eliminated b = L_{2}(r)). By Theorem 4 (i) and the induction hypothesis (i), we have

L_{2}(r + 1) − F_{r−6} = L_{2}(r) + L_{2}(r − 1) − F_{r−6}
= L_{3}(r) + F_{r−7} + L_{3}(r − 1) + F_{r−8} − F_{r−6}
= L_{3}(r) + L_{3}(r − 1).  (9)

Using (9), we have

b + c = 2L_{2}(r − 1) + L_{2}(r − 3)
= 2L_{1}(r − 1) − 2F_{r−4} + L_{1}(r − 3) − F_{r−6}
= L_{2}(r + 1) − 2F_{r−4} − F_{r−6}
< L_{2}(r + 2) − F_{r−6} = L_{3}(r) + L_{3}(r − 1).

Finally, we have that c could be L_{2}(r − 1) = 2L_{1}(r − 3) + L_{1}(r − 5) and b could be 3L_{1}(r − 3) + 2L_{1}(r − 5) or 3L_{1}(r − 3) + L_{1}(r − 5). Then by (8) we see

L_{3}(r) + L_{3}(r − 1) = 5L_{1}(r − 3) + 3L_{1}(r − 5) > 5L_{1}(r − 3) + 2L_{1}(r − 5),

so that 5L_{1}(r−3)+2L_{1}(r−5) is too small, while 5L_{1}(r−3)+3L_{1}(r−5) gives L_{3}(r)+L_{3}(r−1). This eliminates all possibilities and shows nothing can be between L_{3}(r) + L_{3}(r − 1) and L_{2}(r+1), so that s(2k+1) ≤ L_{3}(r)+L_{3}(r−1). Thus, we have L_{3}(r+1) = L_{3}(r)+L_{3}(r−1).

Since the next row in the diatomic array is formed by inserting the sum of two consecutive terms in between them, it makes sense that the k-th largest value in the r-th row will satisfy a Fibonacci recurrence. This appears to hold true for the 4th, 5th, and 6th (distinct) largest value in a row, for a sufficiently large row value. We see in Table 5 a Fibonacci recurrence starts at the 14th row for L_{4}, the 18th for L_{5}, and the 22nd row for L_{6}. This leads us to the following conjecture.

Conjecture 7. For all r ≥ 4m − 2, the m-th largest distinct value satisfies the recurrence L_{m}(r) = L_{m}(r − 1) + L_{m}(r − 2).

Remark 8. By Theorems 4 (i) and 6 (i), we have L_{2}(r) = F_{r+2} − F_{r−3} and L_{3}(r) = L_{2}(r) − F_{r−7}. Note that L_{3}(r) = F_{r+2} − F_{r−3} − F_{r−7}. Inspecting Table 5, we notice the following:

L_{4}(r) =L_{3}(r) − F_{r−11} = F_{r+2} − F_{r−3} − F_{r−7} − F_{r−11} for r ≥ 12,
L_{5}(r) =L_{4}(r) − F_{r−15} = F_{r+2} − F_{r−3} − F_{r−7} − F_{r−11} − F_{r−15} for r ≥ 16, and
L_{6}(r) =L_{5}(r) − F_{r−19} = F_{r+2} − F_{r−3} − F_{r−7} − F_{r−11} − F_{r−15} − F_{r−19} for r ≥ 20.

This leads us to another conjecture.

Conjecture 9. For r ≥ 4(m − 1), we have

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

Table 5: L_{m} of s(n) in rows

\begin{matrix}row r & L_{1}(r) & L_{2}(r) & L_{3}(r) & L_{4}(r) & L_{5}(r) & L_{6}(r) \\ 3 & 5 & 4 & 3 & 2 & 1 & N/A \\ 4 & 8 & 7 & 5 & 4 & 3 & 2 \\ 5 & 13 & 12 & 11 & 10 & 9 & 8 \\ 6 & 21 & 19 & 18 & 17 & 16 & 15 \\ 7 & 34 & 31 & 30 & 29 & 27 & 26 \\ 8 & 55 & 50 & 49 & 47 & 46 & 45 \\ 9 & 89 & 81 & 80 & 79 & 76 & 75 \\ 10 & 144 & 131 & 129 & 128 & 123 & 121 \\ 11 & 233 & 212 & 209 & 208 & 207 & 199 \\ 12 & 377 & 343 & 338 & 337 & 335 & 322 \\ 13 & 610 & 555 & 547 & 546 & 545 & 542 \\ 14 & 987 & 898 & 885 & 883 & 882 & 877 \\ 15 & 1597 & 1453 & 1432 & 1429 & 1428 & 1427 \\ 16 & 2584 & 2351 & 2317 & 2312 & 2311 & 2309 \\ 17 & 4181 & 3804 & 3749 & 3741 & 3740 & 3739 \\ 18 & 6765 & 6155 & 6066 & 6053 & 6051 & 6050 \\ 19 & 10946 & 9959 & 9815 & 9794 & 9791 & 9790 \\ 20 & 17711 & 16114 & 15881 & 15847 & 15842 & 15841 \\ 21 & 28657 & 26073 & 25696 & 25641 & 25633 & 25632 \\ 22 & 46368 & 42187 & 41577 & 41488 & 41475 & 41473 \\ 23 & 75025 & 68260 & 67273 & 67129 & 67108 & 67105 \end{matrix}

5 The Distribution of Gaps

In a previous paper, the author [2] considered the classical question of the distribution of values for the Stern sequence. A more modern question to consider is, what is the distribution of gaps? There are numerous ways we could consider the gaps of the Stern sequence. First, we can simply compute s(n + 1) − s(n). Figure 2 plots the normalized difference for the 14th row. Figure 2 looks like the plot of s(n), given in Figure 1, with also a reflection over the x-axis. If n = 2ℓ, we have

s(n + 1) − s(n) = s(2ℓ + 1) − s(2ℓ) = s(ℓ + 1).

If n = 2ℓ + 1, then we have

s(n + 1) − s(n) = s(2ℓ + 2) − s(2ℓ + 1) = −s(ℓ).

From this perspective, the distribution of gaps is the same problem as the distribution of values.

Figure 1: Values of s(n) in the 14th row  Figure 2: s(n + 1) − s(n) for the 14th row

Another way to approach this problem is to order a row from largest to smallest and then take the difference of consecutive terms. Since values occur at least twice in a row, we would have a lot of zeros. If we eliminate repeated values when taking the difference, then we have a type of step function. Figures 3 and 4 give the differences of terms for the 10th

Figure 3: Length of gaps for the 10th row  Figure 4: Length of gaps for the 14th row

row and the 14th row, after they have been sorted and repeated elements deleted.

In the previous three sections, we discussed the largest three values in a row of the diatomic array, and we can use this information here. First, we normalize the data by dividing by the largest possible value F_{r+2}. By Theorems 4 and 6, we have the biggest gap is F_{r−3}/F_{r+2}, and the next gap is F_{r−7}/F_{r+2}. If the conjecture L_{k}(r) − L_{k−1}(r) = F_{r−(4k−5)} is true, then the distribution of gaps is F_{r−(4k−5)}/F_{r+2} for 2 ≤ k ≤ (r + 5)/4, with the smallest value being 1/F_{r+2}. The largest gaps are fixed, regardless of the row. The smallest gaps then approach 0, for the later rows.

This would mean the distribution of the gaps is not uniformly distributed. If Conjecture 9 is true, then we have the following conjecture.

Conjecture 10. The normalized distribution of gaps for the Stern sequence is

ϕ^{−(4k−3)} for 2 ≤ k ≤ (r + 5)/4.

6 A related sequence

We introduce a new and related sequence. As noted earlier, s(3n) is always even, so we study the related sequence defined by

w(n) := \frac{1}{2}s(3n).

How does this sequence behave? It has some similarities to the Stern sequence, such as symmetry of terms in a row in the diatomic array, the same average order of magnitude, and that the sum over powers of 2 is a power of 3. However, w(n) has a much more complicated structure; it has no simple generating function and the recursive definition is not as short.

Table 6 gives a comparison of the first 64 values of s(n) and w(n). Analogous to the

Table 6: Values for s(n) and w(n)

\begin{matrix}n & s(n) & w(n) & n & s(n) & w(n) & n & s(n) & w(n) & n & s(n) & w(n) \\ 1 & 1 & 1 & 17 & 5 & 6 & 33 & 6 & 8 & 49 & 9 & 13 \\ 2 & 1 & 1 & 18 & 4 & 4 & 34 & 5 & 6 & 50 & 7 & 9 \\ 3 & 2 & 2 & 19 & 7 & 5 & 35 & 9 & 9 & 51 & 12 & 12 \\ 4 & 1 & 1 & 20 & 3 & 2 & 36 & 4 & 4 & 52 & 5 & 5 \\ 5 & 3 & 2 & 21 & 8 & 3 & 37 & 11 & 7 & 53 & 13 & 8 \\ 6 & 2 & 2 & 22 & 5 & 3 & 38 & 7 & 5 & 54 & 8 & 7 \\ 7 & 3 & 4 & 23 & 7 & 7 & 39 & 10 & 9 & 55 & 11 & 15 \\ 8 & 1 & 1 & 24 & 2 & 2 & 40 & 3 & 2 & 56 & 3 & 4 \\ 9 & 4 & 4 & 25 & 7 & 9 & 41 & 11 & 7 & 57 & 10 & 17 \\ 10 & 3 & 2 & 26 & 5 & 5 & 42 & 8 & 3 & 58 & 7 & 9 \\ 11 & 5 & 3 & 27 & 8 & 7 & 43 & 13 & 4 & 59 & 11 & 11 \\ 12 & 2 & 2 & 28 & 3 & 4 & 44 & 5 & 3 & 60 & 4 & 6 \\ 13 & 5 & 5 & 29 & 7 & 9 & 45 & 12 & 8 & 61 & 9 & 13 \\ 14 & 3 & 4 & 30 & 4 & 6 & 46 & 7 & 7 & 62 & 5 & 8 \\ 15 & 4 & 6 & 31 & 5 & 8 & 47 & 9 & 11 & 63 & 6 & 10 \\ 16 & 1 & 1 & 32 & 1 & 1 & 48 & 2 & 2 & 64 & 1 & 1 \end{matrix}

Stern sequence, we can arrange w(n) into a triangular array, where the k-th row is given by w(n) with 2^{k}/3 < n < 2^{k+1}/3, with the convention of when k = 0, n = 0. The entries in this triangular array are one half the even elements from the diatomic array of the Stern 1 1

2 1 2
2 4 1 4 2
3 2 5 4 6 1 6 4 5 2 3
3 7 2 9 5 7 4 9 6 8 1 8 6 9 4 7 5 9 2 7 3

Table 7: Triangular Array for w(n)

sequence. What properties does this sequence have? How often is w(n) even? What is the largest value in a row? What type of recurrence relations does this sequence have? Does it have a nice expression for its generating function?

Looking at Table 6, we see many similarities to the Stern sequence. We notice the first five values are the same, and that at powers of 2, the sequence is 1. The Stern sequence has lots of beautiful recurrence relations, and while w(n) is a little more complicated, it has some similar structure.

We now show the sequence w(n) can be defined independently of s(n).

Theorem 11. Let w(0) = 0, w(1) = 1 and w(3) = 2. For n ≥ 1, we have

w(2n) = w(n),
w(8n ± 1) = w(4n ± 1) + 2w(n),  (10)
w(8n ± 3) = w(4n ± 1) + w(2n ± 1) − w(n).  (11)

Proof. Using the recurrence properties for s(n) and the definition of w(n), we immediately see

w(2^{k}n) = \frac{1}{2}s(3 · 2^{k}n) = \frac{1}{2}s(3n) = w(n).

Looking at w(2n + 1) we see

w(2n + 1) = \frac{1}{2}s(3n + 1) + \frac{1}{2}s(3n + 2),

which is not very enlightening. However, if we consider arithmetic progressions modulo 4, we see

w(4n + 1) = \frac{1}{2}s(3n) + s(3n + 1) = w(n) + s(3n + 1),  (12)
w(4n + 3) = \frac{1}{2}s(3n + 3) + s(3n + 2) = w(n + 1) + s(3n + 2),  (13)

which is better, but still not completely in terms of w(n). We can use a more compact notation and write (12) and (13) as

w(4n ± 1) = w(n) + s(3n ± 1).

Since we still do not have any recurrence formulas strictly in terms of w(n), we consider arithmetic progressions modulo 8. Replace n with 2n and then 2n + 1 in (12) and (13). We then use the definition and recurrence relations for s(n), and rearranging the relations in (12) and (13) to substitute in for s(3n + 1) and s(3n + 2), we obtain the recurrence relations in (10) and (11), which completes the proof.

Remark 12. We remark that the Stern sequence is a 2-regular sequence. The referee observes that, from the point of view of 2-regular sequences, the existence of recurrence formulas such as in Theorem 11 are not surprising. For more on 2-regular sequences, see Allouche and Shallit [1, Ch. 16].

A natural question to ask is, what is the largest value for w(n) in a row of its triangular array? Not surprisingly, the largest value of w(n) depends on the three largest values for s(n). Since L_{1}(r), L_{2}(r), and L_{3}(r) each satisfy a Fibonacci recurrence which is not all even, every third term in the sequence is even. This simply comes from the fact odd + even = odd, even + odd = odd, and odd + odd = even. So the maximum of w(n) in a row occurs precisely when one of L_{1}(r), L_{2}(r),or L_{3}(r) is even and then it is divided by two. Please note Table 8 gives a comparison of the three largest values for s(n) for easy reference. The boxed even values in Table 8 are divided by 2 to yield the M_{k}’s in Table 9.

Let M_{k} be the maximum of w(n) in the k-th row. The maximum values for w(n) and where they occur are given in Table 9. There is a pattern for M_{k} and where they occur, based on every third row.

The Fibonacci numbers F_{r} are even when r is a multiple of 3, which implies L_{1}(r) = F_{r+2} will be even when r ≡ 1 (mod 3). Now, L_{2}(r) = F_{r+2} − F_{r−3}, and this will be even only when r ≡ 2 (mod 3). If r ≡ 1 (mod 3), then F_{r+2} is even and F_{r−3} is odd, so that their sum is odd. If r ≡ 0 (mod 3), then F_{r+2} is odd, and F_{r−3} would be even. If r ≡ 2 (mod 3), then both are odd, so that F_{r+2} − F_{r−3} is even. We have L_{3}(r) = F_{r+2} − 3F_{r−5} is even when r ≡ 0 (mod 3).

However, it is important to note the row numbers for w(n) are shifted up one relative to the row numbers for s(n). To avoid confusion, we denote the row numbers for s(n) with r and the row numbers for w(n) with k (with k = r + 1). We then have the following theorem.

Theorem 13. For k ≥ 5, the maximum value of w(n) in the k-th row is

\frac{1}{2}F_{k+1} − \frac{1}{2}F_{k−4} when k ≡ 0 (mod 3),
\frac{1}{2}F_{k+1} − \frac{3}{2}F_{k−6} when k ≡ 1 (mod 3),
\frac{1}{2}F_{k+1} when k ≡ 2 (mod 3).

Table 8: Comparison of the Three Largest Values of s(n) in rows

\begin{matrix}row r & L_{1}(r) & L_{2}(r) & L_{3}(r) \\ 1 & 2 & 1 & N/A \\ 2 & 3 & 2 & 1 \\ 3 & 5 & 4 & 3 \\ 4 & 8 & 7 & 5 \\ 5 & 13 & 12 & 11 \\ 6 & 21 & 19 & 18 \\ 7 & 34 & 31 & 30 \\ 8 & 55 & 50 & 49 \\ 9 & 89 & 81 & 80 \\ 10 & 144 & 131 & 129 \\ 11 & 233 & 212 & 209 \\ 12 & 377 & 343 & 338 \end{matrix}

Table 9: Maxima of w(n) in rows

\begin{matrix}row & n & M_{k} & row & n & M_{k} \\ 2 & 1 & 1 & 13 & 1817, 1849, 2247, 2279 & 169 \\ 3 & 2 & 1 & 14 & 3641, 4551 & 305 \\ 4 & 3, 5 & 2 & 15 & 7281, 7737, 8647, 9103 & 449 \\ 5 & 7,9 & 4 & 16 & 14567, 14791, 17977, 18201 & 716 \\ 6 & 15, 17 & 6 & 17 & 29127, 36409 & 1292 \\ 7 & 25, 29, 35, 39 & 9 & 18 & 58255, 61895, 69177, 72817 & 1902 \\ 8 & 57, 71 & 17 & 19 & 116505, 118329, 143815, 145639 & 3033 \\ 9 & 113, 121, 135, 143 & 25 & 20 & 233017, 291271 & 5473 \\ 10 & 231, 281 & 40 & 21 & 466033, 495161, 533415, 582543 & 8057 \\ 11 & 455, 569 & 72 & 22 & 932071, 946631, 1150521, 1165081 & 12848 \\ 12 & 911, 967, 1081, 1137 & 106 & 23 & 1864135, 2330169 & 23184 \end{matrix}

Proof. This is a consequence of Theorems 2, 4, and 6. Note when the three largest values for s(n) begin their Fibonacci recurrence (starting at their initial values): L_{1}(r) for all r, L_{2}(r) for r ≥ 4 (k ≥ 5), and L_{3}(r) for r ≥ 8 (k ≥ 9). However, in the r = 6-th row (k = 7-th), L_{3} is 18 and the largest even value among L_{1}, L_{2}, and L_{3}. We also see that \frac{1}{2}(F_{8} − 3F_{1}) = \frac{1}{2}(21 − 3) = \frac{1}{2} · 18 = 9, so the last condition is also true for k = 7. This completes the proof.

Using Theorem 13, the generating function for M_{k} is

∑_{n=0}^{∞} M_{k}x^{k} = \frac{x^{2} + x^{3} + 2x^{4} + 2x^{6} + x^{7} + 2x^{10}}{1 − 4x^{3} − x^{6}} .

The results in this paper are contained in the author’s University of Illinois Ph.D. dissertation [3], which has much more information on w(n).

References

[1] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge University Press, 2003.

[2] J. Lansing, Distribution of values of the binomial coefficients and the Stern sequence, J. Integer Seq. 16 (2013), Article 13.3.7.

[3] J. Lansing, On the Stern sequence and a related sequence, Ph. D. Dissertation, University of Illinois, 2014.

[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] S. Northshield, Stern’s diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, …, Amer. Math. Monthly 117 (2010), 581–590.

[7] B. Reznick, Regularity properties of the Stern enumeration of the rationals, J. Integer. Seq. 11 (2008), Article 08.4.1.

[8] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences. Published electronically

   at http://oeis.org.

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

2010 Mathematics Subject Classification: Primary 11B65. Keywords: Stern sequence, largest value.

(Concerned with sequences \underline{A002487} and \underline{A240388}.)

Received April 11 2014; revised version received June 17 2014. Published in Journal of Integer Sequences, July 1 2014.

Return to Journal of Integer Sequences home page.