On Properties of the General Bow Sequence

Melissa Dennison Department of Mathematics Baldwin Wallace University Berea, OH 44017 USA

                              mdenniso@bw.edu

Abstract

In this paper, we define and study a two-parameter family of recursive sequences, which we call the bow sequences. The general bow sequence is defined similarly to the Stern sequence, and many of the properties of the bow sequences are related to known properties of the Stern sequence. In particular, we focus on common divisors of consecutive terms, maximum values, sums of terms, and generating functions.

1 Introduction

In 1858, Stern [19] studied the so-called “diatomic” array of integers, which was motivated by a function studied by Eisenstein. The diatomic array can be completely understood by consideration of the Stern sequence \underline{A002487}. The Stern sequence is defined as follows:

s(0) = 0, s(1) = 1;  (1)
s(2n) = s(n), for n ≥ 1;  (2)
s(2n + 1) = s(n) + s(n + 1), for n ≥ 1.  (3)

The terms in the Stern sequence can be written in an array, where the r^{th} row consists of s(n) for 2^{r} ≤ n ≤ 2^{r+1}, for r ≥ 0. The even entries in each row are copied from the previous row, and the odd entries are found by adding adjacent entries in the row above. The first five rows of the array are given in Table 1, with the enumeration of terms as in Sloane’s On-Line Encyclopedia of Integer Sequences [18].

De Rham [8] was the first to consider the Stern sequence as defined above. He attributed the name to Bachmann [4], who considered only the diatomic array. The related Stern-Brocot array [10] was used in defining Minkowski’s ?-function [15], and the Stern sequence

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

Table 1: The first five rows of the diatomic array for the Stern sequence

has recently been used to understand 2-regular sequences [1] and the Tower of Hanoi graph [12].

In this paper we define a new two-parameter family of recursive sequences called the bow sequences, which have the flipped recursion from the Stern recursion.

Definition 1. The general bow sequence, b_{α,β}(n), for α, β ∈ ℤ is defined by:

b_{α,β}(0) = 0, b_{α,β}(1) = α, b_{α,β}(2) = β;  (4)
b_{α,β}(2n) = b_{α,β}(n) + b_{α,β}(n + 1), for n ≥ 2;  (5)
b_{α,β}(2n + 1) = b_{α,β}(n), for n ≥ 1.  (6)

We define b_{α,β}(0) = 0 to simplify results, although the designation does not affect later terms in the sequence, as b_{α,β}(0) does not enter into the recurrence. It is also worth noting that (5) fails in the case where n = 1, since if α ≠ 0, then b_{α,β}(2) ≠ b_{α,β}(1) + b_{α,β}(2). Table 2 lists the first 17 values of the general bow sequence.

Many properties of the bow sequences are related to known properties of the Stern sequence. In particular, in Section 3 we note that although pairs of consecutive terms in the Stern sequence are always relatively prime, pairs of consecutive terms in the bow sequences may share a common factor, but triples may only share factors which divide gcd(α, β). We also show that, much like the Stern sequence, the maximum values of the bow sequences on intervals are related to the Fibonacci numbers.

Next, in Section 4, we derive properties of the summatory function. Then we derive the generating function for the general bow sequence, and give interpretations of the generating function for two basic cases in Section 5. In particular, we note that b_{0,1}(n) is the number of ways of writing n − 2 as the sum ∑_{i} c_{i}2^{i} where c_{i} ∈ {0, 2, 3}, while b_{1,0}(n) is the number

of ways of writing n − 3 as a finite sum ∑_{i=0}^{k} c_{i}2^{i} where c_{i} ∈ {1, 3, 4}. Lastly, we look at an

alternative representation of b_{0,1}(n) in Section 6.

\begin{matrix}n & b_{α,β}(n) \\ 0 & 0 \\ 1 & α \\ 2 & β \\ 3 & α \\ 4 & α + β \\ 5 & β \\ 6 & 2α + β \\ 7 & α \\ 8 & α + 2β \\ 9 & α + β \\ 10 & 2α + 2β \\ 11 & β \\ 12 & 3α + β \\ 13 & 2α + β \\ 14 & 2α + 2β \\ 15 & α \\ 16 & 2α + 3β \end{matrix}

Table 2: The general bow sequence

2 Preliminaries

We begin by considering the values of the general bow sequence. Note that the terms of the general bow sequence are not necessarily distinct. In particular, we can see from Table 2 that b_{α,β}(10) = b_{α,β}(14).

By considering the recursion, we see that b_{α,β}(n) is linear in α and β. Accordingly, we can write

b_{α,β}(n) = αb_{1,0}(n) + βb_{0,1}(n).  (7)

For simplicity, we shall define

b_{0}(n) := b_{0,1}(n),

and

b_{1}(n) := b_{1,0}(n).

In this paper we consider the sequences b_{0}(n) \underline{A106345} and b_{1}(n) \underline{A281185}, as all other cases of the general bow sequence can be determined from these two cases by applying equation (7).

We can present the values of the general bow sequence as a “triatomic” array where the first row is b_{α,β}(1), b_{α,β}(2), b_{α,β}(3), and the second row is b_{α,β}(3), b_{α,β}(4), b_{α,β}(5), b_{α,β}(6), b_{α,β}(7). In general the r-th row contains b_{α,β}(2^{r} − 1), ..., b_{α,β}(2^{r+1} − 1). The odd entries in each row are copied from the previous row in Table 3. The even entries are found by adding the two numbers in the previous row that occur to the right of the entry. For example, the second entry in the third row, b_{α,β}(8) = α + 2β, is obtained by adding the second and third entries in the second row of the array, namely, α + β and β. The last even entry in each row is obtained by summing the first two entries in that same row. The first three rows of the array are given in Table 3.

α  β  α
α  α + β  β  2α + β  α
α α + 2β α + β 2α + 2β β 3α + β 2α + β 2α + 2β α

