On Families of Nonlinear Recurrences Related to Digits

Th. Stoll^{1}

Faculty of Mathematics University of Vienna Nordbergstraße 15 1090 Vienna Austria

               thomas.stoll@univie.ac.at

and Institute of Discrete Mathematics and Geometry Wiedner Hauptstraße 8–10 1040 Vienna Austria

                stoll@dmg.tuwien.ac.at

Abstract

Consider the sequence of positive integers (u_{n})_{n≥1} defined by u_{1} = 1 and u_{n+1} = ⌊\sqrt{2} (u_{n} + \frac{1}{2})⌋. Graham and Pollak discovered the unexpected fact that u_{2n+1}−2u_{2n−1} is just the n-th digit in the binary expansion of \sqrt{2}. Fix w ∈ ℝ_{>0}. In this note, we first give two infinite families of similar nonlinear recurrences such that u_{2n+1} − 2u_{2n−1} indicates the n-th binary digit of w. Moreover, for all integral g ≥ 2, we establish a recurrence such that u_{2n+1} − gu_{2n−1} denotes the n-th digit of w in the g-ary digital expansion.

1 Introduction

In 1969, Hwang and Lin [6] studied Ford and Johnson’s algorithm for sorting partially-sorted sets (see also [7]). In doing so, they came across the sequence of integers

1, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, 77, 109 … defined by the nonlinear recurrence

1Supported in part by the Austrian Science Foundation (FWF) FSP-Project S8302-MAT

u_{1} = 1,  u_{n+1} = ⌊\sqrt{2u_{n}(u_{n} + 1)}⌋ , n ≥ 1.  (1)

Since there is no integral square between 2u_{n}^{2} + 2u_{n} and 2u_{n}^{2} + 2u_{n} + \frac{1}{2} = 2(u_{n} + \frac{1}{2})^{2} we can rewrite the recurrence in a more striking form, i.e.,

u_{1} = 1,  u_{n+1} = ⌊\sqrt{2}(u_{n} + 1/2)⌋ , n ≥ 1.  (2)

While investigating closed-form expressions for u_{n} in (2), Graham and Pollak [4] discovered the following amazing fact:

Fact 1 (Graham/Pollak). We have that

d_{n} = u_{2n+1} − 2u_{2n−1}

is the n-th digit in the binary expansion of \sqrt{2} = (1.011010100 …)_{2}.

Since then, sequences arising from the recurrence relation given in (2) are referred to as Graham-Pollak sequences [9, 10]. Sloane [9] gives three special sequences depending on the initial term u_{1}, i.e., sequence \underline{A001521} for u_{1} = 1, \underline{A091522} for u_{1} = 5 and sequence \underline{A091523} for u_{1} = 8.

The curiosity of Fact 1 has drawn the attention of several mathematicians and has been cited a few times, see Ex. 30 in Guy [5], Ex. 3.46 in Graham/Knuth/Patashnik [3] and in Borwein/Bailey [1, pp. 62–63]. A generalization to numbers other than \sqrt{2} is, however, not straightforward from Graham and Pollak’s proof. Nevertheless, Erdős and Graham [2, p. 96] suspected that similar results would also hold “for \sqrt{m} and other algebraic numbers”, but they concluded that “we have no idea what they are.”

By applying a computational guessing approach, Rabinowitz and Gilbert [8] could give an answer in the binary case:

Theorem 1.1 (Rabinowitz/Gilbert). Let w ∈ ℝ_{>0} and t = w/2^{m}, where m = ⌊log_{2} w⌋. Furthermore, set

a = 2 (1 − \frac{1}{t + 2}) , b = \frac{2}{a}.

Define a sequence (u_{n})_{n≥1} by the recurrence

u_{1} = 1
u_{n+1} = \begin{cases}⌊a(u_{n} + 1/2)⌋, & if n is odd; \\ ⌊b(u_{n} + 1/2)⌋, & if n is even. \end{cases}

