Asymptotic Series for Hofstadter’s Figure-Figure Sequences

Benoît Jubin^{1} Mathematics Research Unit University of Luxembourg 6 rue Coudenhove-Kalergi L-1359 Luxembourg City Grand-Duchy of Luxembourg

                      benoit.jubin@uni.lu

Abstract

We compute asymptotic series for Hofstadter’s figure-figure sequences.

1 Introduction

We consider disjoint partitions of the set of strictly positive integers into two subsets such that one set, B, consists of the differences of consecutive elements of the other set, A, and a given difference appears at most once. There are many such partitions. We call a the (strictly increasing) sequence enumerating A, and b the (injective) sequence of its first differences, both with offset 1. Hofstadter’s figure-figure sequences are the sequences a and b corresponding to the partition with the set A lexicographically minimal. This is equivalent to b being increasing. The sequences read

a_{n} = 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …  (OEIS \underline{A005228}),
b_{n} = 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, …  (OEIS \underline{A030124}).

These sequences were introduced by Hofstadter in [2, p. 73]. They appear as an example of complementary sequences in [3]. Their asymptotic behavior does not seem to be given anywhere in the literature except for the asymptotic equivalents mentioned by Hasler and Wilson in the related OEIS entries [1]. In this article, we compute asymptotic series for these sequences.

1 Supported by the Luxembourgish FNR via the AFR Postdoc Grant Agreement PDR 2012-1.

We have by definition b_{n} = a_{n+1}−a_{n}, so a_{n} = 1+∑_{k=1}^{n−1} b_{k}. Since the sequence a is strictly increasing, given any n ≥ 1, there is a unique k ≥ 1 such that a_{k} − k < n ≤ a_{k+1} − (k + 1). This defines a sequence u by letting u_{n} be this k. Therefore,

a(u_{n}) − u_{n} < n ≤ a(u_{n} + 1) − (u_{n} + 1).  (1)

The sequence u is non-decreasing (actually, u_{n+1} − u_{n} ∈ {0, 1}) and u_{1} = 1. It reads

u_{n} = 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, …  (OEIS \underline{A225687}).

The partition condition implies

b_{n} = n + u_{n}.

As a consequence,

a_{n} = 1 + \frac{(n − 1)n}{2} + ∑_{k=1}^{n−1} u_{k}.  (2)

2 Bounds and asymptotic equivalents

Since u_{n} ≥ 1, we have a_{n} ≥ \frac{1}{2}n(n + 1). Therefore, the left inequality of (1) implies \frac{1}{2}u_{n}(u_{n} +

1) − u_{n} ≤ n − 1, or u_{n}^{2} − u_{n} − 2(n − 1) ≤ 0, so u_{n} ≤ \frac{1}{2} + \sqrt{\frac{1}{4} + 2(n − 1)}, and finally

1 ≤ u_{n} < \sqrt{2n} + \frac{1}{2}.

This implies n + 1 ≤ b_{n} < n + \sqrt{2n} + \frac{1}{2}, so

b_{n} ∼ n.

The upper bound on u implies in turn a_{n} < 1 + \frac{1}{2}(n − 1)n + ∑_{k=1}^{n−1}(\sqrt{2k} + \frac{1}{2}). Since the function \sqrt{x} is strictly increasing, we have ∑_{k=1}^{n−1} \sqrt{k} < ∫_{1}^{n} \sqrt{x} dx = \frac{2}{3}(n^{3/2} − 1). Therefore

\frac{n^{2}}{2} + \frac{n}{2} ≤ a_{n} < \frac{n^{2}}{2} + \frac{2^{3/2}}{3} n^{3/2} − \frac{1}{3}

and in particular

a_{n} ∼ \frac{n^{2}}{2} .

The relation a_{n} < \frac{n^{2}}{2} + \frac{2^{3}}{3} (\frac{n}{2})^{3/2} − \frac{1}{3} and the right inequality of (1) imply n < \frac{(u_{n}+1)^{2}}{2} + \frac{2^{3/2}}{3} (u_{n} + 1)^{3/2} − u_{n} − \frac{4}{3}, which implies u_{n} → +∞. Therefore 2n ≤ u_{n}^{2} + O(u_{n}^{3/2}), but we saw that u_{n} = O(\sqrt{n}), so O(u_{n}^{3/2}) ⊆ O(n^{3/4}) ⊆ o(n), so u_{n}^{2} ≥ 2n + o(n), so u_{n} ≥ \sqrt{2n} + o(\sqrt{n}). Combining this with the above upper bound, we obtain