Table 3: First three rows of the triatomic array for the general bow sequence

The triatomic arrays for b_{0}(n) and b_{1}(n) are quite different from each other. As it turns out, b_{0}(n) is much more regular than b_{1}(n), but the two sequences share many properties. Consider Table 4 and Table 5:

0  1  0
0  1  1  1  0
0  2  1  2  1  1  1  2  0
0 3 2 3 1 3 2 2 1 2 1 3 1 2 2 3 0

Table 4: First four rows of the triatomic array for b_{0}(n)

1  0  1
1  1  0  2  1
1  1  1  2  0  3  2  2  1
1 2 1 3 1 2 2 3 0 5 3 4 2 3 2 3 1

Table 5: First four rows of the triatomic array for b_{1}(n)

3 Greatest common divisors and maximum values

3.1 Greatest common divisors of three consecutive terms

One interesting property of the bow sequences is that although two consecutive terms may share a nontrivial factor, three consecutive terms can only share factors which divide gcd (α, β).

Theorem 2. For all {α, β} and n > 0,

gcd(b_{α,β}(n), b_{α,β}(n + 1), b_{α,β}(n + 2)) = gcd(α, β).  (8)

Proof. Observe from Table 2 that gcd(b_{α,β}(n), b_{α,β}(n + 1), b_{α,β}(n + 2)) = gcd(α, β) for n = 1, 2. Now assume that this holds true for n < k.

Case 1: k = 2n + 1, with n < k. Then,

gcd(b_{α,β}(k), b_{α,β}(k + 1), b_{α,β}(k + 2))
= gcd(b_{α,β}(2n + 1), b_{α,β}(2n + 2), b_{α,β}(2n + 3))
= gcd(b_{α,β}(n), b_{α,β}(n + 1) + b_{α,β}(n + 2), b_{α,β}(n + 2))
= gcd(b_{α,β}(n), b_{α,β}(n + 1), b_{α,β}(n + 2))
= gcd(α, β).

Case 2: k = 2n, with n < k. Then,

gcd(b_{α,β}(k), b_{α,β}(k + 1), b_{α,β}(k + 2))
= gcd(b_{α,β}(2n), b_{α,β}(2n + 1), b_{α,β}(2n + 2))
= gcd(b_{α,β}(n) + b_{α,β}(n + 1), b_{α,β}(n), b_{α,β}(n + 1) + b_{α,β}(n + 2))
= gcd(b_{α,β}(n), b_{α,β}(n + 1), b_{α,β}(n + 2))
= gcd(α, β).

Thus gcd(b_{α,β}(n), b_{α,β}(n + 1), b_{α,β}(n + 2)) = gcd(α, β) for all {α, β} and n > 0.

Remark 3. This result bears some similarity to a result for pairs of consecutive terms of the Stern sequence. As noted by Stern [6, 13, 19], for n ≥ 0, every pair of consecutive terms of the Stern sequence is relatively prime, or gcd(s(n), s(n + 1)) = 1.

3.2 Greatest common divisors of pairs

Surprisingly, Theorem 2 has implications for pairs. Although we have seen in Table 4 and Table 5 that pairs frequently share common factors, when the pairs

(b_{0}(n), b_{0}(n + 1)), and (b_{1}(n), b_{1}(n + 1))

are taken together, the resulting quadruple does not have a common factor.

Theorem 4. For n ≥ 0, gcd(b_{0}(n), b_{0}(n + 1), b_{1}(n), b_{1}(n + 1)) = 1.

Proof. Suppose p is prime, and let

p | gcd(b_{0}(n), b_{0}(n + 1), b_{1}(n), b_{1}(n + 1)).

Then, p must necessarily divide b_{0}(n) and b_{0}(n + 1), so we know by Theorem 2 that p ∤ b_{0}(n + 2). Similarly, p ∤ b_{1}(n + 2). So let

b_{0}(n + 2) ≡ r (mod p) and b_{1}(n + 2) ≡ s (mod p),

where 1 ≤ r, s ≤ p − 1.

Consider b_{s,−r}(n) = sb_{1}(n) − rb_{0}(n). Thus p | b_{s,−r}(n), and p | b_{s,−r}(n + 1). Then, since

b_{s,−r}(n + 2) ≡ sr + (−r)s ≡ 0 (mod p),

we know that p | b_{s,−r}(n + 2). But this implies that p | gcd(r, s), which is a contradiction. Thus gcd(b_{0}(n), b_{0}(n + 1), b_{1}(n), b_{1}(n + 1)) = 1.

Remark 5. Note that Theorem 4 fails if we consider only three of the four terms. For example, consider n = 2149948. Then we have

(b_{0}(n), b_{0}(n + 1), b_{1}(n), b_{1}(n + 1)) = (2070, 1815, 1430, 1254)

= (2 · 3^{2} · 5 · 23, 3 · 5 · 11^{2}, 2 · 5 · 11 · 13, 2 · 3 · 11 · 19).

When we consider the triples, we find that

gcd(b_{0}(n), b_{0}(n + 1), b_{1}(n)) = 5,
gcd(b_{0}(n), b_{0}(n + 1), b_{1}(n + 1)) = 3,
gcd(b_{0}(n), b_{1}(n), b_{1}(n + 1)) = 2,
gcd(b_{0}(n + 1), b_{1}(n), b_{1}(n + 1)) = 11.

However, clearly gcd(b_{0}(n), b_{0}(n + 1), b_{1}(n), b_{1}(n + 1)) = 1.

Similarly, we have the following theorem.

Theorem 6. For n ≥ 0, gcd(b_{0}(n), b_{0}(n + 2), b_{1}(n), b_{1}(n + 2)) = 1.

Proof. Suppose p is prime, and let

p | gcd(b_{0}(n), b_{0}(n + 2), b_{1}(n), b_{1}(n + 2)).