Then u_{2n+1} − 2u_{2n−1} is the n-th digit in the binary expansion of w.

Note that for w = \sqrt{2} we get a = b = \sqrt{2} and the statement of Fact 1 is obtained. However, the values of a and b in Theorem 1.1 are somehow wrapped in mystery. Rabinowitz and Gilbert first varied a and b in order that u_{2n+1} − 2u_{2n−1} ∈ {0, 1}. They found that ab = 2 and discovered that the represented w indeed equals 2(a − 1)/(2 − a) provided that 1 < a < 3/2.

It is a natural question to ask, whether there exist other values of a and b such that the binary expansion of w is obtained. Here we prove

Theorem 1.2. Let w ∈ ℝ_{>0} and t = w/2^{m}, where m = ⌊log_{2} w⌋. Furthermore, let j ∈ ℤ_{>0} and set the values of a and b according to one of the following cases:

Case I:

a = 2 (j − \frac{1}{t + 2}) , b = \frac{2}{a}.

Case II:

a = 2j − \frac{t}{t + 2}, b = \frac{2}{a}.

Define a sequence (u_{n})_{n≥1} by the recurrence

u_{1} = 1
u_{n+1} = \begin{cases}⌊a(u_{n} + 1/2)⌋, & if n is odd; \\ ⌊b(u_{n} + ε)⌋, & if n is even, \end{cases}

where 1/3 ≤ ε < 2/3 in Case I and ε = 1/2 in Case II, respectively. Then u_{2n+1} − 2u_{2n−1} is the n-th digit in the binary expansion of w.

In the closing paragraph of [8], the authors finally posed the question, whether there exists an analogous statement for ternary digits. Here we prove

Theorem 1.3. Let w ∈ ℝ_{>0} and g ≥ 2 be an integer. Furthermore, set t = w/g^{m}, where m = ⌊log_{g} w⌋ and

a = \frac{g}{(g − 1)(t + g)}, b = \frac{g}{a}.

Define a sequence (u_{n})_{n≥1} by the recurrence

u_{1} = 1
u_{n+1} = \begin{cases}⌊a(u_{n} + ε)⌋, & if n is odd; \\ ⌊b(u_{n} + 1/(g − 1))⌋, & if n is even, \end{cases}

where −1/g ≤ ε < (g + 1)(g − 2)/g. Then u_{2n+1} − gu_{2n−1} is the n-th digit in the g-ary digital expansion of w.

In view of Fact 1, we note two immediate consequences of Theorem 1.2 and Theorem 1.3. To begin with, we substitute w = t = \sqrt{2} in Case I and Case II of Theorem 1.2. This implies a = 2j − 2 + \sqrt{2} (Case I) and a = 2j + 1 − \sqrt{2} (Case II) for j ≥ 1. By ordering all such values into a single sequence, we obtain Corollary 1.1. Let a_{j} = j + (−1)^{j}\sqrt{2} for j = 0, 2, 3 … and b_{j} = 2/a_{j}. Define a sequence (u_{n})_{n≥1} by

u_{1} = 1
u_{n+1} = \begin{cases}⌊a_{j}(u_{n} + 1/2)⌋, & if n is odd; \\ ⌊b_{j}(u_{n} + 1/2)⌋, & if n is even. \end{cases}

Then u_{2n+1} − 2u_{2n−1} is the n-th digit in the binary expansion of \sqrt{2} = (1.011010100 …)_{2}.

Note that for j = 1 we have a_{1} = 1 − \sqrt{2} < 0 and u_{5} − 2u_{3} = 7 − 2 · 2 = 3, which is not a binary digit.

On the other hand, if we take g = 3, w = t = \sqrt{2} and ε = 1/2 in Theorem 1.3, we get

Corollary 1.2. Define a sequence (u_{n})_{n≥1} by

u_{1} = 1
u_{n+1} = \begin{cases}⌊a(u_{n} + 1/2)⌋, & if n is odd; \\ ⌊b(u_{n} + 1/2)⌋, & if n is even, \end{cases}

