Fibonacci notes

Peter J. Cameron and Dima G. Fon-Der-Flaass

Abstract

These notes put on record part of the contents of a conversation the first author had with John Conway in November 1996, concerning some remarkable properties of the Fibonacci numbers discovered by Clark Kimberling [2] and by Conway himself. Some of these properties are special cases of much more general results, while others are specific to the Fibonacci sequence; some are proved, while others are merely observation (as far as we know). The first four sections are purely expository. The last two sections on numeration systems are the work of the second author. We am grateful to members of the Combinatorics Study Group at QMW, especially Julian Gilbey, for discussions and help with the details.

1 Fibonacci numbers

The Fibonacci number F_{n}, for positive integer n, can be defined as the number of ways of writing n as the sum of a sequence of terms, each equal to 1 or 2. So, for example, 4 can be expressed in any of the forms

2 + 2 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 1 + 1 + 1 + 1,

so F_{4} = 5.

The most important property of the Fibonacci numbers is that they satisfy the recurrence relation

F_{n} = F_{n−1} + F_{n−2}

for n ≥ 3. For consider all the sequences of 1s and 2s with sum n. Divide the sequences into two classes according to whether the last term is 1 or 2. There are F_{n−1} sequences in the first class, since the terms except the last sum to n − 1. Similarly, there are F_{n−2} sequences in the second class. Since the classes don’t overlap, and every sequence lies in one of them, the recurrence relation follows.

This recurrence, together with the initial values F_{1} = 1 and F_{2} = 2, determines F_{n} for all n.

We can extend the definition of F_{n} to n = 0 in a natural way: the empty sequence is the only one with sum 0, so F_{0} = 1. It is possible to define F_{n} for negative n so that the recurrence is satisfied, but there is no natural counting interpretation of these numbers.

Standard arguments give the formula

F_{n} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{n+1} − (\frac{1 − \sqrt{5}}{2})^{n+1}) .

Since α = (1+\sqrt{5})/2 = 1.618 … > 1 and β = (1−\sqrt{5})/2 = −0.618 … > −1, we see that F_{n} is the nearest integer to (1/\sqrt{5})((1 + \sqrt{5})/2)^{n+1}. In particular, F_{n+1}/F_{n} tends to the limit (1 + \sqrt{5})/2 as n → ∞.

Note that α − 1 = −β is the golden ratio τ, the point of division of a unit interval with the property that the ratio of the larger part to the whole is equal to the ratio of the smaller part to the larger.

2 The Fibonacci successor function

In this section we define a function on the positive integers which has the property that it maps each Fibonacci number to the next. It depends on the following property of Fibonacci numbers:

Theorem 2.1 Every positive integer n has a unique expression in the form

n = F_{i_{1}} + F_{i_{2}} + ⋯ + F_{i_{k}},

where i_{j+1} ≥ i_{j} + 2 for j = 1, …, k − 1; in other words, as the sum of a set of Fibonacci numbers with no two consecutive.

We call the expression in the theorem the Fibonacci representation of n. To prove this, we use a simple fact about Fibonacci numbers, easily

demonstrated by induction:

Lemma 2.2 The sum of alternate Fibonacci numbers ending with F_{k} is F_{k+1} − 1.

Proof The inductive step goes from k to k + 2: if we assume the result for k, and add F_{k+2} to both sides of the equation, then on the right we obtain F_{k+3} − 1. So it is necessary to start the induction separately for odd and even k, by observing that F_{1} = F_{2} − 1 and F_{2} = F_{3} − 1.

Now given an integer n, let F_{k} be the largest Fibonacci number not exceeding n. Then any representation of n as the sum of Fibonacci numbers with no two consecutive must include F_{k}, since by the Lemma if we omit F_{k} the greatest we can get is F_{k} − 1. Now, by induction, n − F_{k} has a unique Fibonacci representation; and this representation cannot include F_{k−1}, since n < F_{k+1} = F_{k} + F_{k−1}. So we have constructed the unique Fibonacci representation of n.

Now we define the Fibonacci successor function σ as follows: if

n = F_{i_{1}} + F_{i_{2}} + ⋯ + F_{i_{k}}