Then, p must necessarily divide b_{0}(n) and b_{0}(n + 2), so we know by Theorem 2 that p ∤ b_{0}(n + 1). Similarly, p ∤ b_{1}(n + 1). So let

b_{0}(n + 1) ≡ r (mod p) and b_{1}(n + 1) ≡ s (mod p),

where 1 ≤ r, s ≤ p − 1.

Consider b_{s,−r}(n) = sb_{1}(n) − rb_{0}(n). Thus p | b_{s,−r}(n), and p | b_{s,−r}(n + 2). Then, since

b_{s,−r}(n + 1) ≡ sr + (−r)s ≡ 0 (mod p),

we know that p | b_{s,−r}(n + 1). But this implies that p | gcd(r, s), which is a contradiction. Thus gcd(b_{0}(n), b_{0}(n + 2), b_{1}(n), b_{1}(n + 2)) = 1.

3.3 Maximum values on intervals

For the next theorem, we will need the Fibonacci numbers \underline{A000045}, defined as usual by

F_{0} = 0, F_{1} = 1;
F_{n} = F_{n−1} + F_{n−2}, for n ≥ 2.

Theorem 7. For r ≥ 1,

b_{α,β}(2^{r}) = αF_{r−1} + βF_{r}.  (9)

In particular, for r ≥ 1, b_{0}(2^{r}) = F_{r}, b_{1}(2^{r}) = F_{r−1}, and b_{1,1}(2^{r}) = F_{r+1}.

Proof. First, note that by applying (5) and (6) we find for n ≥ 1,

b_{α,β}(4n) = b_{α,β}(2n) + b_{α,β}(2n + 1) = b_{α,β}(2n) + b_{α,β}(n).

Thus, for r ≥ 2,

b_{α,β}(2^{r}) = b_{α,β}(2^{r−1}) + b_{α,β}(2^{r−2}).

Secondly, recall by (7) that

b_{α,β}(2^{r}) = αb_{1}(2^{r}) + βb_{0}(2^{r}).

Thus we consider only these two cases. All that remains is to check the initial conditions. We find that

(b_{0}(2), b_{0}(4)) = (0, 1) = (F_{0}, F_{1}),

and

(b_{1}(2), b_{1}(4)) = (1, 1) = (F_{1}, F_{2}).

Thus the initial conditions are satisfied.

Next, we estimate the size of b_{α,β}(n). Let I_{r} = (2^{r−1}, 2^{r}] ∩ ℤ. To be specific,

I_{r} = {2^{r−1} + 1, …, 2^{r}}.

Note that

I_{r} = (2I_{r−1} − 1) ∪ 2I_{r−1}.

We have the following upper bound.

Theorem 8. For r ≥ 1,

max_{n∈I_{r}} |b_{α,β}(n)| ≤ max {|α|, |β|}F_{r+1}.  (10)

Moreover, for β ≥ α ≥ 0,

max_{n∈I_{r}} |b_{α,β}(n)| = b_{α,β}(2^{r}) = αF_{r−1} + βF_{r}.  (11)

Proof. Since b_{α,β}(n) ≥ 0 for α, β ≥ 0, |b_{α,β}(n)| ≤ b_{|α|,|β|}(n), and we may assume that α, β ≥ 0. Observe that for α, β ≥ 0 and γ = max{α, β},

b_{α,β}(n) ≤ b_{γ,γ}(n) = γb_{1,1}(n)
= γ (b_{0}(n) + b_{1}(n)) .

For r = 1, 2, it is easy to see that max_{n∈I_{r}} b_{1,1}(n) is F_{r+1}. Now assume that this holds for all r < k. Let r = k. Then

max_{n∈I_{k}} b_{1,1}(n) = max_{n∈I_{k−1}} {b_{1,1}(2n), b_{1,1}(2n − 1)}

= max_{n∈I_{k−1}} {b_{1,1}(n) + b_{1,1}(n + 1), b_{1,1}(n − 1)}.

However, one of n or n + 1 is odd. Thus, if n, n + 1 ∈ I_{k−1}, then

max_{n∈I_{k−1}} {b_{1,1}(n) + b_{1,1}(n + 1), b_{1,1}(n − 1)} ≤ max{F_{k} + F_{k−1}, F_{k}}
= max{F_{k+1}, F_{k}}
= F_{k+1}.

The previous argument fails if n + 1 is not in I_{k−1}. However, then

n + 1 = 2^{k−1} + 1,

and

b_{1,1}(2^{k−1} + 1) = b_{1,1}(2^{k−2}) = F_{k−1}

by Theorem 7.

Thus we have shown that

max_{n∈I_{k}} b_{γ,γ}(n) ≤ γF_{k+1}.

Now we will show that max_{n∈I_{r}} b_{0}(n) ≤ F_{r}. For r = 1, 2, it is easy to see that max_{n∈I_{r}} b_{0}(n) = F_{r}. Now assume that this statement also holds for all r < k. Let r = k. Then

max_{n∈I_{k}} b_{0}(n) = max_{n∈I_{k−1}} {b_{0}(2n), b_{0}(2n − 1)}

= max_{n∈I_{k−1}} {b_{0}(n) + b_{0}(n + 1), b_{0}(n − 1)}.

Similarly, one of n or n + 1 is odd, with the same result if n + 1 = 2^{k−1} + 1. Thus, if n, n + 1 ∈ I_{k−1}, then

max_{n∈I_{k−1}} {b_{0}(n) + b_{0}(n + 1), b_{0}(n − 1)} ≤ max{F_{k−1} + F_{k−2}, F_{k−1}}
= max{F_{k}, F_{k−1}}
= F_{k}.

With δ > 0 and b_{0,δ}(n) = δb_{0}(n), we have max_{n∈I_{r}} b_{0,δ}(n) ≤ δF_{r}.

Now we shall show that the maximum occurs at n = 2^{r}. Let β ≥ α ≥ 0. Then, by setting γ = α and δ = β − α in the previous results above, we find