where a = (9 − 3\sqrt{2})/14 and b = 6 + 2\sqrt{2}. Then u_{2n+1} − 3u_{2n−1} is the n-th digit in the ternary expansion of \sqrt{2} = (1.102011221 …)_{3}.

2 Proofs

For later reference we state an easy, but useful proposition.

Proposition 2. Let g ≥ 2 be an integer and w = (d_{1}d_{2}d_{3} …)_{g} be the g-ary digital expansion of w with d_{1} ≠ 0 and 0 ≤ d_{n} < g for n ≥ 1. Suppose further that for n ≥ 1 not all of d_{n}, d_{n+1}, … equal g − 1. Then

• t = (d_{1}.d_{2}d_{3} …)_{g} with 1 ≤ t < g,

• d_{n} = ⌊tg^{n−1}⌋ − g⌊tg^{n−2}⌋.

Proof. Since m = ⌊log_{g} w⌋ it is immediate that 1 ≤ w/g^{m} < g. Moreover,

⌊tg^{n−1}⌋ − g⌊tg^{n−2}⌋ = (d_{1}d_{2} … d_{n})_{g} − (d_{1}d_{2} … d_{n−1}0)_{g} = d_{n}.

2.1 Proof of Theorem 1.2

First, we prove that in Case I there hold

u_{2k} = 2^{k−1} + ⌊t2^{k−1}⌋ + (j − 1)(2^{k} + 2⌊t2^{k−2}⌋ + 1),
u_{2k+1} = 2^{k} + ⌊t2^{k−1}⌋,

so that Proposition 2 gives u_{2n+1} − 2u_{2n−1} = d_{n}. To begin with, we have u_{1} = 2^{0} + ⌊t/2⌋ = 1 because of 1 ≤ t < 2. We are going to employ an induction argument. Suppose that the result holds true for u_{2k−1}. Then

u_{2k} = ⌊2 (j − \frac{1}{t + 2}) (2^{k−1} + ⌊t2^{k−2}⌋ + \frac{1}{2})⌋

= (j − 1)(2^{k} + 2⌊t2^{k−2}⌋ + 1) + ⌊(1 − \frac{1}{t + 2}) (2^{k} + 2 ⌊t2^{k−2}⌋ + 1)⌋ .

Thus, it suffices to show that

⌊\frac{t + 1}{t + 2} · (2^{k} + 2 ⌊t2^{k−2}⌋ + 1)⌋ = 2^{k−1} + ⌊t2^{k−1}⌋ .  (3)

Since 2 ⌊t2^{k−2}⌋ = ⌊t2^{k−1}⌋ − d_{k} by Proposition 2, we may rewrite (3) in the equivalent form

(t + 2) (2^{k−1} + ⌊t2^{k−1}⌋) ≤ (t + 1) (2^{k} + ⌊t2^{k−1}⌋ − d_{k} + 1)
< (t + 2) (2^{k−1} + ⌊t2^{k−1}⌋ + 1) .

Straightforward algebraic manipulation leads to

t2^{k−1} + ⌊t2^{k−1}⌋ ≤ t2^{k} + (1 − d_{k})(t + 1) < (t2^{k−1} + ⌊t2^{k−1}⌋ + 1) + 1 · (t + 1),

which is obviously true because of ⌊t2^{k−1}⌋ ≤ t2^{k−1} < ⌊t2^{k−1}⌋ + 1. Now, assume that the result is true for u_{2k}. Thus, we have to show that

u_{2k+1} = ⌊\frac{t + 2}{j(t + 2) − 1}(u_{2k} + ε)⌋ = 2^{k} + ⌊t2^{k−1}⌋.  (4)

The equality of integer floors (4) can be rewritten in terms of two inequalities, i.e.,

(j(t + 2) − 1)(2^{k} + ⌊t2^{k−1}⌋) ≤ (t + 2) (2^{k−1} + ⌊t2^{k−1}⌋ + ε + (j − 1)(2^{k} + 2 ⌊t2^{k−2}⌋ + 1))
< (j(t + 2) − 1)(2^{k} + ⌊t2^{k−1}⌋ + 1).