is the Fibonacci representation of n, then

σ(n) = F_{i_{1}+1} + F_{i_{2}+1} + ⋯ + F_{i_{k}+1}.

Note that σ(F_{k}) = F_{k+1}, and that m is the Fibonacci successor of some (unique) positive integer if and only if F_{1} does not occur in the Fibonacci representation of m.

Note also that n + σ(n) = σ^{2}(n) for any n, where σ^{2}(n) denotes σ(σ(n)). So, in order to apply the successor function repeatedly, we only have to apply it once and then use the Fibonacci recurrence relation.

We call the positive integer n a Fibonaacci successor if n = σ(m) for some m. This holds if and only if the Fibonacci representation of n does not contain F_{1}.

We oserved in the last section that each Fibonacci number is approximately α times the preceding one, where α = (1 + \sqrt{5})/2. The convergence is exponentially rapid. A small amount of analysis of geometric progressions in fact shows the following. Given a positive integer n, let ρ(n) be the integer nearest to nα.

Theorem 2.3 For any positive integer n, either σ(n) = ρ(n), or σ(n) = ρ(n) + 1. The first alternative holds if n is a Fibonacci successor.

We can extend the domain of the Fibonacci successor function to include zero, in a natural way. Since the Fibonacci representation of zero is empty, we take σ(0) = 0.

3 The table

We consider the following table. (Ignore for the moment the two columns at the left.)

\begin{matrix}0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & … \\ 1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 & 76 & 123 & … \\ 2 & 4 & 6 & 10 & 16 & 26 & 42 & 68 & 110 & 178 & … \\ 3 & 6 & 9 & 15 & 24 & 39 & 63 & 102 & 165 & 267 & … \\ 4 & 8 & 12 & 20 & 32 & 52 & 84 & 136 & 220 & 356 & … \\ 5 & 9 & 14 & 23 & 37 & 60 & 97 & 157 & 254 & 411 & … \\ 6 & 11 & 17 & 28 & 45 & 73 & 118 & 191 & 309 & 500 & … \\ 7 & 12 & 19 & 31 & 50 & 81 & 131 & 212 & 343 & 555 & … \\ 8 & 14 & 22 & 36 & 58 & 94 & 152 & 246 & 398 & 644 & … \\ 9 & 16 & 25 & 41 & 66 & 107 & 173 & 280 & 453 & 733 & … \\ 10 & 17 & 27 & 44 & 71 & 115 & 186 & 301 & 487 & 788 & … \end{matrix}

The table is constructed as follows. The first row contains the Fibonacci numbers. As we already saw, these are produced by starting with 1 and applying the Fibonacci successor function repeatedly.

The first element in the next row is the smallest number which has not been encountered previously (which happens to be 4). Then we apply the successor function repeatedly to it to generate the row. As we also saw, we only need to apply the successor function once:

4 = 1 + 3 = F_{1} + F_{3},

so

σ(4) = F_{2} + F_{4} = 2 + 5 = 7.

Then the remaining elements can be found from the Fibonacci recurrence relation: next is 7 + 4 = 11, then 11 + 7 = 18, and so on.

Now we repeat this for each succeeding row: the first entry is the smallest number not used in the table so far, and the rest of its row is obtained by applying the successor function repeatedly (or by applying the successor function once and then the recurrence relation).

Clearly the first element in any row is not itself the Fibonacci successor of anything. So the first elements in the rows are the numbers whose Fibonacci representations include F_{1}, arranged in order. We see that every positive integer occurs exactly once in the table: the integer

n = F_{i_{1}} + F_{i_{2}} + ⋯ + F_{i_{k}}

occurs in column i_{1} of the row with first element

m = F_{1} + F_{i_{2}−i_{1}+1} + ⋯ + F_{i_{k}−i_{1}+1}.

Let T_{i,j} denote the entry in row i and column j of the table. (For technical reasons, we take the first row to have number 0). Various remarkable properties hold: we now give some of these.

Theorem 3.1 Let a_{1} and a_{2} be positive integers, and define a sequence (a_{n}) by the Fibonacci recurrence: that is, a_{n+2} = a_{n} + a_{n+1} for n ≥ 1. Then there exist k, l, m such that a_{m+n} = T_{k,l+n} for all n ≥ 0. In other words, every sequence generated by the Fibonacci recurrence occurs, from some point on, in the table.