u_{n} ∼ \sqrt{2n}

and in particular O(u_{n}) = O(\sqrt{n}).

3 Asymptotic series

Since a_{n} ∼ \frac{n^{2}}{2} , we have a_{n+1} − a_{n} = O(n). Now (1) gives a(u_{n}) = n + O(u_{n}). On the other hand, (2) gives a_{n} = \frac{n^{2}}{2} + ∑_{k=1}^{n−1} u_{k} + O(n), therefore \frac{u_{n}^{2}}{2} + ∑_{k=1}^{u_{n}−1} u_{k} = n + O(u_{n}). Since u_{n} = O(\sqrt{n}), we can increment the upper limit of the summation index by 1, and since O(u_{n}) = O(\sqrt{n}), we obtain the main relation

\frac{u_{n}^{2}}{2} + ∑_{k=1}^{u_{n}} u_{k} = n + O(\sqrt{n}).

We are now ready to prove by induction that for all K ≥ 1, we have the asymptotic expansion

u_{n} = ∑_{k=1}^{K}(−1)^{k+1} \frac{2^{1+(k−1)k/2}}{∏_{j=1}^{k−1}(2^{j} + 1)} (\frac{n}{2})^{1/2^{k}} + o (n^{1/2^{K}}) .  (3)

Indeed, the case K = 1 reduces to u_{n} ∼ \sqrt{2n}, which we already proved. We also prove the case K = 2 separately since it is slightly different from the general case. We write u_{n} = \sqrt{2n} + v_{n} with v_{n} = o(\sqrt{n}). We have

\frac{u_{n}^{2}}{2} − n = \sqrt{2n} v_{n} + \frac{v_{n}^{2}}{2} .

We do not know a priori that v_{n}^{2} = O(\sqrt{n}), and that is why we have to prove this case separately. We also have

∑_{k=1}^{u_{n}} u_{k} = \sqrt{2} ∑_{k=1}^{u_{n}} \sqrt{k} + ∑_{k=1}^{u_{n}} v_{k} = \frac{2^{3/2}}{3} u_{n}^{3/2} + o(O(u_{n})^{3/2}) + ∑_{k=1}^{u_{n}} v_{k}.

We have ∑_{k=1}^{u_{n}} v_{k} = o(O(\sqrt{n})^{3/2}) ⊆ o(n^{3/4}) and o(O(u_{n})^{3/2}) ⊆ o(n^{3/4}). We also have u_{n}^{3/2} ∼ (\sqrt{2n})^{3/2} = (2n)^{3/4}. Therefore,

\frac{u_{n}^{2}}{2} + ∑_{k=1}^{u_{n}} u_{k} − n = \sqrt{2n} v_{n} + \frac{v_{n}^{2}}{2} + \frac{2^{9/4}}{3} n^{3/4} + o(n^{3/4}).

This has to be O(\sqrt{n}) by the main relation. Dividing the right-hand side by \sqrt{2n}, we obtain

v_{n} + \frac{v_{n}^{2}}{2\sqrt{2n}} + \frac{2^{7/4}}{3} n^{1/4} = o(n^{1/4}).

Since v_{n} = o(\sqrt{n}), we have \frac{v_{n}^{2}}{2\sqrt{2n}} = o(v_{n}), so

v_{n} + \frac{2^{7/4}}{3} n^{1/4} = o(n^{1/4}) + o(v_{n}),

so v_{n} ∼ −\frac{2^{2}}{3} (\frac{n}{2})^{1/4}, as desired.

Now, suppose that the expansion holds for some K ≥ 2. We prove it for K + 1. It will be convenient to denote the coefficients of the expansion by

α_{k} = (−1)^{k+1} \frac{2^{1+(k−1)k/2}}{∏_{j=1}^{k−1}(2^{j} + 1)},

so α_{1} = 2. We write v_{n} = o(n^{1/2^{K}}) for the remainder in (3). Then (3) gives

