On a Strange Recursion of Golomb

Ed Barbeau  Steve Tanny
Department of Mathematics  Department of Mathematics
University of Toronto  University of Toronto
Toronto, Canada M5S 1A1  Toronto, Canada M5S 1A1
barbeau@math.utoronto.ca  tanny@math.utoronto.ca

Submitted: January 4, 1996; Accepted: February 1, 1996.

“There are patterns I must follow just as I must breathe each breath” (Paul Simon, Patterns, 1964)

Abstract

In an unpublished note, Golomb proposed a family of “strange” recursions of metafibonacci type, parameterized by k, and, for each k, identified what he speculated was the unique increasing solution. We show that, to the contrary, there are many increasing solutions for each k, and we indicate explicitly how to construct them. We also provide some additional general results concerning the nature of the strictly increasing solutions for this unusual family of recursions.

Subject Number: 05A11

1. Introduction

In an unpublished note [1], Golomb considers a variety of sequences that satisfy “strange” recursions. Included among these are the well-known Hofstadter sequence [3] and the Newman-Conway sequence [5].

Golomb writes the “simplest strange recursion” as u(u(n)) = u(n) and easily determines the general solution for it. Subsequently, he introduces a more complicated “strange” recursion (actually a family of recursions)

b(b(n) + kn) = 2b(n) + kn  (1)

with initial conditions b(1) = 1 and b(2) = 3 for k = 1, and b(1) = 1 and b(2) = 2 for k > 1. Here k is assumed to be a positive integer.

It is tempting to try a linear function in n for b(n). At the same time, it is necessary that b(n) is a positive integer, so that (b(n) + kn) is well-defined as an index for b. This appears to motivate the following solution given (without proof) by Golomb, who states that one strictly increasing sequence which satisfies this recursion is ⌊nα_{k}⌋, where ⌊x⌋ is the floor of x (the biggest integer less than or equal to x), and α_{k} is the positive root of the equation

x^{2} + (k − 2)x − k = 0.

Golomb credits A. Fraenkel with suggesting the study of the sequences ⌊nα_{k}⌋ in this context.^{1} He also observes that no finite number of initial conditions is sufficient to uniquely specify the solution of the recurrence (1) for any given k.

Golomb notes that the above solution for (1) is not unique, but suggests that “it appears to be the only monotonically increasing solution, however” [1, p. 14]. In what follows, we show that appearances deceive and that this supposition is false for every k. We also provide additional results concerning the nature of the increasing solutions for this recursion.

2. Increasing Solutions Abound

Consider the recursion (1) with initial condition b(1) = B, where k and B are any positive integers (note that we have not assumed anything about the value of b(2)). Together these determine the values b(n) for an infinite subsequence of the arguments of b. For example,

b(B + k) = b(b(1) + k) = 2b(1) + k = 2B + k.

Applying (1) to n = B + k yields

b(b(B + k) + (B + k)k) = 2b(B + k) + (B + k)k,

which simplifies to

b((k + 2)B + (k + 1)k) = (k + 4)B + (k + 2)k.

The first two arguments of b whose values are now set are (B+k) and {(k+2)B+(k+1)k}. Clearly we can continue in this manner indefinitely.

We call this sequence of arguments, which derives from (1) and the initial condition b(1) = B, the descendant sequence of the argument 1. It is easy to see that this sequence is

1 See [2], p. 77, where the sequence ⌊nα_{k}⌋, considered as a multiset, is called the spectrum of α_{k}. strictly increasing. The descendant sequence can be defined analogously for every argument at which the value of b is known, including arguments already contained in a descendant sequence.

For given k, the values of b are now uniquely determined at all of the arguments which appear as terms in the descendant sequence for 1. However, this still leaves the value of b undefined for all the arguments between successive values of the descendant sequence of 1. Golomb’s conjecture amounts to the assertion that, in the case B = 1, for each positive integer k, there is an unique way of assigning the value of b at these arguments, given by the floor function noted above, so that b is strictly increasing and satisfies (1).

In fact, it turns out that for any positive integer B there are many ways to extend the function b so that it meets these conditions. This is readily shown by induction. Let r be a positive integer. For r = 1, we know that if b(1) = B, then the next element where b is known is B + k, the first descendant of 1, and b(B + k) = 2B + k. To extend b to the B + k − 2 arguments between 1 and B + k, the only requirement is that the values of b at these arguments must lie between b(1) and b(B + k). Since there are b(B + k) − b(1) − 1 = (2B + k) − B − 1 = B + k − 1 possible values for b in this set, which exceeds B + k − 2, many increasing assignments are possible. Thus, we can extend b to all the arguments up to and including b(1) + k.