Proof It is enough to show that a_{n+1} = σ(a_{n}) for some n: for the number a_{n} occurs in the table (by our previous remark) and the given sequence agrees with that row from that point on.

Now the solution to any Fibonacci recurrence is given by

a_{n} = Aα^{n} + Bβ^{n}

for some A and B, where α and β are as in Section 1. Since |β| < 1, for sufficiently large n we see that a_{n+1} = ρ(a_{n}), the nearest integer to a_{n}α. So, by Theorem 2.3, it is enough to find a sufficiently large n such that a_{n} is a Fibonacci successor.

Suppose that a_{n} is not a Fibonacci successor, say

a_{n} = F_{1} + F_{k} + ⋯,

with k ≥ 3. Then by Theorem 2.3, we have

a_{n+1} = ρ(a_{n}) = σ(a_{n}) − 1 = F_{1} + F_{k+1} + · · · .

But then

a_{n+2} = a_{n} + a_{n+1} = F_{2} + F_{k+2} + ⋯

is a Fibonacci suuccessor, as required.

Remark If two sequences satisfying the Fibonacci recurrence agree from some point on, then (by extrapolting back) they agree throughout their entire ength. So, in Theorem 3.1, we may assume that either l or m is equal to 1.

Let r_{n} be the number of the row containing the positive integer n. The sequence (r_{n}) begins

0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, …

The lengths of the gaps between successive zeros are Fibonacci numbers (starting with F_{0} = 1). The numbers in the gap of length F_{k} are a permutation π_{k} of {1, 2, …, F_{k} − 1}, and the permutation π_{k+1} is obtained from π_{k} by inserting the additional numbers in appropriate gaps.

We can imagine that the table is extrapolated backwards using the recurrence: that is, T_{i,0} = T_{i,2} − T_{i,1} and T_{i,−1} = T_{i,1} − T_{i,0} for all i ≥ 0.

Theorem 3.2 We have T_{i,−1} = i and T_{i,0} = σ(i) + 1. Moreover, T_{i,1} = σ(T_{i,0}) − 1.

Proof The function σ is strictly monotonic, and the entries in column 1 of the table are (by construction) increasing. So the numbers

σ^{−1}(σ^{−1}(T_{i,1} + 1) − 1)

are strictly increasing. So it suffices to prove that every non-negative integer n can be expressed in the form

n = σ^{−1}(σ^{−1}(m + 1) − 1)

for some m which is not a Fibonacci successor, and that, conversely, if m is not a Fibonacci successor, then it can be written in the form

m = σ(σ(n) + 1) − 1

for some n.

For the first, take any n and write its Fibonacci representation. There are two cases. If F_{1} occurs (that is, n is not a Fibonacci successor), then, say,

n = F_{1} + ⋯ + F_{2l−1} + F_{k} + ⋯,

with k > 2l + 1. Then

σ(n) + 1 = F_{2l+1} + F_{k+1} + ⋯,

whence

σ(σ(n) + 1) − 1 = F_{1} + ⋯ + F_{2l+1} + F_{k+2} + ⋯,

which is not a Fibonacci successor. On the other hand, if F_{1} does not occur in the representation of n, then say

n = F_{2} + ⋯ + F_{2l} + F_{k} + ⋯,

with k ≥ 2l + 2 (and possibly l = 0). Then

σ(n) + 1 = F_{1} + F_{3} + ⋯ + F_{2l+1} + F_{k+1} = ⋯,

and

σ(σ(n) + 1) − 1) = F_{1} + F_{4} + ⋯ + F_{2l+2} + F_{k+2} + ⋯,

which again is not a Fibonacci successor.

For the converse, suppose that

m = F_{1} + F_{3} + ⋯ + F_{2l+1} + F_{k} = ⋯,

where k > 2l + 3. Then

m + 1 = F_{2l+2} + F_{k} + ⋯,

so that

σ^{−1}(m + 1) = F_{2l+1} + F_{k−1} + · · · .