Again, we use Proposition 2 and proper term cancelling such that (4) translates into

0 ≤ ⌊t2^{k−1}⌋ − t2^{k−1} + (t + 2) (ε + (j − 1)(1 − d_{k})) < j(t + 2) − 1.

Since −1 < ⌊t2^{k−1}⌋ − t2^{k−1} ≤ 0 and ε < 2/3 we have

⌊t2^{k−1}⌋ − t2^{k−1} + (t + 2) (ε + (j − 1)(1 − d_{k})) < (t + 2)(2/3 + (j − 1)) ≤ j(t + 2) − 1.

On the other hand, ε ≥ 1/3 implies

⌊t2^{k−1}⌋ − t2^{k−1} + (t + 2) (ε + (j − 1)(1 − d_{k})) > −1 + (t + 2)ε ≥ 0.

This finishes the proof of Theorem 1.2 for Case I.

Let now a, b and ε be according to Case II. Again, by Proposition 2 it suffices to show that

u_{2k} = 2^{k} + ⌊t2^{k−2}⌋ + (j − 1)(2^{k} + 2⌊t2^{k−2}⌋ + 1),
u_{2k+1} = 2^{k} + ⌊t2^{k−1}⌋.

As before, we have u_{1} = 2^{0} + ⌊t/2⌋ = 1. Assume that the closed-form expression holds true for u_{2k−1}. Then

u_{2k} = ⌊(2j − \frac{t}{t + 2}) (2^{k−1} + ⌊t2^{k−2}⌋ + \frac{1}{2})⌋

= (j − 1)(2^{k} + 2⌊t2^{k−2}⌋ + 1) + ⌊(1 − \frac{t}{2(t + 2)}) (2^{k} + 2 ⌊t2^{k−2}⌋ + 1)⌋ .

Hence, it is sufficient to prove that

2^{k} + ⌊t2^{k−2}⌋ ≤ \frac{t + 4}{2(t + 2)} · (2^{k} + 2⌊t2^{k−2}⌋ + 1) < 2^{k} + ⌊t2^{k−2}⌋ + 1.  (5)

By multiplying (5) with 2(t+2) and simply canceling out all terms with ⌊t2^{k−2}⌋, (5) simplifies to

0 ≤ 4 (⌊t2^{k−2}⌋ − t2^{k−2}) + t + 4 < 2t + 4.  (6)

Relation (6) is obviously true, since −1 < ⌊t2^{k−2}⌋ − t2^{k−2} ≤ 0. For the induction step from u_{2k} to u_{2k+1} we have to ensure that

u_{2k+1} = ⌊\frac{2(t + 2)}{2j(t + 2) − t} (u_{2k} + \frac{1}{2})⌋ = 2^{k} + ⌊t2^{k−1}⌋,

or equivalently, that

2^{k} + ⌊t2^{k−1}⌋ ≤ \frac{2(t + 2)}{2j(t + 2) − t} (2^{k} + ⌊t2^{k−2}⌋ + \frac{1}{2} + (j − 1)(2^{k} + 2⌊t2^{k−2}⌋ + 1))
< 2^{k} + ⌊t2^{k−1}⌋ + 1.

We replace all ⌊t2^{k−2}⌋ by (⌊t2^{k−1}⌋ − d_{k}) /2 and after some term sorting we obtain

0 ≤ (t + 2)(2j − 1)(1 − d_{k}) + t2^{k} − 2⌊t2^{k−1}⌋ < 2j(t + 2) − t.  (7)

Since 0 ≤ t2^{k} − 2⌊t2^{k−1}⌋ = d_{k+1} + t2^{k} − ⌊t2^{k}⌋ = (d_{k+1}.d_{k+2}d_{k+3} …)_{2} < 2, the inequalities given in (7) hold true for all k ≥ 1. The proof of Theorem 1.2, Case II is done. It is not difficult to see that ε = 1/2 cannot be replaced by any other value.