As our induction hypothesis, suppose for any positive integer r, we have selected or determined the value of b so that it is increasing for all the arguments b(1), b(2), ..., b(r) + kr. We show that we can now extend b for all the arguments between b(r) + kr and b(r + 1) + k(r + 1) to ensure that b remains increasing.

Since b(r) > 0 we necessarily have r < b(r) + kr. Thus, by the induction hypothesis, b has already been determined for the argument r + 1. It follows from (1) that the value of b at the argument b(r + 1) + k(r + 1) is set too. Further, observe that the difference between the two arguments

{b(r + 1) + k(r + 1)} − {b(r) + kr} = b(r + 1) − b(r) + k,

while the difference between their corresponding images under b is 2[b(r + 1) − b(r)] + k, which is larger. Thus, there is enough room to define the value of b at all the arguments between b(r) + kr and b(r + 1) + k(r + 1) in an increasing way. The only difficulty that might arise is if for some argument i, where b(r) + kr < i < b(r + 1) + k(r + 1), the value of b(i) is already determined because i is a descendant of some earlier argument whose value under b has already been set (and thus by the recursion the value b(i) would be known).

In fact, this cannot occur, since if it did, then it must be possible to write i = b(j)+kj for some j < i, and by the recursion (1), b(i) = 2b(j) + kj. But either j ≤ r or j ≥ r + 1. In the first instance, since b is increasing, i = b(j) + kj ≤ b(r) + kr, while in the second, i = b(j) + kj ≥ b(r + 1) + k(r + 1). Both conclusions are contrary to the assumption about i. This completes the induction.

3. Analyzing the Descendant Sequence

From what we have already seen, it is evident that the domain of increasing functions b which satisfy (1) can be partitioned into two disjoint sets. The first consists of all those elements whose value under b can be specified arbitrarily, subject to the condition that b is increasing (call these seeds). For example, note that from the above derivation, every element from 1 to B + k − 1 is a seed. The second set consists of all the descendants under b of each of the seeds.

In fact, a second partition is more interesting. It contains an infinite number of sets, each of which consists of an unique seed, together with all of its descendants whose value under b is determined from the recursion (1) and the value of b at the seed. It seems reasonable that these sets must form a partition, since the descendants of any seed depend on the value of b at the seed, and the value of b at the seeds is completely arbitrary subject to the constraint that b is increasing. This suggests that no two distinct seeds can have any descendants in common.

To verify that this is the case, we determine first, for any given seed p, an explicit formula for all the descendants of p, together with their respective values under b. We focus first on the seed 1. We showed above that the first two such descendants of 1 are B + k and (k + 2)B + (k + 1)k, with values under b of 2B + k and 2b(B + k) + (B + k)k, respectively. It is easy to verify by induction that we can continue to apply (1) in the same way as we have just done for the first two arguments to define recursively polynomials x_{k}(n), y_{k}(n), f_{k}(n) and g_{k}(n) which satisfy equations of the form

b(x_{k}(n)B + y_{k}(n)k) = f_{k}(n)B + g_{k}(n)k  (2)

for n = 1, 2, 3, · · ·. More precisely, by applying (1) to the argument x_{k}(n)B+y_{k}(n)k (which is the n^{th} descendant of 1) we obtain

b(b(x_{k}(n)B +y_{k}(n)k)+(x_{k}(n)B +y_{k}(n)k)k) = 2b(x_{k}(n)B +y_{k}(n)k)+(x_{k}(n)B +y_{k}(n)k)k.

From (2), after some rearrangement of the terms, we have

b((f_{k}(n) + kx_{k}(n))B + (g_{k}(n) + ky_{k}(n))k) = (2f_{k}(n) + kx_{k}(n))B + (2g_{k}(n) + ky_{k}(n))k

the form of which is analogous to (2) and provides the basis for defining x_{k}(n+1), y_{k}(n+1), f_{k}(n + 1) and g_{k}(n + 1), respectively. As a result, we have the following four recursions:^{2}