b_{α,β}(2^{r}) = αb_{1,1}(2^{r}) + (β − α)b_{0}(2^{r})
≤ αF_{r+1} + (β − α)F_{r}
= αF_{r−1} + βF_{r}.

However, by Theorem 7 we know that b_{α,β}(2^{r}) = αF_{r−1} + βF_{r}, thus the maximum occurs at n = 2^{r}.

Remark 9. As noted by Lucas [14] and Lehmer [13], the maximum value of s(n) on I_{r} is F_{r+1}.

4 Properties of the summatory function

Next, we consider the sums of the rows of the triatomic array. We define a new function as follows:

Definition 10. D_{α,β}(r) is defined as the sum of the r^{th} row of the triatomic array of the bow sequence,

D_{α,β}(r) := ∑_{n∈I_{r+1}} b_{α,β}(n) = ∑_{n=2^{r}+1}^{2^{r+1}} b_{α,β}(n).  (12)

Lemma 11. For r ≥ 5,

D_{α,β}(r) = 3D_{α,β}(r − 1) − αF_{r−5} − βF_{r−4}.  (13)

Proof. Starting with the definition of D_{α,β}(r) and applying the recurrence, we find

D_{α,β}(r) = ∑_{n∈I_{r+1}} b_{α,β}(n)

= ∑_{n∈I_{r}} b_{α,β}(2n) + b_{α,β}(2n − 1)

= ∑_{n∈I_{r}} b_{α,β}(n) + b_{α,β}(n + 1) + b_{α,β}(n − 1)

= (∑_{n∈I_{r}} 3b_{α,β}(n)) + b_{α,β}(2^{r} + 1) − b_{α,β}(2^{r−1} + 1) + b_{α,β}(2^{r−1}) − b_{α,β}(2^{r})

= 3D_{α,β}(r − 1) + b_{α,β}(2^{r−1}) − b_{α,β}(2^{r−2}) + b_{α,β}(2^{r−1}) − b_{α,β}(2^{r}).

Then, by applying Theorem 7 and simplifying we get

D_{α,β}(r) = 3D_{α,β}(r − 1) + 2(αF_{r−2} + βF_{r−1}) − αF_{r−3} − βF_{r−2} − αF_{r−1} − βF_{r}
= 3D_{α,β}(r − 1) + α (F_{r−1} − 3F_{r−3}) + β (F_{r} − 3F_{r−2})
= 3D_{α,β}(r − 1) + α (F_{r−2} − 2F_{r−3}) + β (F_{r−1} − 2F_{r−2})
= 3D_{α,β}(r − 1) + α (F_{r−4} − F_{r−3}) + β (F_{r−3} − F_{r−2})
= 3D_{α,β}(r − 1) − αF_{r−5} − βF_{r−4}.

Lemma 11 suggests a relationship of the following form. Theorem 12. For r ≥ 1,

D_{α,β}(r) = α(\frac{7}{5} · 3^{r−1} + \frac{3}{5} · F_{r} − \frac{4}{5} · F_{r−1}) + β(\frac{2}{5} · 3^{r} − \frac{1}{5} · F_{r} + \frac{3}{5} · F_{r−1}).

Proof. By considering Table 2, we check that this holds for small r. Suppose that the formula holds for r < k. Then by Lemma 11,

D_{α,β}(k) = 3α(\frac{7}{5} · 3^{k−2} + \frac{3}{5} · F_{k−1} − \frac{4}{5} · F_{k−2}) + 3β(\frac{2}{5} · 3^{k−1} − \frac{1}{5} · F_{k−1} + \frac{3}{5} · F_{k−2})

+ αF_{k−1} − 3αF_{k−3} + βF_{k} − 3βF_{k−2}

= α(\frac{7}{5} · 3^{k−1} + \frac{9}{5} · F_{k−1} − \frac{12}{5} · F_{k−2} + F_{k−1} − 3F_{k−3})

+ β(\frac{2}{5} · 3^{k} − \frac{3}{5} · F_{k−1} + \frac{9}{5} · F_{k−2} + F_{k} − 3F_{k−2})

= α(\frac{7}{5} · 3^{k−1} + \frac{3}{5} · F_{k} − \frac{4}{5} · F_{k−1}) + β(\frac{2}{5} · 3^{k} − \frac{1}{5} · F_{k} + \frac{3}{5} · F_{k−1}).

Thus the theorem holds for r ≥ 1.

Remark 13. Theorem 12 implies that

\frac{D_{α,β}(r)}{3^{r}} = \frac{7α + 6β}{15} + O ((\frac{ϕ}{3})^{r}) = \frac{7α + 6β}{15} + o(1).

Remark 14. Interestingly, as noted by Stern [19] and Lehmer [13], the sum of the r^{th} row of the diatomic array for the Stern sequence is 3^{r} + 1.

Remark 15. Note that D_{−6,7}(r) = −5F_{r} + 9F_{r−1}, which means that the average value of b_{−6,7}(n) → 0 as n → ∞.

Now suppose we sum all the terms of the general bow sequence up to the N^{th} term. Note that summatory functions of k-regular sequences are again k-regular sequences, as they are obtained by convolution with the all 1 sequence, which is also k-regular. The result is kregular, as noted by Allouche and Shallit [2], which explains in some sense Theorem 17. Define a new function as follows:

Definition 16. E_{α,β}(N) is defined as the finite sum of the first N terms of the bow sequence,

E_{α,β}(N) := ∑_{k=1}^{N} b_{α,β}(k).  (14)

Theorem 17. For N ≥ 1 we have the following:

E_{α,β}(2N) = 3E_{α,β}(N) − α − b_{α,β}(N) + b_{α,β}(N + 1).  (15)

Proof. One can calculate quickly that this formula holds for N < 4. Let N ≥ 4. We start with the definition, separate terms and apply the recursion to find