u_{n}^{2} = (\sqrt{2n} + ∑_{k=2}^{K} α_{k} (\frac{n}{2})^{1/2^{k}} + v_{n})^{2} = 2n (1 + \frac{1}{\sqrt{2n}} ∑_{k=2}^{K} α_{k} (\frac{n}{2})^{1/2^{k}} + \frac{v_{n}}{\sqrt{2n}})^{2}

= 2n (1 + \frac{2}{\sqrt{2n}} ∑_{k=2}^{K} α_{k} (\frac{n}{2})^{1/2^{k}} + 2\frac{v_{n}}{\sqrt{2n}} + O (n^{1/4+1/4−1}) + O (\frac{v_{n}^{2}}{n} ) + O (n^{1/4−1}v_{n})) .

Since K ≥ 2, we have v_{n} = o (n^{1/2^{K}}) ⊆ o (n^{1/4}). Therefore

\frac{u_{n}^{2}}{2} − n = 2 ∑_{k=2}^{K} α_{k} (\frac{n}{2})^{1/2+1/2^{k}} + \sqrt{2n} v_{n} + O(\sqrt{n}).

On the other hand,

∑_{k=1}^{u_{n}} u_{k} = ∑_{k=1}^{K} 2\frac{2^{k}}{2^{k} + 1}α_{k} (\frac{u_{n}}{2} )^{1+1/2^{k}} + o (u_{n}^{1+1/2^{K}})

= ∑_{k=1}^{K} \frac{2^{k+1}}{2^{k} + 1}α_{k} (\frac{n}{2})^{1/2+1/2^{k+1}} + o (n^{1/2+1/2^{K+1}}) .

Therefore

\frac{u_{n}^{2}}{2} + ∑_{k=1}^{u_{n}} u_{k} − n = 2 ∑_{k=2}^{K} α_{k} (\frac{n}{2})^{1/2+1/2^{k}} + ∑_{k=1}^{K} α_{k} \frac{2^{k+1}}{2^{k} + 1} (\frac{n}{2})^{1/2+1/2^{k+1}}

+ \sqrt{2n} v_{n} + o (n^{1/2+1/2^{K+1}})

= α_{K} \frac{2^{K+1}}{2^{K} + 1} (\frac{n}{2})^{1/2+1/2^{K+1}} + 2 (\frac{n}{2})^{1/2} v_{n} + o (n^{1/2+1/2^{K+1}})

since the terms in the sums cancel out except for the last in the second sum. This expression has to be O(\sqrt{n}) by the main relation, so v_{n} ∼ −\frac{2^{K}}{2^{K}+1}α_{K} (\frac{n}{2})^{1/2^{K+1}}, as desired.

From the expansion of u_{n}, we find that of b_{n} = n + u_{n}, and that of a_{n} by term-by-term integration. We obtain

b_{n} = n + ∑_{k=1}^{K}(−1)^{k+1} \frac{2^{1+(k−1)k/2}}{∏_{j=1}^{k−1}(2^{j} + 1)} (\frac{n}{2})^{1/2^{k}} + o (n^{1/2^{K}})

and

a_{n} = \frac{n^{2}}{2} + ∑_{k=1}^{K}(−1)^{k+1} \frac{2^{k(k+1)/2}}{∏_{j=1}^{k}(2^{j} + 1)} (\frac{n}{2})^{1+1/2^{k}} + o (n^{1+1/2^{K}}) .

4 Acknowledgments

I would like to thank Neil J. A. Sloane for useful comments on a first version of this article, and Clark Kimberling and Maximilian Hasler for their advice.

References

[1] The On-line Encyclopedia of Integer Sequences (OEIS), published electronically at

   http://oeis.org, 2013.

[2] Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979.

[3] Clark Kimberling, Complementary equations, J. Integer Sequences, 10 (2007), Article 07.1.4.

2010 Mathematics Subject Classification: Primary 41A60. Keywords: Hofstadter sequence, asymptotic series.

(Concerned with sequences \underline{A005228}, \underline{A030124}, \underline{A225687}.)

Received April 8 2014; revised version received May 23 2014. Published in Journal of Integer Sequences, June 10 2014.

Return to Journal of Integer Sequences home page.