Then

σ^{−1}(m + 1) − 1 = F_{2} + ⋯ + F_{2l} + F_{k−1} + ⋯,

and so

σ^{−1}(σ^{−1}(m + 1) − 1) = F_{1} + ⋯ + F_{2l−1} + F_{k} = · · · .

(It is possible that the initial terms F_{1} + ⋯ + F_{2l−1} are absent, if l = 0.)

So the entries in column −1 conveniently label the rows by non-negative integers.

4 Phyllotaxis

Fibonacci numbers, and the golden ratio, are popularly associated with the growth of plants. In order that the leaves of a growing plant should not shade the leaves below them, each new leaf should grow so as to make an angle of τ of a circle with the previous one, where τ = (\sqrt{5} − 1)/2 is the golden ratio. See the discussion in Coxeter [1], Chapter 11.

Let us consider the leaves on such an idealised plant. Suppose that the stem has unit circumference, and that leaf number zero grows at the reference point 0. Then the position of leaf number n is at {nτ} = nτ − ⌊nτ⌋, the fractional part of nτ. When it emerges, the circle is already divided into n intervals by the existing leaves. Suppose that there are a_{n} intervals between the zeroth and the nth leaf when it emerges, and b_{n} intervals between the nth leaf and the zeroth. (Thus a_{n} + b_{n} = n + 1.) What can be said about the ordered pairs (a_{n}, b_{n})?

It is known that the ratio of consecutive Fibonacci numbers is a close approximation to the golden ratio. More precisely,

lim_{k→∞} F_{k}/F_{k+1} = τ,

and the ratio F_{k}/F_{k+1} is a better approximation to τ than any rational with smaller denominator; moreover, the ratio is alternately greater and less than its limit. Thus, when leaf number n = F_{k+1} emerges, we have either a_{n} = 1 (if k is odd) or b_{n} = 1 (if k is even). Thus,

