A MATRIX DYNAMICS APPROACH TO GOLOMB’S RECURSION

Edward J. Barbeau, John Chew and Stephen Tanny Department of Mathematics University of Toronto Toronto, ON M5S 3G3

barbeau@math.utoronto.ca, jjchew@math.utoronto.ca and tanny@math.utoronto.ca

Submitted: February 10, 1997; Accepted: July 14, 1997

Abstract

In an unpublished note Golomb proposed a family of “strange” recursions of metafibonacci type, parametrized by k. Previously we showed that contrary to Golomb’s conjecture, for each k there are many increasing solutions, and an explicit construction for multiple solutions was displayed. By reformulating our solution approach using matrix dynamics, we extend these results to a characterization of the asymptotic behaviour of all solutions of the Golomb recursion. This matrix dynamics perspective is also used to construct what we believe is the first example of a “nontrivial” nonincreasing solution, that is, one that is not eventually increasing.

Subject Number: 05A11

Key Words: metafibonacci recursion; Golomb recursion; matrix dynamics 1. Introduction

In [3], Golomb introduced the recursion

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

with initial conditions b(1) = 1 and b(2) = 3 for k = 1 and b(2) = 2 for k > 1. Here k is a fixed positive integer parameter and n ranges over the positive integers. This recursion, which Golomb describes as “strange”, was suggested to him by Fraenkel [2], who shows that one solution is given by b(n) = ⌊nρ⌋, where ρ is the positive root of the equation

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

In the particular case that k = 1, ρ is equal to τ, the golden ratio which satisfies τ^{2} = 1+τ and τ > 0. The sequence b(n) is called the homogeneous Beatty sequence of ρ. See [3], where a considerably more general recursion that (1) is discussed, based upon iterates of the floor function ⌊nρ⌋ for any algebraic number ρ.

Golomb noted that the solution b(n) of (1) was not unique, but conjectured that “it appears to be the only monotonically increasing solution” [4, p. 14]. In [1], Barbeau and Tanny showed that the recursion (1) with the initial condition b(1) = B for arbitrary positive integer B, has, in fact, many increasing solutions.

Golomb remarks that no finite set of initial conditions is sufficient to specify uniquely the solutions for (1) for any given k. We have seen in [1] that the recursion (1) together with each initial condition specifies an infinite subsequence on which the solution must be increasing, and that any solution to (1) necessarily involves the “piecing together” of these restricted functions. In particular, we showed that it is possible to do so in many ways to generate different increasing solutions to (1).

Recently, an examination of the properties of several of these increasing solutions has revealed that as n grows, all of them come close to the solution above identified by Fraenkel. This inspired a reformulation of (1) using standard dynamical theory of a matrix operator. Based on this approach, in Section 2, we are able to characterize the asymptotic behaviour of all the solutions of (1), including possibly nonincreasing ones (should they exist). Indeed, using this approach, we also determine explicitly an (uncountably) infinite family of increasing solutions to (1), all of which are closely related to Fraenkel’s solution.

It is easy to select a set of initial conditions for (1) so that the solution is initially nonincreasing. However, since each initial condition specifies an infinite subsequence upon which the solution is increasing, it turns out to be more challenging to determine solutions for (1) that are eventually not increasing. In Section 3, we use the matrix dynamics perspective to show that this is possible, where, as in [1], the Fibonacci numbers play a prominent role.

2. Matrix dynamics

For the positive integer u_{1}, let v_{1} = b(u_{1}). Then applying the recursion (1) successively determines two sequences of values {u_{n}}, {v_{n}}, where v_{n} = b(u_{n}) and the pairs (u_{n}, v_{n}) satisfy the linear recursions

\begin{aligned}u_{n+1} & = ku_{n} + v_{n} \\ v_{n+1} & = ku_{n} + 2v_{n} . \end{aligned}  (3)

In [1], we call the sequence {u_{n}} the descendent sequence of the initial argument or “seed” u_{1}. It is easy to see that both {u_{n}} and {v_{n}} are strictly increasing.