E_{α,β}(2N) = ∑_{k=1}^{2N} b_{α,β}(k)

= b_{α,β}(1) + b_{α,β}(2) + b_{α,β}(3) + ∑_{k=4}^{2N} b_{α,β}(k)

= b_{α,β}(1) + b_{α,β}(2) + b_{α,β}(3) + ∑_{k=2}^{N} (b_{α,β}(2k) + b_{α,β}(2k + 1)) − b_{α,β}(2N + 1)

= b_{α,β}(1) + b_{α,β}(2) + b_{α,β}(3) + ∑_{k=2}^{N} (2b_{α,β}(k) + b_{α,β}(k + 1)) − b_{α,β}(2N + 1).

Using Table 2 we see that

E_{α,β}(2N) = 2α + β + ∑_{k=2}^{N} (2b_{α,β}(k) + b_{α,β}(k + 1)) − b_{α,β}(2N + 1)

= ∑_{k=1}^{N} 2b_{α,β}(k) + ∑_{k=1}^{N} b_{α,β}(k + 1) − b_{α,β}(2N + 1).

We reindex the second sum and apply (14) to obtain

E_{α,β}(2N) = 2E_{α,β}(N) + ∑_{k=2}^{N+1} b_{α,β}(k) − b_{α,β}(2N + 1)

= 2E_{α,β}(N) + E_{α,β}(N) − α + b_{α,β}(N + 1) − b_{α,β}(2N + 1).

Then by applying the recursion we get the desired result

E_{α,β}(2N) = 3E_{α,β}(N) − α − b_{α,β}(N) + b_{α,β}(N + 1).

Corollary 18. For r ≥ 3 we have

E_{α,β}(2^{r+1}) = 3E_{α,β}(2^{r}) − α(F_{r−3} + 1) − βF_{r−2}.  (16)

Proof. By Theorem 17 we have

E_{α,β}(2^{r+1}) = 3E_{α,β}(2^{r}) − α − b_{α,β}(2^{r}) + b_{α,β}(2^{r} + 1).

By applying Theorem 7 and (6), and simplifying we obtain

E_{α,β}(2^{r+1}) = 3E_{α,β}(2^{r}) − α − (αF_{r−1} + βF_{r}) + (αF_{r−2} + βF_{r−1})
= 3E_{α,β}(2^{r}) − α − αF_{r−3} − βF_{r−2}
= 3E_{α,β}(2^{r}) − α(F_{r−3} + 1) − βF_{r−2}.

Corollary 18 suggests the following relationship.

Theorem 19. For r ≥ 1 we have

E_{α,β}(2^{r}) = α (\frac{7}{10} · 3^{r−1} − \frac{1}{5} · F_{r} + \frac{3}{5} · F_{r−1} + \frac{1}{2}) + β (\frac{1}{5} · 3^{r} + \frac{2}{5} · F_{r} − \frac{1}{5} · F_{r−1}) . (17)

Proof. By considering Table 2, we check that this holds for small r ≥ 1. Suppose that the formula holds for r < k. Then, by Corollary 18,

E_{α,β}(2^{r}) = 3α (\frac{7}{10} · 3^{r−2} − \frac{1}{5} · F_{r−1} + \frac{3}{5} · F_{r−2} + \frac{1}{2})

+ 3β (\frac{1}{5} · 3^{r−1} + \frac{2}{5} · F_{r−1} − \frac{1}{5} · F_{r−2}) − α(F_{r−4} + 1) − βF_{r−3}

= α (\frac{7}{10} · 3^{r−1} − \frac{3}{5} · F_{r−1} + \frac{9}{5} · F_{r−2} + \frac{3}{2} − F_{r−4} − 1)

+ β (\frac{1}{5} · 3^{r} + \frac{6}{5} · F_{r−1} − \frac{3}{5} · F_{r−2} − F_{r−3}) .

Then, by simplifying the Fibonacci terms, we find

E_{α,β}(2^{r}) = α (\frac{7}{10} · 3^{r−1} − \frac{3}{5} · F_{r−1} + \frac{4}{5} · F_{r−2} + F_{r−3} + \frac{1}{2})

+ β (\frac{1}{5} · 3^{r} + \frac{1}{5} · F_{r−1} + \frac{2}{5} · F_{r−2})

= α (\frac{7}{10} · 3^{r−1} − \frac{1}{5} · F_{r} + \frac{3}{5} · F_{r−1} + \frac{1}{2}) + β (\frac{1}{5} · 3^{r} + \frac{2}{5} · F_{r} − \frac{1}{5} · F_{r−1}) .

Thus the theorem holds for r ≥ 1.

Remark 20. Theorem 19 implies that

\frac{E_{α,β}(2^{r})}{3^{r}} = \frac{7α + 6β}{30} + O ((\frac{ϕ}{3})^{r}) = \frac{7α + 6β}{30} + o(1).

Remark 21. By comparison, as noted by Stern [19] and Lehmer [13], the sum of the first 2^{r} terms of the Stern sequence is

\frac{1}{2} (3^{r} + 1) .

5 Generating functions

We use the following notation for generating functions:

G^{a_{1},a_{2},a_{3},...,a_{m}}(x) := x ∏_{j=0}^{∞}(1 + x^{a_{1}·2^{j}} + x^{a_{2}·2^{j}} + ⋯ + x^{a_{m}·2^{j}})  (18)
:= ∑_{n=1}^{∞} c^{a_{1},a_{2},a_{3},...,a_{m}}(n)x^{n}.  (19)

Combinatorially, this means that c^{a_{1},a_{2},a_{3},...,a_{m}}(n) is the number of ways of writing n − 1

as the sum ∑_{i≥0} γ_{i}2^{i} where γ_{i} ∈ {0, a_{1}, a_{2}, a_{3}, …, a_{m}}.

Example 22. Consider