If n = F_{k+1} then (a_{n}, b_{n}) = \{ \begin{matrix}(1, n) & if k is odd, \\ (n, 1) & if k is even. \end{matrix}

Moreover, the Fibonacci numbers are the only numbers with this property: that is, if n is not a Fibonacci number then a_{n}, b_{n} > 1.

We find the following values:

\begin{matrix}n & a_{n} & b_{n} \\ 1 & 1 & 1 \\ 2 & 1 & 2 \\ 3 & 3 & 1 \\ 4 & 2 & 3 \\ 5 & 1 & 5 \\ 6 & 5 & 2 \\ 7 & 3 & 5 \\ 8 & 8 & 1 \\ 9 & 5 & 5 \\ 10 & 2 & 9 \\ 11 & 9 & 3 \\ 12 & 5 & 8 \\ 13 & 1 & 13 \\ 14 & 10 & 5 \\ 15 & 5 & 11 \\ 16 & 15 & 2 \\ 17 & 9 & 9 \\ 18 & 3 & 16 \\ 19 & 15 & 5 \\ 20 & 8 & 13 \\ 21 & 21 & 1 \\ 22 & 13 & 10 \\ 23 & 5 & 19 \\ 24 & 20 & 5 \\ 25 & 11 & 15 \end{matrix}

Now observe what happens as n runs along a row of our master table. We already noted that, if n runs through the Fibonacci numbers, then one of a_{n} and b_{n} is equal to 1, and this number bounces from side to side. Empirically, something similar happens for any row, except that the ‘bouncing number’ is not 1 for any other row. In fact, the values of the bouncing number t are as shown in the following table:

\begin{matrix}n & t \\ 0 & 1 \\ 1 & 3 \\ 2 & 2 \\ 3 & 5 \\ 4 & 8 \\ 5 & 5 \\ 6 & 9 \\ 7 & 5 \\ 8 & 10 \\ 9 & 15 \\ 10 & 9 \end{matrix}

The bouncing number seems to be often but not always a Fibonacci number. We do not know how to explain these patterns!

5 Recurrent numeration systems

This section gives a wide generalisation of the table of sequences satisfying the Fibonacci relation.

We let ℕ denote the natural numbers, starting at zero, and ℕ^{+} = ℕ \ {0} the positive integers. Also, P is the set of all nonempty finite subsets of N ordered lexicographically. We shall often identify elements of P with finite binary words: every set X ∈ P is identified with the word ε_{m} … ε_{0} where m = max X, and ε_{i} = 1 whenever i ∈ X. Thus the words corresponding to elements of P always begin with 1.

By a general numeration system (NS) we mean any infinite subset S ⊆ P together with the uniquely determined order-preserving bijection n : S → ℕ^{+}.

We now give some examples.

Example 1. The most trivial example: S is the collection of all one-element sets. Then every positive integer n is the image of the word B_{n} = 10 … 0 (n zeros).

Example 2 The most common example: the binary system. S = P, all non-empty finite sets. The positive integer n is the image of its own base 2 representation.

Example 3 The example which has motivated this section: the Fibonacci numbering system. S is the collection of all finite sets containing no two consecutive numbers.

A numeration system (S, n) is called based if there exists a base sequence B(S) = (b_{0}, b_{1}, …) of positive natural numbers such that

n(X) = ∑_{i∈X} b_{i}

for every X ∈ S.

In Example 1, the base sequence is just the sequence of natural numbers 1, 2, . . .. In Example 2, it is the sequence of powers of 2, while in Example 3, it is the Fibonacci sequence (this follows from the Fibonacci representation in Section 2).

A NS (S, n) is called tree-like if it satisfies the following three properties (here we look at S as a set of binary words):

(T1) 1 ∈ S;

(T2) if w ∈ S then w0 ∈ S;

(T3) every nonempty initial segment of w ∈ S belongs to S.

The set S with the set of arcs (w, wε), ε ∈ {0, 1}, forms a directed tree rooted at the vertex 1. Label every arc (w, wε) by ε. Now, if we add another vertex 0, and an arc (0, 1) labelled by 1, we get a rooted tree T (S), and every element of S is the sequence of labels on some path beginning at 0. Every vertex w ≠ 0 has outdegree 1 or 2, and the outgoing arcs are labelled by 0, or by 0 and 1. If we start at 0 and choose an arc with label 1 whenever possible, we get

Lemma 5.1 Let S be a tree-like NS. There exists an infinite binary sequence M = M(S) = m_{1}m_{2}m_{3} …, m_{1} = 1, the maximal sequence of S, such that every its initial segment M_{k} = m_{1} … m_{k} is the lexicographically maximal k-digit word in S.

The arcs labelled by 0 determine a partition of S into infinite sequences C_{0}, C_{1}, … numbered in the increasing order of their initial elements. Let C_{i} = (v_{i1}, v_{i2}, …). Then the numbers c_{ij} = n(v_{ij}) form the table of the NS (S, n).

Our three examples are tree-like.

In Example 1, we have M = 1000 …, and (b_{i}) = (1, 2, 3, 4, …). The table is a single row (1, 2, 3, 4, …). In Example 2, M = 1111 …; and b_{i} = 2^{i}. Entries of the table are c_{ij} = (2i + 1)2^{j−1}, for i ≥ 0, j ≥ 1: that is, the rows start with the odd numbers, and each entry is double the one to its left.

In Example 3, the base sequence (b_{i}) = (1, 2, 3, 5, 8, …) is the Fibonacci sequence: b_{0} = 1, b_{1} = 2, b_{n} = b_{n−1} + b_{n−2}. Finally, M = 101010 . . .. The table is the one given in Section 3.

In the other direction, a numeration system can be constructed as follows. Take any infinite binary sequence M = m_{1}m_{2} … beginning with m_{1} = 1;

for i = 0, 1, … let M_{i} be its initial segment of length i, and define M′_{i} = M_{i−1}0 for those i > 0 for which m_{i} = 1;

Let S be the set of words w which begin with 1 and can be represented in the form w = v′_{1} … v′_{s}v, s ≥ 0, where v′_{i} are some words M′_{j}, and v is one of M_{i} (if it exists, such representation is unique). We have M = M(S) (cf. Lemma 5.1).

The base sequence of S is defined recursively by b_{0} = 1 and

b_{n} = m_{1}b_{n−1} + m_{2}b_{n−2} + … + m_{n}b_{0} + 1.  (1)

And now, at last, the first non-trivial result of this section.

Theorem 5.2 Every numeration system which is both tree-like and based is constructed by the above recipe from an infinite binary sequence M.

Conversely, every set S so constructed is a tree-like based numeration system.

Proof The theorem immediately follows from three claims:

(1) If S is a based tree-like NS (for short, BTNS) with M = M(S) as in Lemma 5.1 then its base sequence is given by the formula (1).

(2) There exists at most one BTNS with any given base sequence.

(3) The system S defined in the theorem is a BTNS with the base sequence given by (1).

Proof of (1) The minimal word in S is 1: this implies that b_{0} = 1. For every k ≥ 1, the maximal k-letter word in S is M_{k}, by Lemma 5.1; and the minimal (k + 1)-letter word is B_{k} = 100 … 0 (k zeros). We have n(B_{k}) − n(M_{k}) = 1 which is equivalent to (1).

Proof of (2) We shall show by induction that the sets S_{k} of words of length k in S are determined uniquely; this is true for k = 1 (S_{1} = {1}). Given S_{k}, the set S_{k+1} consists of all words w0 for w ∈ S_{k} and, possibly, some of the words w1. Let w′ be the immediate successor of w in S_{k}, or w′ = B_{k} when w is maximal in S_{k}. We see that the word w1 is in S_{k+1} if and only if n(w′0) − n(w0) = 2, and thus the set S_{k+1} is uniquely determined. Note that if n(w′0) − n(w0) is less than 1 or greater than 2 then the BTNS does not exist.

Proof of (3) Let S be the system defined in the theorem. We shall need three properties of S which easily follow from the definition.

(a) If w1 ∈ S for some non-empty word w then w0 ∈ S, and in the decomposition w0 = v′_{1} … v′_{s}v the word v is empty.

(b) For each k ≥ 1, the word M_{k} is the maximal word of length k in S.

(c) For w ∈ S, the decomposition w = v′_{1} … v′_{s}v can be found in one pass from left to right, without backtracking and/or looking ahead.

Now, take an arbitrary word x ∈ S of length ≥ 2. We shall find the word y ∈ S immediately preceding x in the lexicographic order, and check that n(x) − n(y) = 1 — this will suffice to prove the claim.

If x = x′1 then by (a) we have x′0 ∈ S, therefore y = x′0 and n(x)−n(y) = 1, as required.

Let x = x′10 … 0, with k ≥ 1 zeros at the end. If x′ is empty then (b) implies that y = M_{k}, and n(x)−n(y) = 1 from the recurrence (1). Otherwise we can apply the property (a) to the word x′1 ∈ S to obtain that the word x′0 is in S, and that in its decomposition x′0 = v′_{1} … v′_{s}v the tail v is empty. Therefore, appending to x′0 any word from S results again in a word from S, and by (c) all words from S beginning with x′0 can be obtained in this way. So, again by (b), we have y = x′0M_{k}. Again the recurrence (1) implies that n(x) − n(y) = 1. So, the claim, and the theorem, are proved.

Our three examples have two features in common: first, that the sequence M is periodic; second, that the numbers (b_{i}) satisfy some linear recurrence. The following theorem shows that these two properties are equivalent.

Theorem 5.3 Let S be a BTNS. Then its base sequence B(S) satisfies some linear recurrence if and only if its maximal sequence M(S) is periodic. If M(S) has a period of length p after an initial segment of length l then there exists a linear recurrence for B(S) of degree at most p + l with integer coefficients.

Proof Let B(S) = (b_{0}, b_{1}, …), M(S) = m_{1}m_{2} . . .. Take any real numbers a_{1}, …, a_{k}. For i = 1, …, k define

x_{i} = b_{k−i} − ∑_{j=1}^{k−i} a_{j}b_{k−i−j}.  (2)

In particular, we have x_{k} = b_{0} = 1. Let also

d = a_{1} + … + a_{k} − 1.  (3)

Equation (1) implies that, for any n ≥ 0,

b_{n+k} − a_{1}b_{n+k−1} − a_{2}b_{n+k−2} − … − a_{k}b_{n} =
= (1 + ∑_{i=1}^{n+k} m_{i}b_{n+k−i}) −

−a_{1}(1 + ∑_{i=1}^{n+k−1} m_{i}b_{n+k−1−i}) − … − a_{k}(1 + ∑_{i=1}^{n} m_{i}b_{n−i})

= ∑_{i=1}^{n} m_{i}(b_{n+k−i} − a_{1}b_{n+k−i−1} − … − a_{k}b_{n−i}) +

+m_{n+1}x_{1} + … + m_{n+k}x_{k} − d.

It follows that B(S) satisfies the recurrence b_{n+k} = a_{1}b_{n+k−1} + … + a_{k}b_{n} if and only if for every subword (m_{n+1} … m_{n+k}) of M(S) we have

m_{n+1}x_{1} + … + m_{n+k}x_{k} = d.  (4)

If (4) holds then m_{n+k} is uniquely determined by m_{n+1}, …, m_{n+k−1}. As there are only finitely many binary words of length k −1, the sequence M(S) is periodic.

Conversely, let M(S) be periodic with period of length p after an initial sequence of length l. Take k = l + p. We can easily satisfy the equations (4) by taking x_{1} = … = x_{l} = 0, x_{l+1} = … = x_{l+p} = 1, and d equal to the number of ones in the period. Then from the equations (2) we can successively determine the numbers a_{1}, …, a_{k−1}:

a_{k−i} = b_{k−i} − x_{i} − ∑_{j=1}^{k−i−1} a_{j}b_{k−i−j}.

Finally, from the equation (3) we can find a_{k}. The theorem is proved.

When M(S) is purely periodic with period of length p, the recurrence for B(S) is especially simple: we can take

a_{1} = m_{1}, a_{2} = m_{2}, …, a_{p−1} = m_{p−1}, a_{p} = m_{p} + 1.

l + p is not necessarily the lowest possible degree of the recurrence; an interesting question is: how long can the period of M(S) be if B(S) satisfies a recurrence of degree k?

6 Complete tables

The most interesting property of the Fibonacci table is its completeness: it contains all sequences satisfying Fibonacci recurrence (Theorem 3.1). In this section we shall give another, purely combinatorial proof of this fact, and at the same time we shall find infinitely many other recurrences having the same nice property.

Definition 6.1 Let S be a BTNS whose base sequence B = (b_{0}, b_{1}, b_{2}, …) satisfies the recurrence

b_{n+k} = a_{1}b_{n+k−1} + … + a_{k}b_{n}.  (5)

The system S is complete if every sequence of positive integers satisfying this recurrence occurs, from some point on, in the successor table of S.

One way to demonstrate that a certain S is complete is the following: to prove that every sequence of natural numbers satisfying (5) is a linear combination with positive integer coefficients of some successor sequences (for instance, of some shifts of the base sequence); and then to prove that every such linear combination is a successor sequence from some point on. Note that the base sequence always coincides with the first row of the successor table.

Let us do this for the BTNS with the maximal sequence M(S) = (11 … 10)^{∗} (k −1 ones). The system S consists of all binary words not containing k consecutive ones; its base sequence satisfies the recurrence

b_{n+k} = b_{n+k−1} + … + b_{n}  (6)

with the initial values b_{i} = 2^{i} for i = 0, 1, …, k − 1. Going backwards, we find:

b_{−1} = 1, b_{−2} = … = b_{−k} = 0, b_{−(k+1)} = 1.

Thus, the sequences satisfying (6) and beginning with k-tuples

b^{(0)} = (1, 0, 0, …, 0, 0)
b^{(1)} = (0, 1, 1, 2, …, 2^{k−3})
…
b^{(k−3)} = (0, …, 0, 1, 1, 2)
b^{(k−2)} = (0, 0, …, 0, 1, 1)
b^{(k−1)} = (0, 0, …, 0, 0, 1)

are shifts of the base sequence.

The vectors b^{(0)}, b^{(1)}, …, b^{(k−1)} form a basis of the k-dimensional row space. One easily finds that

(a_{0}, …, a_{k−1}) = a_{0}b^{(0)} + a_{1}b^{(1)} + (a_{2} − a_{1})b^{(2)} + (a_{3} − a_{2} − a_{1})b^{(3)}
+ … + (a_{k−1} − a_{k−2} − … − a_{1})b^{(k−1)}.

Thus, if (x_{n})_{n≥0} is any sequence of natural numbers satisfying (6) then the k-tuple (x_{k}, x_{k+1}, …, x_{2k−1}) is a linear combination of b^{(0)}, …, b^{(k−1)} with integer non-negative coefficients; and we have fulfilled the first part of our plan.

For the second part, we introduce the following game. Fix a natural number k ≥ 2. On the doubly infinite strip of squares indexed by integers are placed finitely many pebbles (possibly, more than one pebble in a square). One is allowed to make moves of two kinds.

1. If there are k consecutive non-empty squares, say n, n+1, …, n+k −1 then one can remove one pebble from each of them, and add one pebble to the square n + k.

2. If a square n contains two or more pebbles then one can remove from it two pebbles, and add to the squares n − k and n + 1 one pebble each.

Lemma 6.2 The game described above always terminates; and the final position depends only on the initial position, and not on the sequence of moves.

Proof Let (w_{i})_{i∈ℤ} be any sequence of real numbers satisfying the recurrence (6). Every position in the game is determined by the sequence (a_{i}) of nonnegative integers, all but finitely many of which are equal to 0. The weight of the position A = (a_{i}) is defined as

w(A) = ∑ w_{i}a_{i}.

The rules of the game are chosen so that legal moves don’t change the weight of the position. Also, they don’t increase the number of pebbles.

Now, let α be the positive root of the equation

x^{k} = x^{k−1} + x^{k−2} + … + x + 1.

We have 1 < α < 2. Let w_{i} = α^{i}; obviously, this sequence satisfies (6).

First we shall prove by induction on the number of pebbles that the game eventually stops. Consider the maximal index of a pebble in the position. It does not decrease, but it cannot increase indefinitely (the weight of the position is bounded) — therefore, from some moment on, the pebble with the maximal index is left untouched, and we can apply induction to the remaining pebbles.

In any final position, there is at most one pebble in each square, and there are no k consecutive non-empty squares. To finish the proof it suffices to show that any two different positions with these properties have different weights. Let X = (x_{i}) and Y = (y_{i}) be two such positions; n — the maximal index for which x_{n} ≠ y_{n}; say, x_{n} = 1, y_{n} = 0. Let s = ∑_{i>n} w_{i}x_{i} = ∑_{i>n} w_{i}y_{i}. Then

w(X) ≥ s + α^{n};
w(Y) < s + ∑_{l≥0} ∑_{i=1}^{k−1} α^{n−kl−i} = s + α^{n};

and w(X) > w(Y). The lemma is proved.

Now, let a_{n} = ∑ x_{i}b_{n+i} be any linear combination of shifts of the base sequence with non-negative integer coefficients. Take (x_{i}) as the initial position of the above game; let (y_{i}) be the corresponding unique final position. As in the proof of the lemma, we have ∑ y_{i}b_{n+i} = ∑ x_{i}b_{n+i} = a_{n}. Let m be the minimal index for which y_{m} ≠ 0. We see that, starting from n = −m, the sequence (a_{i}) is a successor sequence.

By a similar but more involved argument one can prove that the numeration system with the maximal sequence 100100100 … (and with the recurrence b_{n+1} = b_{n} + b_{n−2}) is also complete. On the other hand, this is not so for the recurrence b_{n+1} = b_{n} + b_{n−3}.

Problem. Classify all based tree-like numeration systems with recurrent base sequences which are complete.

Remark. Lemma 6.2 was given as a problem at 1997 Russian Mathematical Olympiad, and was voted by the participants “the best problem of the year”.

7 Exercise

Given n, form all possible sequences of positive integers with sum n. For each such sequence, multiply the terms together; then take the sum of all these products. What is the result?

References

[1] H. S. M. Coxeter, Introduction to Geometry, Wiley, New York, 1961.

[2] C. Kimberling, Numeration systems and fractal sequences, Acta Arith. 73 (1995), 103–117.