x_{k}(n + 1) = f_{k}(n) + kx_{k}(n)  (3)
y_{k}(n + 1) = g_{k}(n) + ky_{k}(n)  (4)
f_{k}(n + 1) = 2f_{k}(n) + kx_{k}(n)  (5)
g_{k}(n + 1) = 2g_{k}(n) + ky_{k}(n)  (6)

2 These recursions are similar to the ones appearing in Jones and Matijasevic [4, p. 695].

From this we derive that for every positive integer n,

x_{k}(n + 1) = f_{k}(n + 1) − f_{k}(n)  (7)
y_{k}(n + 1) = g_{k}(n + 1) − g_{k}(n)  (8)

Further, the relations (3) and (5) yield

x_{k}(n + 1) = (k + 2)x_{k}(n) − kx_{k}(n − 1)  (9)
f_{k}(n + 1) = (k + 2)f_{k}(n) − kf_{k}(n − 1)  (10)

while (4) and (6) imply

y_{k}(n + 1) = (k + 2)y_{k}(n) − ky_{k}(n − 1)  (11)
g_{k}(n + 1) = (k + 2)g_{k}(n) − kg_{k}(n − 1)  (12)

Thus, x_{k}(n), y_{k}(n), f_{k}(n) and g_{k}(n) satisfy the same second order linear recursion. The initial conditions are (x_{k}(1), y_{k}(1), f_{k}(1), g_{k}(1)) = (1, 1, 2, 1) and (x_{k}(2), y_{k}(2), f_{k}(2), g_{k}(2)) = (k + 2, k + 1, k + 4, k + 2). It follows that for all n

g_{k}(n) = x_{k}(n)  (13)

But from this fact, together with (8), and (7), we conclude that for n > 2

y_{k}(n) = x_{k}(n) − x_{k}(n − 1) = f_{k}(n) − 2f_{k}(n − 1) + f_{k}(n − 2)  (14)

Thus, from the above relations, we are readily able to generate recursively all four sequences. It is also easy to confirm by induction that x_{k}(n), y_{k}(n), f_{k}(n) and g_{k}(n) are polynomials in k of degree n − 1.

From the relations among the initial conditions, and the fact that all these polynomials satisfy the same recursion which obviously generates an increasing sequence, it follows that for all positive integers n > 1, y_{k}(n) < g_{k}(n) = x_{k}(n) < f_{k}(n). Notice that x_{k}(n)B + y_{k}(n)k < f_{k}(n)B + g_{k}(n)k.

In fact, the above argument can be applied to any seed p, where b(p) is specified arbitrarily to ensure that b is increasing. Then in the same way as above we can use the relation (1) together with the starting value b(p) to identify all the arguments which are the descendants of p and determine their respective values under b. We find that the kth descendant of p is given by x_{k}(n)b(p) + y_{k}(n)kp, and

b(x_{k}(n)b(p) + y_{k}(n)kp) = f_{k}(n)b(p) + g_{k}(n)kp  (15)

where the same polynomials x_{k}(n), y_{k}(n), f_{k}(n) and g_{k}(n) as defined above appear once again. This characterizes completely the elements in each of the sets in the second partition which we described above.

The relation (15) leads to a set of interesting identities among the polynomials which will prove useful. For any positive integers r and s,

x_{k}(r + s) = x_{k}(s)f_{k}(r) + x_{k}(r)y_{k}(s)k  (16)
y_{k}(r + s) = x_{k}(s)g_{k}(r) + y_{k}(r)y_{k}(s)k  (17)
f_{k}(r + s) = f_{k}(s)f_{k}(r) + x_{k}(r)g_{k}(s)k  (18)
g_{k}(r + s) = f_{k}(s)g_{k}(r) + y_{k}(r)g_{k}(s)k  (19)

The proof (by induction on s) of each of these identities is quite straightforward. For example, to prove (16), use (3) and the initial conditions defining the polynomials to observe that it holds for s = 1, 2. Assume (16) is true for all positive integers less than s. For s we have from (3) that

x_{k}(r + s) = (k + 2)x_{k}(r + s − 1) − kx_{k}(r + s − 2) = (k + 2) [x_{k}(s − 1)f_{k}(r) + x_{k}(r)y_{k}(s − 1)k] − k [x_{k}(s − 2)f_{k}(r) + x_{k}(r)y_{k}(s − 2)k]