\frac{1}{x}G^{1}(x) = ∏_{n=0}^{∞}(1 + x^{2^{j}}) = \frac{1}{1 − x} = ∑_{k=0}^{∞} x^{k}.

Thus we recover the fact that every integer n > 0 has a unique representation

n = ∑_{i=0}^{∞} γ_{i}2^{i},

where γ_{i} ∈ {0, 1}.

We now consider the generating function for the general bow sequence. First, let

B_{α,β}(x) = ∑_{n≥0} b_{α,β}(n)x^{n} = αB_{1,0}(x) + βB_{0,1}(x).  (20)

It follows from (10) that B_{1,0}(x) and B_{0,1}(x) have radius of convergence 1.

By repeatedly applying (5) and (6) and tweaking the limits, we have

B_{α,β}(x) = αx + βx^{2} + ∑_{n≥3} b_{α,β}(n)x^{n}

= αx + βx^{2} + ∑_{n≥1} b_{α,β}(2n + 1)x^{2n+1} + ∑_{n≥2} b_{α,β}(2n)x^{2n}

= αx + βx^{2} + ∑_{n≥1} b_{α,β}(n)x^{2n+1} + ∑_{n≥2}(b_{α,β}(n) + b_{α,β}(n + 1))x^{2n}

= αx + βx^{2} + ∑_{n≥1} b_{α,β}(n)x^{2n+1} + ∑_{n≥2} b_{α,β}(n)x^{2n} + ∑_{n≥2} b_{α,β}(n + 1)x^{2n}

= αx + βx^{2} + ∑_{n≥1} b_{α,β}(n)x^{2n+1} + ∑_{n≥2} b_{α,β}(n)x^{2n} + ∑_{n≥3} b_{α,β}(n)x^{2n−2}

= αx + βx^{2} + x ∑_{n≥1} b_{α,β}(n)x^{2n} + ∑_{n≥2} b_{α,β}(n)x^{2n} + \frac{1}{x^{2}} ∑_{n≥3} b_{α,β}(n)x^{2n}

= αx + βx^{2} + x ∑_{n≥1} b_{α,β}(n)x^{2n} + ∑_{n≥1} b_{α,β}(n)x^{2n} − αx^{2}

+ \frac{1}{x^{2}} ∑_{n≥1} b_{α,β}(n)x^{2n} − α − βx^{2}

= −α + αx − αx^{2} + (\frac{1}{x^{2}} + 1 + x) B_{α,β}(x^{2})

= −α(1 − x + x^{2}) + \frac{1}{x^{2}} (1 + x^{2} + x^{3})B_{α,β}(x^{2}).

Since b_{α,β}(0) = 0 and b_{α,β}(1) = α, we can write B_{α,β}(x) = αx+x^{2}C_{α,β}(x), with C_{α,β}(0) = β, so B_{α,β}(x^{2}) = αx^{2} + x^{4}C_{α,β}(x^{2}). Thus we have

B_{α,β}(x) = αx + x^{2}C_{α,β}(x)

= \frac{1}{x^{2}} (1 + x^{2} + x^{3})(αx^{2} + x^{4}C_{α,β}(x^{2})) − α(1 − x + x^{2}).

Solving for C_{α,β}(x), we find

C_{α,β}(x) = \frac{1}{x^{2}} (α(1 − x + x^{2} + x^{3}) + x^{2}C_{α,β}(x^{2})(1 + x^{2} + x^{3}) − α(1 − x + x^{2}))
= αx + C_{α,β}(x^{2})(1 + x^{2} + x^{3}).

We can feed this identity back into the equation to get

C_{α,β}(x) = αx + (1 + x^{2} + x^{3})(αx^{2} + C_{α,β}(x^{4})(1 + x^{4} + x^{6}))
= αx + (1 + x^{2} + x^{3})αx^{2} + (1 + x^{2} + x^{3})(1 + x^{4} + x^{6})C_{α,β}(x^{4}).

After N steps,

C_{α,β}(x) = αx + α ∑_{k=0}^{N} x^{2·2^{k}} ∏_{j=0}^{k}(1 + x^{2·2^{j}} + x^{3·2^{j}}) + ∏_{k=0}^{N+1}(1 + x^{2·2^{k}} + x^{3·2^{k}})C_{α,β}(x^{2^{N+2}}).

Since, C_{α,β}(x) = β + x · P (x) for some P (x), C_{α,β}(x^{2^{N+2}}) − β = x^{2^{N+2}}P (x^{2^{N+2}}). Thus for |x| < 1, C_{α,β}(x^{2^{N+2}}) − β → 0 as N → ∞; hence we have

C_{α,β}(x) = αx + α ∑_{k=0}^{∞} x^{2·2^{k}} ∏_{j=0}^{k}(1 + x^{2·2^{j}} + x^{3·2^{j}}) + β ∏_{k=0}^{∞}(1 + x^{2·2^{k}} + x^{3·2^{k}}).

Thus we have the following theorem.

Theorem 23. The generating function for the general bow sequence is:

B_{α,β}(x) = αx + αx^{3} + αx^{2} ∑_{k=0}^{∞} x^{2·2^{k}} ∏_{j=0}^{k}(1 + x^{2·2^{j}} + x^{3·2^{j}})  (21)

+ βx^{2} ∏_{k=0}^{∞}(1 + x^{2·2^{k}} + x^{3·2^{k}}).

Since B_{α,β}(x) = αB_{1,0}(x) + βB_{0,1}(x), we can state two combinatorial implications. First, as also noted by Anders, Lansing, Reznick, and the author [3] we have

B_{0,1}(x) := ∑_{n=0}^{∞} b_{0}(n)x^{n} = x^{2} ∏_{k=0}^{∞}(1 + x^{2·2^{k}} + x^{3·2^{k}}) = xG^{2,3}(x)  (22)

for the case when α = 0, β = 1.