2.2 Proof of Theorem 1.3

Here we prove

u_{2k} = (g^{k−1} − 1)/(g − 1),
u_{2k+1} = g^{k} + ⌊tg^{k−1}⌋.

Similarly as before, the statement of Theorem 1.3 is then obtained from Proposition 2. Again, u_{1} = g^{0} + ⌊t/g⌋ = 1. Suppose first, the result holds for u_{2k}. Then

u_{2k+1} = ⌊b (u_{2k} + \frac{1}{g − 1})⌋ = ⌊(t + g)(g^{k−1} − 1) + (t + g)⌋ = g^{k} + ⌊tg^{k−1}⌋.

Vice versa, assume the result holds for u_{2k+1}. Let {x} denote the fractional part of x ∈ ℝ_{>0}. Then

u_{2k+2} = ⌊a(u_{2k+1} + ε)⌋ = ⌊a⌊g^{k−1}(t + g)⌋ + aε⌋

= ⌊a ⌊\frac{g^{k}}{a(g − 1)}⌋ + aε⌋ = \frac{g^{k} − 1}{g − 1} + ⌊\frac{1}{g − 1} − a \{\frac{g^{k}}{a(g − 1)}\} + aε⌋ .

Since 0 < a ≤ g/(g^{2} − 1), we have 1/(g − 1) − a ≥ a/g. Thus, for ε ≥ −1/g we get

\frac{1}{g − 1} − a \{\frac{g^{k}}{a(g − 1)}\} + aε > \frac{1}{g − 1} − a + aε ≥ \frac{a}{g} − \frac{a}{g} = 0.

On the other hand, if ε < (g + 1)(g − 2)/g then

\frac{1}{g − 1} − a \{\frac{g^{k}}{a(g − 1)}\} + aε ≤ \frac{1}{g − 1} + aε < \frac{1}{g − 1} + \frac{g}{g^{2} − 1} · \frac{(g + 1)(g − 2)}{g} = 1.

This finishes the proof of Theorem 1.3.

Acknowledgment

The author wishes to thank the referee for her/his detailed remarks on the original manu– script; in particular, for pointing out several inaccuracies in the statement of the results.

References

[1] J. Borwein and D. Bailey, Mathematics by Experiment, Natick, MA, 2003.

[2] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, L’Enseignement Mathématique, Genève, 1980.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, MA, second edition, 1994.

[4] R. L. Graham and H. O. Pollak, Note on a nonlinear recurrence related to \sqrt{2}, Math. Mag., 43 (1970), 143–145.

[5] R. K. Guy, The strong law of small numbers, Amer. Math. Monthly, 95 (1988), 697–712.

[6] F. Hwang and S. Lin, An analysis of Ford and Johnson’s sorting algorithm, in: Proc. Third Annual Princeton Conf. on Inform. Sci. and Systems, 1969, pp. 292–296.

[7] D. E. Knuth, The Art of Computer Programming – Volume 3, Addison-Wesley, Mass.- London-Don Mills, Ont., 2nd ed., 1998.

[8] S. Rabinowitz and P. Gilbert, A nonlinear recurrence yielding binary digits, Math. Mag., 64 (1991), 168–171.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at www.research.att.com/∼njas/sequences, 1996–2005.

[10] E. W. Weisstein, Graham-Pollak Sequence (from Mathworld, a Wolfram Web Re– source), http://mathworld.wolfram.com/Graham-PollakSequence.html, 1999–2005.

2000 Mathematics Subject Classification: Primary 11B37; Secondary 11A67. Keywords: Graham-Pollak sequence, nonlinear recurrence, digits.

(Concerned with sequences \underline{A001521}, \underline{A091522} and \underline{A091523}.)

Received April 1 2005; revised version received May 12 2005. Published in Journal of Integer Sequences, May 24 2005.

Return to Journal of Integer Sequences home page.