= [(k + 2)x_{k}(s − 1) − kx_{k}(s − 2)] f_{k}(r) + kx_{k}(r) [(k + 2)y_{k}(s − 1) − ky_{k}(s − 2)]
= x_{k}(s)f_{k}(r) + x_{k}(r)y_{k}(s)k

as required. The proof of the identities (17)–(19) is similar.^{3}

We are now in a position to show that no two distinct seeds q and p have any descendants in common. For simplicity take q = 1, and suppose a seed p > 1 lies between the rth and (r + 1)th descendant of 1, that is,

x_{k}(r)B + y_{k}(r)k < p < x_{k}(r + 1)B + y_{k}(r + 1)k.  (20)

Since b is increasing, the image of p under b satisfies the inequalities

f_{k}(r)B + g_{k}(r)k < b(p) < f_{k}(r + 1)B + g_{k}(r + 1)k.  (21)

We now verify that the s^{th} descendant of p, which is given by x_{k}(s)b(p) + y_{k}(s)kp, lies between the (r + s)th and (r + s + 1)th descendant of 1, so satisfies

x_{k}(r + s)B + y_{k}(r + s)k < x_{k}(s)b(p) + y_{k}(s)kp < x_{k}(r + s + 1)B + y_{k}(r + s + 1)k. (22)

3 Professor Doron Zeilberger observed that equations (16)–(19) are analogs of the addition theorems for trigonometric functions, and can be proved the same way, using Binet’s formula.

The value of this descendant of p under b must lie in the interval

f_{k}(r + s)B + g_{k}(r + s)k < b(x_{k}(s)b(p) + y_{k}(s)kp) < f_{k}(r + s + 1)B + g_{k}(r + s + 1)k. (23)

Both (22) and (23) follow directly from the inequalities (20)–(21) and the identities (16)– (19). For example,

x_{k}(s)b(p) + y_{k}(s)kp > x_{k}(s)f_{k}(r)B + x_{k}(s)g_{k}(r)k + y_{k}(s)x_{k}(r)Bk + y_{k}(r)y_{k}(s)k^{2}
= (x_{k}(s)f_{k}(r) + y_{k}(s)x_{k}(r))B + (x_{k}(s)g_{k}(r) + ky_{k}(r)y_{k}(s))k
= x_{k}(r + s)B + y_{k}(r + s)k

as required. The other half of (22), as well as (23), follow in an entirely analogous manner. Note that to derive (23) we also use (15). This shows that no two descendants of the seeds 1 and p can ever coincide. The argument is easily generalized for any two seeds q and p.

4. Observations on the Case B = 1

This is the special case considered by Golomb [1]. We begin by supplying a simple proof, which Golomb omits, that the function ⌊nα_{k}⌋ specified above is a solution of the recurrence (1). Write nα_{k} = ⌊nα_{k}⌋ + fr(n; k), where fr(n; k) is the fractional part of nα_{k}. Let c_{k}(n) = ⌊nα_{k}⌋. Then

c_{k}(c_{k}(n) + kn) = ⌊(c_{k}(n) + kn)α_{k}⌋
= ⌊c_{k}(n)α_{k} + knα_{k}⌋
= ⌊⌊nα_{k}⌋α_{k} + knα_{k}⌋
= ⌊nα_{k}^{2} − fr(n; k)α_{k} + knα_{k}⌋
= ⌊nk + (2 − k)nα_{k} − fr(n; k)α_{k} + knα_{k}⌋,

where the last equality is obtained by substituting for α_{k}^{2} from the equation which defines α_{k}. But nk is an integer, so we have

c_{k}(c_{k}(n) + kn) = ⌊2nα_{k} − fr(n; k)α_{k}⌋ + nk
= ⌊2⌊nα_{k}⌋ + 2fr(n; k) − fr(n; k)α_{k}⌋ + nk
= 2⌊nα_{k}⌋ + nk + ⌊(2 − α_{k})fr(n; k)⌋.

But from the definition of α_{k} it follows easily that 0 < 2 − α_{k} < 1, so c_{k}(n) = ⌊nα_{k}⌋ satisfies the recursion (1), and c_{k}(1) = 1.