We see that b_{0}(n) = c^{2,3}(n − 1), where c^{2,3}(m) is the number of ways of writing m − 1 as the sum ∑_{i} c_{i}2^{i} where c_{i} ∈ {0, 2, 3}. We interpret this statement as:

Corollary 24. Combinatorially, for n ≥ 2, b_{0}(n) is the number of ways of writing n − 2 as the sum ∑_{i} c_{i}2^{i} where c_{i} ∈ {0, 2, 3}.

We also have

B_{1,0}(x) := ∑_{n=0}^{∞} b_{1}(n)x^{n} = x + x^{3} + x^{2} ∑_{k=0}^{∞} x^{2·2^{k}} ∏_{j=0}^{k}(1 + x^{2·2^{j}} + x^{3·2^{j}})  (23)

for the case when α = 1, β = 0. We interpret this statement as:

Corollary 25. Combinatorially, for n ≥ 4, b_{1}(n) is the number of ways of writing n−2−2^{k+1}

as the sum ∑_{i=0}^{k} c_{i}2^{i} where c_{i} ∈ {0, 2, 3} and k ∈ ℕ.

Remark 26. By rearranging, we find that b_{1}(n) is also the number of ways of writing n − 2

as the sum ∑_{i=0}^{k} c_{i}2^{i} where k ∈ ℕ, c_{i} ∈ {0, 2, 3} for i ≤ k − 1, and c_{k} ∈ {2, 4, 5}.

Alternatively, since ∑_{i=0}^{k} 2^{i} = 2^{k+1} − 1, we get the following formula

B_{1,0}(x) = x + x^{3} + x^{3} ∑_{k=0}^{∞} ∏_{j=0}^{k}(x^{1·2^{j}} + x^{3·2^{j}} + x^{4·2^{j}}),  (24)

which means that b_{1}(n) is the number of ways of writing n − 3 as a finite sum ∑_{i=0}^{k} c_{i}2^{i} where

c_{i} ∈ {1, 3, 4}. Remark 27. Similarly, Reznick [17] showed for the Stern sequence that

S(x) = xT (x) = x ∏_{j=0}^{∞}(1 + x^{2^{j}} + x^{2·2^{j}}).  (25)

By equation (18) we see that S(x) = G^{1,2}(x).

6 Another representation of b_{0}(n)

In this section, we discuss another representation of b_{0}(n), found independently in unpublished work by Paul Barry [5], and referenced in Sloane’s On-Line Encyclopedia of Integer Sequences [18]. The sequence was defined by Barry, but was not shown to satisfy the bow recurrence. We show that b_{0}(n) can be determined by computing this finite sum, which is independent of the recurrence. Before we give this new equation we must first state a few formulas which will be necessary in the proof of our theorem. The first is the well-known dePolignac’s formula.

Theorem 28 (dePolignac’s Formula). [11, 16] For n ≥ 1, the exponent of the highest power of a prime p dividing n! is

s_{p}(n) := ∑_{k=1}^{∞} ⌊\frac{n}{p^{k}} ⌋ .  (26)

We will need the following corollary for the proof of the next theorem.

Corollary 29. For m ≥ 1,

s_{2}(2m + 1) = s_{2}(2m) = s_{2}(m) + m.  (27)

Proof. We write (2m + 1)! = (2m + 1)(2m)!, thus s_{2}(2m + 1) = s_{2}(2m).

Then, pulling the first term out of the sum, we find

s_{2}(2m) = ⌊\frac{2m}{2}⌋ + ∑_{k=2}^{∞} ⌊\frac{2m}{2^{k}}⌋
= m + s_{2}(m).

Thus s_{2}(2m + 1) = s_{2}(2m) = s_{2}(m) + m.

Remark 30. The second equality in Corollary 29 can also be shown directly by noting that

(2m)! = 2^{m}m! ∏_{j=1}^{m}(2j − 1).

Definition 31. Define ϵ(m) to be the smallest non-negative residue of m modulo 2, thus m ∈ {0, 1}.

Let

c(n) := ∑_{k=0}^{⌊ \frac{n}{2} ⌋} ϵ (\binom{k}{n − 2k}) .  (28)

The terms of this sequence are 1, 0, 1, 1, 1, 0, 2, 1, 2, … We can see that this looks the same as b_{0}(n + 2). In fact, we shall prove that c(n − 2) = b_{0}(n).

Let c(n − 2) = a(n). We have the following lemma.

Lemma 32.

\binom{2a + 1}{2b + 1} ≡ \binom{2a + 1}{2b} ≡ \binom{2a}{2b} ≡ \binom{a}{b} (mod 2).

Proof. To show that the first three have the same parity, we note that

\frac{(2a + 1)!}{(2b + 1)!(2a − 2b)!}, \frac{(2a + 1)!}{(2b)!(2a + 1 − 2b)!}, and \frac{(2a)!}{(2b)!(2a − 2b)!}

share all the same even factors in both their numerator and denominator. Thus the highest power of 2 dividing \binom{2a+1}{2b+1}, \binom{2a+1}{2b}, and \binom{2a}{2b} is the same, and they are all congruent modulo 2.

Then, to show that \binom{a}{b} ≡ \binom{2a}{2b} (mod 2), we notice that if s_{2}(a) = r, then by Corollary 29 we know that s_{2}(2a) = r+a. Similarly, if s_{2}(b) = t, then s_{2}(2b) = t+b. Lastly, if s_{2}(a−b) = s, then s_{2}(2a − 2b) = s + (a − b).

The highest power of 2 dividing \binom{a}{b} is r − s − t, and the highest power of 2 dividing \binom{2a}{2b} is r + a − (t + b) − s − (a − b) = r − s − t. Thus the highest power of 2 dividing \binom{a}{b} and \binom{2a}{2b} is the same, and they are congruent modulo 2.

Remark 33. Note that Lemma 32 also follows from Lucas’s Theorem, stated below. In particular, we can see that \binom{2a}{2b} ≡ \binom{a}{b} (mod 2) since multiplication by 2 simply shifts all the indices in the base 2 expansions of a and b up by 1.