The pair of recursions (3) arising from the assignment v_{1} = b(u_{1}) can be written

\binom{u_{n+1}}{v_{n+1}} = ( \begin{matrix}k & 1 \\ k & 2 \end{matrix} ) \binom{u_{n}}{v_{n}} .

The eigenvalues μ and ν for the matrix satisfy the characteristic equation x^{2} − (k + 2)x + k = 0. It is straightforward to check that μ = \frac{1}{2}(k + 2 + \sqrt{k^{2} + 4}) and ν = \frac{1}{2}(k + 2 − \sqrt{k^{2} + 4}). Observe that 0 < ν < 1 < μ. It turns out that, for ρ the positive root of (2), \binom{1}{ρ} is an eigenvector for μ. Thus,

k + ρ = μ

k + 2ρ = μρ

so that μ = \frac{ρ}{ρ−1} = 1 + \frac{1}{ρ−1}, and ρ = \frac{2−k+\sqrt{k^{2}+4}}{2}.

Similarly \binom{1}{ζ} is an eigenvector for ν, where ζ is the negative root of (2), ν = 1 + \frac{1}{ζ−1}, and

ζ = \frac{2 − k − \sqrt{k^{2} + 4}}{2} .

Observe that ζ < 0 < ρ.

Since k < \sqrt{k^{2} + 4} < k + 2, then 2 < 2 − k + \sqrt{k^{2} + 4} < 4, whence 1 < ρ < 2. Suppose that u_{1} and v_{1} = b(u_{1}) are both positive. Then, using the fact that (ρ^{2} − 2ρ) + (kρ − k) = 0, we find that, for n ≥ 1,

ρu_{n+1} − v_{n+1} = ρ(ku_{n} + v_{n}) − (ku_{n} + 2v_{n})
= (kρ − k)u_{n} + (ρ − 2)v_{n} = (2 − ρ)ρu_{n} + (ρ − 2)v_{n}
= (2 − ρ)(ρu_{n} − v_{n}) = (2 − ρ)^{n}(ρu_{1} − v_{1})  (4)

This leads to the following propositions:

Proposition 1. Let u_{1} and v_{1} be positive integers for which v_{1} = b(u_{1}) and define u_{n} and v_{n} by (3). Then

(a) lim_{n→∞} |ρu_{n} − b(u_{n})| = 0 ;

(b) there exists an integer N such that, for n ≥ N,