The particular solution c_{k}(n) provides an interesting new relation between the polynomials x_{k}(n) and y_{k}(n) in the case B = 1. First, observe that for B = 1 the descendant sequence of arguments x_{k}(n)B + y_{k}(n)k from the initial condition b(1) = B simplifies to the sequence x_{k}(n) + y_{k}(n)k = g_{k}(n) + y_{k}(n)k = y_{k}(n + 1). Similarly, from the relations proved in Section 3, the values of b at these arguments reduce to f_{k}(n) + g_{k}(n)k = f_{k}(n) + x_{k}(n)k = f_{k}(n + 1) − f_{k}(n) = x_{k}(n + 1). Thus, for B = 1, b(y_{k}(n + 1)) = x_{k}(n + 1). Since b(1) = 1, b(y_{k}(n)) = x_{k}(n) for all positive integers n. But this relation holds for every solution b, so we can apply this result to the solution c_{k}(n) = ⌊nα_{k}⌋ to conclude that for all n and k, ⌊y_{k}(n)α_{k}⌋ = x_{k}(n).

For k = 1, observe that α_{1} is the golden mean, and the solution c_{1}(n) = ⌊nα_{1}⌋ has the property that c_{1}(F_{n}) equals F_{n+1} or F_{n+1} − 1, where F_{n} is the Fibonacci sequence, with initial conditions F_{1} = F_{2} = 1. More precisely, it is easy to show that for n > 1, c_{1}(F_{2n}) = F_{2n+1} − 1 while c_{1}(F_{2n−1}) = F_{2n} (see [2], p. 300ff).

It turns out that for B = k = 1, all of the increasing solutions of (1) involve the Fibonacci sequence in an interesting way which generalizes this result. From (9) and (11) (and the initial conditions specified by Golomb for k = 1), we have x_{1}(n) = F_{2n} and y_{1}(n) = F_{2n−1}. From what we have just shown above, it follows that every solution b(n) of (1) satisfies b(F_{2n−1}) = F_{2n}. In particular this holds for the solution c_{1} given above, so this provides an alternate proof that c_{1}(F_{2n−1}) = F_{2n}.

In fact, this argument can be extended to yield additional relationships with the Fibonacci numbers. For example, suppose a particular solution s(n) of (1) satisfies s(3) = A, where to ensure monotonicity we require 3 < s(3) < s(4) < 8. It follows from the recursion (1) that s(A + 3) = 2A + 3, and, more generally,

s(F_{2n}A + 3F_{2n−1}) = F_{2n+1}A + 3F_{2n}.  (24)

This can be proved easily by induction.

We can also derive explicitly a second solution to the recursion (1) for B = k = 1. Notice that if in (24) we select A = 5, the next Fibonacci number following 3, then the expressions on both sides of (24) simplify to yield s(F_{2n+4}) = F_{2n+5} (see [2], p. 294, where the required Fibonacci identities are discussed). Combining this with what we showed above (namely, since s is a solution, s(F_{2n−1}) = F_{2n}), we have that for all n, s(F_{n}) = F_{n+1}. Once we extend the definition of this s appropriately to all other seeds, then s is a particularly simple example of a second solution of the original problem posed by Golomb; further, it must be different from the function c_{1} since c_{1}(F_{2n}) = F_{2n+1} − 1.

We can complete the specification of this strictly increasing s(n) in an interesting and natural way. For any j, where F_{n} < j < F_{n+1}, let

j = F_{n} + F_{x_{1}} + F_{x_{2}} + ⋯ + F_{x_{r}}

be the Zeckendorf representation of j (see [2], p. 295). It follows that no two of the F_{x}’s have consecutive indices. Then define

s(j) = F_{n+1} + F_{x_{1}+1} + F_{x_{2}+1} + ... + F_{x_{r}+1}.

It is easy to show by induction that s(j) is a strictly increasing solution of the recurrence (1). Note that since s(F_{n}) = F_{n+1}, we have that s(F_{n}) + s(F_{n+1}) = s(F_{n+2}), so s is additive on the Fibonacci indices, and has been extended to all other arguments additively.

5. References

[1] S. W. Golomb, Discrete chaos: sequences satisfying “strange” recursions, preprint (undated, likely late eighties or early nineties).

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

[3] R. K. Guy, Some suspiciously simple sequences, Amer. Math Monthly 93, (1986), 186–190.

[4] J. P. Jones and Y. V. Matijasevic, Proof of recursive unsolvability of Hilbert’s tenth problem, Amer. Math Monthly, 98(8), October, 1991, 689–709.

[5] C. L. Mallows, Conway’s challenge sequence, Amer. Math Monthly 98 (1991), 5–20.