Theorem 34 (Lucas’s Theorem). [9] For non-negative integers m and n and a prime p, the congruence relation

\binom{m}{n} ≡ ∏_{i=0}^{k} \binom{m_{i}}{n_{i}} (mod p)

holds, where m = ∑_{i=0}^{k} m_{i}p^{i} and n = ∑_{i=0}^{k} n_{i}p^{i} with m_{i}, n_{i} ∈ {0, …, p − 1} are the base p

expansions of m and n, using the convention that \binom{m}{n} = 0 if m < n.

6.1 A New Formula for b_{0}(n)

We use Theorem 28, Corollary 29, and Lemma 32 to prove that b_{0}(n) satisfies the following formula.

Theorem 35. For n ≥ 2, b_{0}(n) can be described by the following formula

b_{0}(n) = a(n) := ∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{k}{n − 2 − 2k}) .  (29)

Proof. Clearly b_{0}(2) = 1 = a(2). Defining a(0) = a(1) = 0, we shall show that the bow recursion holds for a(n).

First we shall show that a(2n + 1) = a(n), or

∑_{k=0}^{⌊(2n+1)/2−1⌋} ϵ (\binom{k}{2n − 1 − 2k}) = ∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{k}{n − 2 − 2k}) .  (30)

Consider the terms in the left hand side of (30)

∑_{k=0}^{⌊(2n+1)/2−1⌋} ϵ (\binom{k}{2n − 1 − 2k}) = ∑_{k=0}^{n−1} ϵ (\binom{k}{2n − 1 − 2k}) .

In general, when k is even, the term \binom{k}{2a+1} ≡ 0 mod 2. Thus we need only consider the terms where k is odd. So let k = 2a + 1 and now consider the sum

∑_{a=0}^{⌊n/2−1⌋} ϵ (\binom{2a + 1}{2n − 1 − 2(2a + 1)}) .

We know that

∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{2k + 1}{2n − 1 − 2(2k + 1)}) = ∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{k}{n − 2 − 2k})  (31)

because the terms are equal, by Lemma 32 with a = k, and b = n − 2 − 2k. Thus, the recurrence a(2n + 1) = a(n) holds.

Second, we must show that a(2n) = a(n) + a(n + 1) holds, or

∑_{k=0}^{n−1} ϵ (\binom{k}{2n − 2 − 2k}) = ∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{k}{n − 2 − 2k}) + ∑_{k=0}^{⌊(n+1)/2−1⌋} ϵ (\binom{k}{n − 1 − 2k}) . (32)

We shall first consider the right hand side.

By applying Lemma 32 with a = k and b = n − 2 − 2k, we find

∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{k}{n − 2 − 2k}) = ∑_{k=0}^{⌊n/2−1⌋} ϵ (\binom{2k + 1}{2n − 4 − 4k}) .  (33)

Similarly applying Lemma 32 with a = k and b = n − 1 − 2k, we obtain

∑_{k=0}^{⌊(n+1)/2−1⌋} ϵ (\binom{k}{n − 1 − 2k}) = ∑_{k=0}^{⌊(n+1)/2−1⌋} ϵ (\binom{2k}{2n − 2 − 4k}) .  (34)

Summing (33) and (34) together we observe that these are the odd and even terms of the sum

∑_{k=0}^{n−1} ϵ (\binom{k}{2n − 2 − 2k}) .  (35)

Therefore (32) holds and we have shown that a(2n) = a(n) + a(n + 1), and hence b_{0}(n) = a(n).

7 Acknowledgments

Many of the results in this paper were part of the author’s doctoral dissertation [7] at the University of Illinois at Urbana-Champaign. The author wishes to thank Professor Bruce Reznick for his guidance, support, and enthusiasm. The author would also like to thank the referee for their careful reading and thoughtful additions.

References

[1] J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), 163–197.

[2] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[3] K. Anders, M. Dennison, J. Lansing, and B. Reznick, Congruence properties of binary partition functions, Ann. Comb. 17 (2013), 15–26.

[4] P. Bachmann, Niedere Zahlentheorie, vol. 1, 1902. Reprinted by Chelsea, 1968.

[5] P. Barry, unpublished, cited in [18], sequence \underline{A106345}, 2005.

[6] N. Calkin and H. Wilf, Recounting the rationals, Amer. Math. Monthly 107 (2000), 360–363.

[7] M. Dennison, A sequence related to the Stern sequence, Ph.D. dissertation, University of Illinois at Urbana-Champaign, 2010.

[8] G. de Rham, Un peu de mathématiques à propos d’une courbe plane, Elem. Math. 2 (1947), 73–76, 89–97.

[9] N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589–592.

[10] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.

[11] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 2nd ed., Clarendon Press, 1945.

[12] A. Hinz, S. Klavžar, U. Milutinović, D. Parisse, and C. Petr, Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, Euro. J. Comb. 26 (2005), 693– 708.

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

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

[15] H. Minkowski, Zur Geometrie der Zahlen, Ver. III, Int. Math-Kong., Heidelberg, 1904, pp. 164–173. Also in Gesammelte Abhandlungen, Vol. 2, Chelsea, 1967, pp. 45–52.

[16] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991.

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

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

cally at https://oeis.org.

[19] M. A. Stern, Ueber eine Zahlentheoretische Funktion, J. Reine Angew. Math. 55 (1858), 193–220.

2010 Mathematics Subject Classification: Primary 11B37. Keywords: Fibonacci number, generating function, recursion, Stern sequence.

(Concerned with sequences \underline{A000045}, \underline{A002487}, \underline{A106345}, and \underline{A281185}.)

Received December 19 2017; revised versions received December 19 2018; March 24 2019. Published in Journal of Integer Sequences, March 28 2019.

Return to Journal of Integer Sequences home page.