\begin{aligned}b(u_{n}) & = ⌊ρu_{n} + 0.5⌋ \\ & = \{ \begin{matrix}⌈ρu_{n}⌉ & if v_{1} > ρu_{1}, \\ ⌊ρu_{n}⌋ & if v_{1} < ρu_{1}. \end{matrix} . \end{aligned}

That is, for large n, b(u_{n}) is the nearest integer to ρu_{n}, which turns out to be the ceiling of ρu_{n} if v_{1} > ρu_{1} and the floor of ρu_{n} otherwise.

Proof. Observe that, since 0 < 2 − ρ < 1, (a) holds and ρu_{n} − v_{n} always has the same sign as ρu_{1} − v_{1}. Since, for each n, v_{n} = b(u_{n}) is an integer and since |ρu_{n} − v_{n}| < 0.5 for n sufficiently large, (b) now follows.

Proposition 2. Let 0 ≤ α ≤ 1 and define

B_{k,α}(n) = ⌊nρ + α⌋

where n ∈ N. Then B_{k,α}(n) is a solution of (1). In particular, ⌊nρ⌋ and ⌈nρ⌉ are solutions corresponding to α = 0, 1 respectively.

Proof. Let u_{1} be any positive integer and let v_{1} = B_{k,α}(u_{1}). If u_{2} = B_{k,α}(u_{1})+ ku_{1} = v_{1} + ku_{1} and v_{2} = 2B_{k,α}(u_{1}) + ku_{1} = 2v_{1} + ku_{1}, we have to show that v_{2} = B_{k,α}(u_{2}).

Since u_{1}ρ − (1 − α) ≤ v_{1} ≤ u_{1}ρ + α, it follows that

−(1 − α) ≤ v_{1} − u_{1}ρ ≤ α ,

whence

−(1 − α) < −(2 − ρ)(1 − α) ≤ (2 − ρ)(v_{1} − u_{1}ρ) = v_{2} − u_{2}ρ ≤ (2 − ρ)α < α .

Since u_{1} and v_{1} are integers, then so are u_{2} and v_{2}. Hence v_{2} = ⌊ρu_{2} + α⌋ = B_{k,α}(u_{2}). Thus (1) is satisfied by b = B_{k,α}.

We will denote the solution B_{k,1/2} simply by B_{k}.

Remark. In a similar way, it can be shown that setting b(n) equal to ⌊nρ⌋ for all n or to ⌈nρ⌉ for all n will also yield solutions to (1).

3. Generating sets and non-increasing solutions

The results of the previous section show that there are uncountably many natural increasing solutions to (1). In this section, we use the matrix dynamics perspective developed above to construct a solution b which decreases infinitely often.

We have already noted that b is increasing on the descendants of any single seed. Experimentation shows that we can choose values for finitely many seeds in such a way that b is well-defined (on the union of the descendant sets of the seeds) but not initially increasing. Since Proposition 1 shows that any b constructed in this manner will ultimately be increasing on this domain, we will need to consider infinite sets of seeds in order to find a b that decreases infinitely often.

For an infinite set of seeds, ensuring that b is well-defined is problematic. On the one hand, descendants of any finite set of seeds spread out ever more sparsely among the integers, leaving room to introduce new seeds. But on the other hand, if we have already defined b on a subset S of N, and b remains to be defined at some value u less than a value s in S, then setting b(u) > b(s) may lead to a situation in which u and s have a descendant in common for which b ought to take different values.

To illustrate what might be possible, consider the similar recursion

f(f(n) + n) = f(n) + 4n  (5)

This has an increasing solution given by f(n) = 2n. But there is an additional nonincreasing solution

f(1) = 2 and f(2 × 3^{m} + r) = 8 × 3^{m} − 2r

for m = 0, 1, 2, ⋯ and 0 ≤ r ≤ 4 × 3^{m} − 1.

To check this, note that, if n = 2 × 3^{m} + r and 0 ≤ r ≤ 4 × 3^{m} − 1, then
f(n) + n = 10 × 3^{m} − r = 2 × 3^{m+1} + [4 × 3^{m} − r]

where 1 ≤ 4 × 3^{m} − r ≤ 4 × 3^{m+1} − 1. Hence

\begin{aligned}f(f(n) + n) & = 8 × 3^{m+1} − 2[4 × 3^{m} − r] = 16 × 3^{m} + 2r \\ & = (8 × 3^{m} − 2r) + 4(2 × 3^{n} + r) = f(n) + 4n \end{aligned}

as desired. The following table illustrates what happens:

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ f(n) & 2 & 8 & 6 & 4 & 2 & 24 & 22 & 20 \\ n & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ f(n) & 18 & 16 & 14 & 12 & 10 & 8 & 6 & 4 \\ n & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ f(n) & 2 & 72 & 70 & 68 & 66 & 64 & 62 & 60 \end{matrix}

In particular, f(3^{m}) = 2 × 3^{m} for m ≥ 0.

The recursion (5) provides more room to manoeuvre than Golomb’s recursion, so (1) will require more delicate handling. For a pair \binom{u}{v} of positive integers, let

D_{k}(\binom{u}{v}) = \{ ( \begin{matrix}k & 1 \\ k & 2 \end{matrix} )^{n} \binom{u}{v} : n = 0, 1, 2, ⋯ \} ,

the set of pairs involving u and its descendents, together with their corresponding values under b. For a set S of such pairs of positive integers, let

D_{k}(S) = ∪\{D_{k}(\binom{u}{v}) : \binom{u}{v} ∈ S\} .

Define S to be a generating set for a solution b of the Golomb recursion with parameter k if

b(n) = \{ \begin{matrix}r & if \binom{n}{r} ∈ D_{k}(S) \\ B_{k}(n) & otherwise \end{matrix}  (6)

is well-defined and satisfies (1).

A function b that is well-defined by (6) satisfies (1) for those n for which there exists \binom{n}{r} in D_{k}(S) by the construction of D_{k}(S), and for other n by Proposition 2. It is however possible that (6) may fail to define a function b at some n. This can happen in one of two ways: a generator may be incompatible with the default function B_{k}(n), or two generators may be mutually incompatible with each other.

For example, if k = 1 and ρ = τ, \{\binom{1}{4}\} as a possible generating set is incompatible with the B_{k}(n) in that, since b(2) = B_{1}(2) = 3, b(5) is ill-defined by the conflicting recursions b(5) = b(b(2) + 2) = 2b(2) + 2 = 8 and b(5) = b(b(1) + 1) = 2b(1) + 1 = 9. Note however that this conflict can be resolved by adding \binom{2}{2} to form the generating set \{\binom{1}{4}, \binom{2}{2}\}.

Again with k = 1, we see that the two generators in the set \{\binom{1}{14}, \binom{6}{9}\} are incompatible. Each on its own could constitute a generating set, but together they lead to b(15) being ill-defined by the recursions b(15) = b(b(1) + 1) = 2b(1) + 1 = 29 and b(15) = b(b(6) + 6) = 2b(6) + 6 = 24.

Thus, to check that S is generating, we need to verify the conditions

(i) if \binom{n}{r_{1}} and \binom{n}{r_{2}} belong to D_{k}(S), then r_{1} = r_{2};

(ii) if \binom{n}{r} = ( \begin{matrix}k & 1 \\ k & 2 \end{matrix} ) \binom{x}{y} belongs to D_{k}(S), then either r = B_{k}(n) or y ≠ B_{k}(x).

Since, by Proposition 1, D_{k}(\binom{u}{v}) contains only finitely many pairs \binom{n}{r} for which r ≠ B_{k}(n), it suffices to check (i) and (ii) for a finite number of initial elements of D_{k}(\binom{u}{v}) for each \binom{u}{v} in S.

The following result provides an interesting infinite family of singleton generating sets.

Proposition 3. Consider the case k = 1. Let τ be the golden ratio (i.e., τ > 0 and τ^{2} = τ + 1), let c be one of the integers −1, 0, 1, 2 and let u be any integer exceeding 1 that is not of the form ⌊mτ^{2} +0.5⌋ for an integer m. Then the singleton

\{\binom{u}{⌊τu⌋ + c}\}

is a generating set for a solution of (1).

Proof. Observe that, since k = 1, ρ = τ. There is nothing to check for (i). Let u_{1} = u, v_{1} = ⌊τu⌋ + c, and define u_{n} and v_{n} by (3). Since

|τu − (⌊τu⌋ + c)| < 2 ,

it follows from (4) with ρ = τ and (2 − τ)^{2} < (0.382)^{2} < 0.15, that |τu_{3} − v_{3}| < 0.5 and v_{3} = ⌊τu_{3} + 0.5⌋. Therefore, to check (ii), it suffices to check that \binom{u_{1}}{v_{1}} and \binom{u_{2}}{v_{2}} cannot arise from applying the matrix to a pair \binom{x}{y} with y = B_{k}(x).

If

\binom{u_{1}}{v_{1}} = \binom{u}{⌊τu⌋ + c} = ( \begin{matrix}1 & 1 \\ 1 & 2 \end{matrix} ) \binom{x}{y}

with y = B_{k}(x), then

u = x + ⌊τx + 0.5⌋ = ⌊(τ + 1)x + 0.5⌋ = ⌊τ^{2}x + 0.5⌋ ,

contrary to assumption.

Consider u_{2} = u + ⌊τu⌋ + c and v_{2} = u + 2⌊τu⌋ + 2c. To check (ii), we need show only that

(u − 1) + b(u − 1) < u_{2} < (u + 1) + b(u + 1)

since B_{1}(n) is increasing in n. Now

τ(u − 1) + 0.5 = τu − (τ − 0.5) < τu − 1

so that

\begin{aligned}(u − 1) + b(u − 1) & = (u − 1) + ⌊τ(u − 1) + 0.5⌋ ≤ (u − 1) + ⌊τu⌋ − 1 \\ & = u + ⌊τu⌋ − 2 < u + ⌊τu⌋ + c . \end{aligned}

Also

τ(u + 1) + 0.5 = τu + (τ + 0.5) > τu + 2

so that

\begin{aligned}(u + 1) + b(u + 1) & = (u + 1) + ⌊τ(u + 1) + 0.5⌋ ≥ u + 1 + ⌊τu⌋ + 2 \\ & = u + ⌊τu⌋ + 3 > u + ⌊τu⌋ + c . \end{aligned}

The result follows.

We now apply the generating set idea to construct a solution of (1) in the case k = 1 which is not eventually increasing. In this case, as we remarked above, the generating set for the solution must be infinite.

Proposition 4. Let F_{n} be the nth Fibonacci number, with F_{1} = F_{2} = 1 and F_{n+1} = F_{n} + F_{n−1} for n ≥ 2. Then, for the case k = 1,

\{\binom{F_{2n+1} + 1}{F_{2n+2} − 2} : n = 1, 2, ⋯ \}

is a generating set.

Proof. Observe that

D_{1}(\{\binom{F_{2n+1} + 1}{F_{2n+2} − 2}\})

= \{\binom{F_{2n+1} + 1}{F_{2n+2} − 2}, \binom{F_{2n+3} − 1}{F_{2n+4} − 3}, \binom{F_{2n+5} − 4}{F_{2n+6} − 7}, \binom{F_{2n+7} − 11}{F_{2n+8} − 18}, ⋯ \} .

We first establish that each entry beyond the third has the form \binom{u}{v} with v = B_{1}(u), so that conditions (i) and (ii) have to be checked only for the first three terms.

Observe that, for each positive integer n,

τF_{2n+1} − F_{2n+2} = τ(F_{2n} + F_{2n−1}) − (2F_{2n} + F_{2n−1})

= (τ − 1)F_{2n−1} − (2 − τ)F_{2n} = (τ − 1)τ^{−1}(τF_{2n−1} − F_{2n})

= (τ − 1)^{n}τ^{−n}(τF_{1} − F_{2}) = (τ − 1)^{n+1}τ^{−n} = τ^{−(2n+1)}

so that 0 < τF_{2n+1} − F_{2n+2} < 0.25 for n ≥ 1. Hence

|τ(F_{2n+1} + 1) − (F_{2n+2} − 2)| ≤ 0.25 + τ + 2 < 4 < [2(2 − τ)^{3}]^{−1}

so that, from (3), |τu − v| < 0.5 for each entry \binom{u}{v} beyond the third.

Since

\begin{aligned}D_{1}(\{\binom{F_{3} + 1}{F_{4} − 2}\}) & = \{\binom{3}{1}, \binom{4}{5}, \binom{9}{14}, ⋯ \} \\ D_{1}(\{\binom{F_{5} + 1}{F_{6} − 2}\}) & = \{\binom{6}{6}, \binom{12}{18}, \binom{30}{48}, ⋯ \} , \end{aligned}

and F_{k+2} − F_{k} ≥ 6 for k ≥ 5, it can be seen that condition (i) is satisfied.

To check condition (ii), we must show that for each positive integer n, F_{2n+1}+1, F_{2n+3} − 1 and F_{2n+5} − 4 cannot be of the form x + B_{1}(x) for any integer x. Now

F_{2n} = ⌊τF_{2n−1} + 0.5⌋,

so that F_{2n+1} = F_{2n−1} + B_{1}(F_{2n−1}). Since τ > 1, B_{1}(n) is strictly increasing in n, so that (F_{2n−1} + 1) + B_{1}(F_{2n−1} + 1) ≥ F_{2n+1} + 2. Thus, F_{2n+1} + 1 cannot have the form x + B_{1}(x). Similarly, F_{2n+3} − 1 cannot have this form.

Finally

F_{2n+5} − 4 = (F_{2n+4} + F_{2n+3}) − 4 < (τ + 1)F_{2n+3} − 4
= (τ + 1)(F_{2n+3} − 1) − (3 − τ) < (F_{2n+3} − 1) + τ(F_{2n+3} − 1) − 1
< (F_{2n+3} − 1) + B_{1}(F_{2n+3} − 1)

and

F_{2n+5} − 4 = F_{2n+4} + F_{2n+3} − 4 = (τ + 1)F_{2n+3} − τ^{−(2n+3)} − 4
= (τ + 1)(F_{2n+3} − 2) + 2τ − τ^{−(2n+3)} − 2
> (F_{2n+3} − 2) + τ(F_{2n+3} − 2) + 1
> (F_{2n+3} − 2) + B_{1}(F_{2n+3} − 2) .

Since B_{1}(n) is strictly increasing, F_{2n+5} − 4 cannot be of the form x + B_{k}(x).

Notice that, since b(F_{2n+1}) = F_{2n+2} > F_{2n+2} − 2 = b(F_{2n+1} + 1), the solution obtained with this generating set decreases infinitely often, as required.

For k > 1, we believe that a similar approach will lead to a solution to (1) which is not eventually increasing.

4. Concluding remarks

The matrix dynamics approach described in Section 2 can be applied to the more general recursion

f(af(n) + bn) = cf(n) + dn

with integer coefficients a, b, c and d (the Golomb recursion has a = 1, b = d = k and c = 2). Once again, a given value v_{1} = f(u_{1}) imposes other values v_{n} = f(u_{n}) where \binom{u_{n}}{v_{n}} satisfies the recursion

\binom{u_{n+1}}{v_{n+1}} = ( \begin{matrix}b & a \\ d & c \end{matrix} ) \binom{u_{n}}{v_{n}} .

The transition matrix will have eigenvector(s) \binom{1}{ρ} where ρ satisfies aρ^{2}+(b−c)ρ−d = 0 and f(n) = ρn satisfies the recursion. If 0 < c − aρ < 1, then the analogues of Propositions 1 and 2 hold. Otherwise, depending on the signs and magnitudes of a, b, c, d and ρ, a variety of behaviours are possible, as illustrated for example by recursion (5). The tools developed for the Golomb recursion can be readily adapted to analyze these situations, and it is not illuminating to simply go through the cases in general.

Alternatively, one could introduce higher orders of recursion, such as occur in equations of the type

f(a_{0}n + a_{1}f(n) + a_{2}f(f(n))) = b_{0}n + b_{1}f(n) + b_{2}f(f(n)) .

The matrix dynamics procedure suggests considering triples (u_{n}, v_{n}, w_{n}) with v_{n} = f(u_{n}) and w_{n} = f(v_{n}) = f(f(u_{n})), so that

f(a_{0}u_{n} + a_{1}v_{n} + a_{2}w_{n}) = b_{0}u_{n} + b_{1}v_{n} + b_{2}w_{n} .

While we can define u_{n+1} = a_{0}u_{n} +a_{1}v_{n} +a_{2}w_{n} and v_{n+1} = b_{0}u_{n} +b_{1}v_{n} +b_{2}w_{n}, we would need further information on the type of recursion to sensibly define w_{n+1} and utilize our techniques. Such information might be available in a specific context, but it is beyond the scope of this paper to explore the hypothetical possibilities.

References

[1] E. Barbeau and S. Tanny, On a strange recursion of Golomb, Electronic J. of Combinatorics 3 (1996), R8.

[2] A. Fraenkel, private communication to Golomb, 1983.

[3] A. Fraenkel, Iterated floor function, algebraic numbers, discrete chaos, Beatty subsequences, semigroups, Transactions of the American Mathematical Society 341 (2), February 1994.

[4] S. W. Golomb, Discrete chaos: sequences satisfying “strange” recursions, preprint (undated, likely late 80s or early 90s).