# Ambiguity in the m-bonacci numeration system

Petra Kocábová and Zuzana Masáková and Edita Pelantová

Department of Mathematics FNSPE, Czech Technical University
Trojanova 13, 120 00 Praha 2, Czech Republic

received 27 Dec 2004, revised 23 Apr 2005, accepted 19 May 2005.

We study the properties of the function $R^{(m)}(n)$ defined as the number of representations of an integer $n$ as a sum of distinct $m$-Bonacci numbers $F_k^{(m)}$, given by $F_i^{(m)} = 2^{i-1}$, for $i \in \{1, 2, \dots, m\}$, $F_{k+m}^{(m)} = F_{k+m-1}^{(m)} + F_{k+m-2}^{(m)} + \dots + F_k^{(m)}$, for $k \ge 1$. We give a matrix formula for calculating $R^{(m)}(n)$ from the greedy expansion of $n$. We determine the maximum of $R^{(m)}(n)$ for $n$ with greedy expansion of fixed length $k$, i.e. for $F_k^{(m)} \le n < F_{k+1}^{(m)}$. Unlike the Fibonacci case $m = 2$, the values of the maxima are not related to the sequence $(F_k^{(m)})_{k \ge 1}$. We describe the palindromic structure of the sequence $(R^{(m)}(n))_{n \in \mathbb{N}}$, which is richer than in the case of Fibonacci numeration system.

**Keywords:** numeration system, generalized Fibonacci numbers, greedy expansion, palindromes

## 1 Introduction

Any strictly increasing sequence $(G_k)_{k \in \mathbb{N}}$, with $G_k \in \mathbb{N}$, $G_1 = 1$, defines a system of numeration where every positive integer can be written as a linear combination $\sum a_k G_k$, where $a_k \in \mathbb{N}_0$, see for instance [8]. Some sequences $(G_k)_{k \in \mathbb{N}}$ have even nicer property: Every positive integer can be expressed as a sum of distinct elements of the sequence $(G_k)_{k \in \mathbb{N}}$. The necessary and sufficient condition so that it is possible is that the sequence satisfies $G_1 = 1$ and $G_n - 1 \le \sum_{i=1}^{n-1} G_i$ for all $n \in \mathbb{N}$. Example of such a sequence is $(2^{k-1})_{k \ge 1}$ or $(F_k)_{k \ge 1}$, the sequence of Fibonacci numbers. The expression of $n$ in the form

$$n = G_{i_s} + G_{i_{s-1}} + \dots + G_{i_1}, \quad \text{where } i_s > i_{s-1} > \dots > i_1 \ge 1,$$

is called a representation of $n$ in the numeration system $(G_k)_{k \in \mathbb{N}}$. This representation can be written using a sequence of coefficients $(a_k)_{k \in \mathbb{N}} \in \{0, 1\}^\mathbb{N}$ as $n = \sum_{i=1}^\infty a_i G_i$, where only a finite number of elements of the sequence $(a_k)_{k \in \mathbb{N}}$ are non-zero. The maximal index $k$ such that $a_k \ne 0$ are called the length of the representation. The representation can be coded by the word $a_k a_{k-1} \cdots a_1$ in the alphabet $\{0, 1\}$. In the writing of number representations we adopt the usual convention that the concatenation of $l$ copies of a finite word is written $w^l$, for $l = 0, 1, 2, \dots$. For example, the representation of the number $n = G_{k+2} + G_k$ is coded by the word $1010^{k-1}$.

If $(G_k)_{k \in \mathbb{N}} = (2^{k-1})_{k \ge 1}$, then the representation of every integer $n$ in the system $(G_k)_{k \in \mathbb{N}}$ is unique, and the word $a_k a_{k-1} \cdots a_1$ is the binary expansion of $n$. If we choose for $(G_k)_{k \in \mathbb{N}}$ the
Fibonacci sequence $G_k = F_k$, given by the recurrence $F_{k+2} = F_{k+1} + F_k$, $F_0 = F_1 = 1$, then most integers have several representations. The number of distinct representations, denoted by $R(n)$, is a function studied by many authors [1, 2, 5, 11].

On the set of representations of a given integer $n$ in the system $(G_k)_{k \in \mathbb{N}}$ one can introduce the lexicographic order in the following way: We say that the representation $v_l v_{l-1} \cdots v_1$ of the number $n$ is greater than the representation $u_k u_{k-1} \cdots u_1$ of $n$ if $l > k$ or $l = k$ and the first non zero element in the sequence $v_k - u_k, v_{k-1} - u_{k-1}, \cdots, v_1 - u_1$ is positive. This order is sometimes called the radix order. The lexicographically greatest representation of a given number $n$ is called the greedy expansion of $n$.

In this paper we study the measure of ambiguity of the representation of integers in the generalized Fibonacci numeration systems, the so-called *m*-Bonacci systems defined for $m \ge 2$ by recurrence

$$ 
\begin{gathered}
F_1^{(m)} = 1, \quad F_2^{(m)} = 2, \quad \dots, \quad F_m^{(m)} = 2^{m-1}, \\
F_{k+m}^{(m)} = F_{k+m-1}^{(m)} + F_{k+m-2}^{(m)} + \dots + F_k^{(m)}, \quad \text{for } k \ge 1.
\end{gathered}
\tag{1} $$

The 2-Bonacci sequence is thus the ordinary Fibonacci sequence; 3-Bonacci sequence is usually called the Tribonacci sequence. Combinatorial properties of the *m*-Bonacci numeration system have been discussed in [7], in order to study the Garsia entropy connected with Pisot numbers $\beta$ fulfilling $\beta^m = \beta^{m-1} + \cdots + \beta + 1$.

The *m*-Bonacci numeration systems are studied in [6] from the point of view of automata theory. It is proven that addition of integers written in the *m*-Bonacci numeration system can be performed by means of a finite state automaton, whereas it is impossible to convert an *m*-Bonacci representation of an integer into its standard binary expansion by a finite state automaton.

It has been shown already in [10] that every non-negative integer $n$ can be represented as a sum of distinct elements of the *m*-Bonacci sequence. Such representation of $n$ may not be unique. We denote by $R^{(m)}(n)$ the number of different representations of $n$. The recurrence relation for *m*-Bonacci numbers ensures that starting from an arbitrary representation of $n$ we can get any other representation of $n$ by interchanging $10^m \leftrightarrow 01^m$ or vice versa in the word coding the representation of $n$.

Obviously, the lexicographically greatest (greedy) representation of $n$ does not contain the block $1^m$. Let us denote the greedy expansion of $n$ in the numeration system $(F_k^{(m)})_{k \ge 1}$ by $\langle n \rangle_m$. It can be written in the form

$$ \langle n \rangle_m = 10^{r_s} 10^{r_{s-1}} 10^{r_{s-2}} \cdots 10^{r_2} 10^r, \quad \text{where } r_i \in \mathbb{N}_0, $$

and for every $i$ such that $m-1 \le i \le s$ we have $r_{i-m+2} + r_{i-m+3} + \cdots + r_i \ge 1$. The length of the greedy expansion $\langle n \rangle_m$ is $s+r_s+r_{s-1}+\cdots+r_1$. If the lengths of $\langle n \rangle_m$ is $k$, then every other representation of $n$ has the length either $k$ or $k-1$. Representations of length $k$ are called ‘long’ representations and their number is denoted by $R_1^{(m)}(n)$; the other representations are called ‘short’ and their number is denoted by $R_0^{(m)}(n)$. Obviously, we have

$$ R^{(m)}(n) = R_0^{(m)}(n) + R_1^{(m)}(n). $$

The aim of the paper is to study the properties of the function $R^{(m)}(n)$. First we show that the Berstel matrix formula [1] for calculation of the value $R^{(2)}(n)$ from the greedy expansion $\langle n \rangle_m$ can
be generalized for $m \ge 3$. In the next section we focus on the study of the segment of the sequence $R^{(m)}(n)$ for $F_k^{(m)} \le n < F_{k+1}^{(m)}$, i.e. for such integers $n$ whose greedy expansion has constant length $k$. For the Fibonacci numeration system it is known [2, 5] that among numbers with a fixed length $k$ of the greedy expansion only $n = F_{k+1}^{(2)} - 1$ satisfies $R^{(2)}(n) = 1$, and moreover, the segments of the sequence $R^{(2)}(n)$ between two unit values are palindromes. For the $m$-Bonacci numeration system with $m \ge 3$ we show that the number of integers $n$ in the segment $[F_k^{(m)}, F_{k+1}^{(m)})$ with a unique representation $R^{(m)}(n) = 1$ is equal to the $(m-1)$-Bonacci number $F_k^{(m-1)}$. Thus the number of $1$'s in the corresponding segment of the sequence $(R^{(m)}(n))_{n \in \mathbb{N}}$ increases, however, we show that the palindromic structure of the sequence $(R^{(m)}(n))_{n \in \mathbb{N}}$ remains preserved.

In the rest of the paper we determine the maximum of the function $(R^{(m)}(n))_{n \in \mathbb{N}}$ in the mentioned segment. For $m = 2$, i.e. the Fibonacci numeration system, the maxima have been determined in [11],

$$ \max\{R^{(2)}(n) \mid F_k^{(2)} \le n < F_{k+1}^{(2)}\} = \begin{cases} F_{\frac{k+1}{2}}^{(2)} & \text{for } k \text{ odd,} \\ 2F_{\frac{k-2}{2}}^{(2)} & \text{for } k \text{ even.} \end{cases} $$

We shall thus concentrate on determining the values of the maxima for $m \ge 3$. Unlike the Fibonacci case, the values of the maxima are not related to the sequence $(F_k^{(m)})_{k \ge 1}$.

## 2 The number of representations of $n$ in the $m$-Bonacci system

The number of representations of a given integer $n$ is related to the possible interchanges $10^m \leftrightarrow 01^m$ in the greedy expansion of $n$. For example, if $\langle n \rangle_m$ is of length $k \le m$, then no interchange is possible and we have $R^{(m)}(n) = 1$. If the length of $\langle n \rangle_m$ is $m+1$, then only $\langle n \rangle_m = 10^m$ admits such an interchange. It follows that

$$ \begin{aligned} R^{(m)}(n) &= 1, && \text{for } 1 \le n \le F_{m+2}^{(m)} - 1, \quad n \ne F_{m+1}^{(m)}, \\ R^{(m)}(F_{m+1}^{(m)}) &= 2. && \end{aligned} \qquad (2) $$

The aim of this section is to derive a compact formula for calculating the values of the function $R^{(m)}(n)$. Both the formula and its proof are slight generalizations of the result of [1, 5] for the case $m = 2$. Consider therefore $m \ge 3$.

First we state several simple observations, which transpose the calculation of the value $R_0^{(m)}(n)$ and $R_1^{(m)}(n)$ for an integer $n$ with $s$ $1$'s in its greedy expansion to calculation of $R_0^{(m)}(n)$ and $R_1^{(m)}(n)$ for some $\tilde{n}$ whose greedy expansion has strictly smaller number $\tilde{s} < s$ of $1$'s. In the following, we shall identify the writing $R^{(m)}(n)$ with $R^{(m)}(w)$, where $w$ is the word in the alphabet $\{0, 1\}$ coding the greedy expansion of $n$, i.e. a word starting with 1.

**Fact 2.1** If $0 \le l \le m-2$, then $R_0^{(m)}(10^l w) = 0$, therefore $R_1^{(m)}(10^l w) = R^{(m)}(w)$. In matrix form,

$$ \begin{pmatrix} R_0^{(m)}(10^l w) \\ R_1^{(m)}(10^l w) \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} R_0^{(m)}(w) \\ R_1^{(m)}(w) \end{pmatrix}. $$
**Remark 2.2**

(i) Note that $R_0^{(m)}(10^l w) = 0$ does not imply $l \le m-2$. It is not difficult to see that $R_0^{(m)}(w) = 0$ implies that the word $w$ is of the form $w = (10^{m-1})^s \tilde{w}$, where $s \ge 0$ and $\tilde{w}$ is either the empty word, or a word of the form $\tilde{w} = 10^l \tilde{w}$ for $l \le m-2$. Therefore the smallest $n_1$ such that $\langle n_1 \rangle_m = k$ and for which $R_0^{(m)}(n_1) = 0$ is the number with greedy expansion

$$ \langle n_1 \rangle_m = \begin{cases} (10^{m-1})^s, & \text{if } s := \frac{k}{m} \in \mathbb{N}, \\ (10^{m-1})^s 10^{k-ms-1}, & \text{if } s := \lfloor \frac{k}{m} \rfloor \neq \frac{k}{m}. \end{cases} \quad (3) $$

At the same time, for every $n$ such that $n_1 \le n < F_{k+1}^{(m)}$ we have $R_0^{(m)}(n) = 0$.

(ii) In the word $\langle n_1 \rangle_m$ of the form (3) one cannot perform any interchange $10^m \leftrightarrow 01^m$, and therefore $R^{(m)}(n_1) = 1$. We have thus found the smallest number $n$ such that $F_k^{(m)} \le n < F_{k+1}^{(m)}$ and $R^{(m)}(n) = 1$. Note that in the Fibonacci numeration system $R_0^{(2)}(n) = 0$ already implies $R^{(2)}(n) = 1$. For $m \ge 3$ this is not valid. As an example, consider $\langle n \rangle_m = 110^{k-2}$ for $k \ge m+2$. Such $n$ satisfies $R_0^{(m)}(n) = 0$ and $R^{(m)}(n) \ge 2$.

(iii) Let us express explicitly the value of $n_1$. Every 1 in the word $\langle n_1 \rangle_m$ at the position $i > m$ represents the number

$$ F_i^{(m)} = F_{i-1}^{(m)} + F_{i-2}^{(m)} + \dots + F_{i-m}^{(m)}. $$

The 1 at a position $i \le m$ represents

$$ F_i^{(m)} = 2^{i-1} = 1 + F_{i-1}^{(m)} + F_{i-2}^{(m)} + \dots + F_1^{(m)}. $$

The number $n_1$ with greedy expansion of the form (3) is therefore equal to

$$ n_1 = 1 + \sum_{i=1}^{k-1} F_i^{(m)}. $$

**Fact 2.3** $R_0^{(m)}(10^{m-1}w) = R_0^{(m)}(w)$ and $R_1^{(m)}(10^{m-1}w) = R^{(m)}(w)$. In a matrix form,

$$ \begin{pmatrix} R_0^{(m)}(10^{m-1}w) \\ R_1^{(m)}(10^{m-1}w) \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} R_0^{(m)}(w) \\ R_1^{(m)}(w) \end{pmatrix}. $$

**Fact 2.4** If $l \ge m$, then we have $R_0^{(m)}(10^l w) = R^{(m)}(10^{l-m}w)$ and $R_1^{(m)}(10^l w) = R_1^{(m)}(10^{l-m}w)$. In a matrix form,

$$ \begin{pmatrix} R_0^{(m)}(10^l w) \\ R_1^{(m)}(10^l w) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} R_0^{(m)}(10^{l-m} w) \\ R_1^{(m)}(10^{l-m} w) \end{pmatrix}. $$

**Lemma 2.5** Let $\langle n \rangle_m = 10^l w$, where $w = \langle \tilde{n} \rangle_m$ for some integer $\tilde{n}$. Then

$$ \begin{pmatrix} R_0^{(m)}(10^l w) \\ R_1^{(m)}(10^l w) \end{pmatrix} = \begin{pmatrix} \lfloor \frac{l+1}{m} \rfloor & \lfloor \frac{l}{m} \rfloor \\ 1 & 1 \end{pmatrix} \begin{pmatrix} R_0^{(m)}(w) \\ R_1^{(m)}(w) \end{pmatrix}. $$
**Proof:** Let us write $l = am+b$, where $b \in \{0, 1, \dots, m-1\}$. If $b \le m-2$, then for the calculation of the values $R_0^{(m)}(10^l w)$, $R_1^{(m)}(10^l w)$ one uses $a$ times Fact 2.4 and then Fact 2.1. Since

$$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^a \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} a & a \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} \left[ \frac{l+1}{m} \right] & \left[ \frac{l}{m} \right] \\ 1 & 1 \end{pmatrix}, $$

the statement is proved.

If $b = m-1$, we use $a$ times Fact 2.4 and then Fact 2.3. The matrix identity

$$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^a \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} a+1 & a \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} \left[ \frac{l+1}{m} \right] & \left[ \frac{l}{m} \right] \\ 1 & 1 \end{pmatrix}, $$

completes the proof.

□

In order to derive the formula for calculation of $R^{(m)}(n)$, we need to derive the values $R_0^{(m)}(n)$, $R_1^{(m)}(n)$ for integers $n$ with only one 1 in their greedy expansion. It is easy to see that $R_1^{(m)}(10^l) = 1$ and $R_0^{(m)}(10^l) = \left[\frac{l}{m}\right]$, which can be written by

$$ \begin{pmatrix} R_0^{(m)}(10^l) \\ R_1^{(m)}(10^l) \end{pmatrix} = \begin{pmatrix} \left[ \frac{l+1}{m} \right] & \left[ \frac{l}{m} \right] \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$

Since $R^{(m)}(n) = R_0^{(m)}(n) + R_1^{(m)}(n)$, we can formulate the result. For that we introduce the following notation,

$$ M(l) = M_m(l) := \begin{pmatrix} \left[ \frac{l+1}{m} \right] & \left[ \frac{l}{m} \right] \\ 1 & 1 \end{pmatrix}. \qquad (4) $$

**Theorem 2.6** Let $\langle n \rangle_m = 10^{r_s} 10^{r_{s-1}} \cdots 10^{r_1}$ be the greedy expansion of the integer $n$ in the $m$-Bonacci numeration system. Then

$$ R^{(m)}(n) = (1 \ 1) M(r_s) M(r_{s-1}) \cdots M(r_1) \begin{pmatrix} 0 \\ 1 \end{pmatrix}. \qquad (5) $$

### 3 Integers with a unique representation in the $m$-Bonacci numeration system

In order that an integer $n$ has only one representation in the $m$-Bonacci numeration system, the lexicographically greatest and the lexicographically smallest representation must coincide. Consider $n$ in the interval $[F_k^{(m)}, F_{k+1}^{(m)})$. The word coding the greedy expansion of $n$ has the form

$$ u_k u_{k-1} \cdots u_1, \quad \text{where } u_1, \dots, u_{k-1} \in \{0, 1\} \text{ and } u_k = 1. \qquad (6) $$

If $k < m$, then an arbitrary word of the above form is a greedy expansion of some integer $n$. At the same time it is obvious that in such a word one cannot perform any interchange $10^m \leftrightarrow 01^m$ and therefore this integer $n$ has only one $m$-Bonacci representation. Let

$$ U_k^{(m)} = \#\{n \mid F_k^{(m)} \le n < F_{k+1}^{(m)}, R^{(m)}(n) = 1\}. $$
We have derived that

$$U_k^{(m)} = 2^{k-1}, \quad \text{for } k = 1, 2, \dots, m-1. \qquad (7)$$

Consider now $k \ge m$. A word of length $k$ satisfying (6) is a greedy expansion of some integer $n$, if and only if it does not contain the string $1^m$. In order that no interchange $10^m \leftrightarrow 01^m$ is possible in this word, so that $R^{(m)}(n) = 1$, the word cannot contain the string $0^m$. Therefore $U_k^{(m)}$ is equal to the number of words $u_k u_{k-1} \cdots u_1$ such that

$$ \begin{array}{l} u_1, \dots, u_{k-1} \in \{0,1\}, \quad u_k = 1, \quad \text{and} \\ u_k u_{k-1} \cdots u_1 \text{ does not contain the strings } 0^m, 1^m. \end{array} \qquad (8) $$

In order to determine $U_k^{(m)}$, we divide words satisfying (8) into $2(m-1)$ disjoint groups according to their suffix

$$v \in S := \{10, 10^2, 10^3, \dots, 10^{m-1}, 01, 01^2, 01^3, \dots, 01^{m-1}\}.$$

The number of words satisfying (8) with suffix $v$ will be denoted by $A_k^v$. Obviously,

$$U_k^{(m)} = \sum_{v \in S} A_k^v.$$

Since every word $w$ of length $k$ satisfying (8) is of the form $w = \tilde{w}0$ or $w = \tilde{w}1$, where $\tilde{w}$ is a word of length $k-1$ satisfying (8), we obtain recurrence relations

$$A_k^{10} = A_{k-1}^{01} + A_{k-1}^{012} + \cdots + A_{k-1}^{01^{m-1}}, \qquad (9)$$

$$A_k^{10^l} = A_{k-1}^{10^{l-1}}, \quad \text{for } l = 2, 3, \dots, m-1, \qquad (10)$$

$$A_k^{01} = A_{k-1}^{10} + A_{k-1}^{102} + \cdots + A_{k-1}^{10^{m-1}}, \qquad (11)$$

$$A_k^{01^l} = A_{k-1}^{01^{l-1}}, \quad \text{for } l = 2, 3, \dots, m-1. \qquad (12)$$

Equations (9) and (11) imply that $U_k^{(m)} = A_{k+1}^{10} + A_{k+1}^{01}$. From (10) we obtain $A_k^{10^l} = A_{k-l+1}^{10}$ for $l = 2, 3, \dots, m-1$. Similarly, from (12) we obtain $A_k^{01^l} = A_{k-l+1}^{01}$ for $l = 2, 3, \dots, m-1$. Substituting this into (9) and (11) and taking sum, we obtain

$$U_k^{(m)} = A_{k+1}^{10} + A_{k+1}^{01} = (A_k^{10} + A_k^{01}) + (A_{k-1}^{10} + A_{k-1}^{01}) + \cdots + (A_{k-m+2}^{10} + A_{k-m+2}^{01}).$$

The sequence $(A_{k+1}^{10} + A_{k+1}^{01})_{k \in \mathbb{N}} = (U_k^{(m)})_{k \in \mathbb{N}}$ thus satisfies the same recurrence relation as the $(m-1)$-Bonacci sequence $F_k^{(m-1)}$. It has even the same initial conditions (cf. (1) and (7)). We have thus derived the following statement.

**Proposition 3.1** For $m \ge 3$ the number of integers $n$ with greedy expansion of length $k$ having unique representation in the $m$-Bonacci numeration system is equal to the $k$-th element of the $(m-1)$-Bonacci system. Formally,

$$\#\{n \mid F_k^{(m)} \le n < F_{k+1}^{(m)} \text{ and } R^{(m)}(n) = 1\} = F_k^{(m-1)}. $$

A general theory for counting the number of words with forbidden strings is developed in [9].
## 4 Palindromic structure of $R^{(m)}(n)$

Let us recall that transition between different representations of the same integer $n$ is allowed by the interchange $10^m \leftrightarrow 01^m$. Note that the block $10^m$ is the complement of the block $01^m$, in the sense that every 1 is substituted by 0 and every 0 is substituted by 1. Taking complement of the word $\langle n \rangle_m = 1u_{k-1} \cdots u_1$, we obtain the word $0(1-u_{k-1})(1-u_{k-2})\cdots(1-u_1)$, which is an $m$-Bonacci representation of an integer, which we denote by $\bar{n}$. It is obvious that

$$R^{(m)}(n) = R^{(m)}(\bar{n}).$$

Since

$$n + \bar{n} = \sum_{i=1}^{k} F_{i}^{(m)} \qquad (13)$$

the center of the symmetry of the function $R^{(m)}(n)$ is in the value $c = \frac{1}{2} \sum_{i=1}^{k} F_{i}^{(m)}$. Thus the sequence $(R^{(m)}(n))_{n \in \mathbb{N}}$ contains a palindrome, which ends with the value $R^{(m)}(F_{k+1}^{(m)} - 1)$ and starts with the value $R^{(m)}(\sum_{i=1}^{k} F_{i}^{(m)} - F_{k+1}^{(m)} + 1)$. Note that the center of the symmetry $c$ satisfies $F_{k}^{(m)} < c < F_{k+1}^{(m)}$ for $k \ge m + 2$. According to (2), the values $R^{(m)}(1), \dots, R^{(m)}(F_{m+2}^{(m)} - 1)$ are all equal to 1 except $R^{(m)}(F_{m+1}^{(m)}) = 2$, thus only $k \ge m + 2$ is interesting.

**Remark 4.1** For $m = 2$, i.e. for the Fibonacci sequence, we have $\sum_{i=1}^{k} F_{i}^{(2)} = F_{k+2}^{(2)} - 2$. Thus the beginning of the palindrome is at $F_{k}^{(2)} - 1$ and the end at $F_{k+1}^{(2)} - 1$.

**Remark 4.2** For $m \ge 3$, we have for the starting index of the palindrome

$$\sum_{i=1}^{k} F_{i}^{(m)} - F_{k+1}^{(m)} + 1 < F_{k-1}^{(m)}.$$

Therefore having calculated the values of the function $R^{(m)}(n)$ for $n \le F_{k}^{(m)} - 1$, most of the values $R^{(m)}(n)$ for $F_{k}^{(m)} \le n < F_{k+1}^{(m)}$ can be obtained from the palindromic structure.

Let us determine the smallest number $n_0 \in [F_{k}^{(m)}, F_{k+1}^{(m)})$, whose complement $\bar{n}_0$ lies in the range $[1, F_{k}^{(m)})$, where we assume having the knowledge of the values of $R^{(m)}$. Obviously $\bar{n}_0 = F_{k}^{(m)} - 1$ and from (13) we have $n_0 = \sum_{i=1}^{k-1} F_{i}^{(m)} + 1$. For $k \ge m + 2$ we have $n_0 > F_k$. Note that $n_0$ is the same as the number $n_1$ from Remark 2.2. Thus the values $R^{(m)}(n)$ for $\bar{n}_0 + 1 = F_{k}^{(m)} \le n \le n_0 - 1$ are not equal to 1. The sequence $R^{(m)}(\bar{n}_0 + 1), R^{(m)}(\bar{n}_0 + 2), \dots, R^{(m)}(n_0 - 1)$ is a palindrome which does not contain the number 1.

**Example 4.3** For the Tribonacci numeration system, i.e. for $m = 3$, the values of the function $R_3^{(m)}$ between $F_7^{(3)} = 44$ and $F_8^{(3)} - 1 = 80$ are the following.

$$ \begin{array}{ccc} R^{(3)}(44) & n_0 = 52 & R^{(3)}(80) \\ \downarrow & \downarrow & \downarrow \\ 3222222311111221111121112222111211111 & & \\ \uparrow & & \\ \end{array} $$

center of the palindrome
Note that the value 1 appears in the line 21 times, where $21 = F_7^{(2)}$ as corresponds to Proposition 3.1. The line does not show the entire palindrome; the missing values are $R^{(3)}(15), \dots, R^{(3)}(43)$.

We end this section with a theorem whose proof for $m = 2$ can be found in [2, 5]. The proof for $m \ge 3$ follows by induction on the length of the greedy expansion of $n$ from Remark 4.2.

**Theorem 4.4** The segment of the sequence $R^{(m)}(n)$ between two consecutive 1's forms a palindrome, i.e. if $R^{(m)}(p) = R^{(m)}(q) = 1$ and $R^{(m)}(n) > 1$ for all $n, p < n < q$, then the sequence $R^{(m)}(p), R^{(m)}(p+1), \dots, R^{(m)}(q-1), R^{(m)}(q)$ is invariant under mirror image.

## 5 Maxima of the function $R^{(m)}(n)$

The aim of this section is to determine the maximal value of the function $R^{(m)}$ on integers with a fixed length of the greedy expansion. Denote

$$ \text{Max}(k) := \max\{R^{(m)}(n) \mid F_k^{(m)} \le n < F_{k+1}^{(m)}\}. $$

The values $\text{Max}(k)$ for small $k$ can be determined easily. We will use them as the initial step for the proof of the main theorem, which will be done by induction.

* If $k \le m$, then in the expansion of the length $k$ one cannot perform any interchange $10^m \leftrightarrow 01^m$. Thus

$$ \text{Max}(k) = 1, \quad \text{for } 1 \le k \le m. $$

* For $m < k \le 2m$ one can perform at most one interchange $10^m \leftrightarrow 01^m$ and therefore

$$ \text{Max}(k) = 2, \quad \text{for } m+1 \le k \le 2m. $$

* For $k = 2m+1$ one can perform in the strings $10^{m-1}10^m$ and $10^{2m}$ two interchanges in a given order. Therefore

$$ \text{Max}(2m+1) = 3. $$

* For $2m+1 < k \le 3m$ one can perform on suitable chosen words two independent interchanges. Therefore

$$ \text{Max}(k) = 4, \quad \text{for } 2m+2 \le k \le 3m. $$

* For $k = 3m+1$ we can see by similar arguments that

$$ \text{Max}(3m+1) = 5. $$

In order to obtain a lower bound on $\text{Max}(k)$, we determine the value $R^{(m)}(n)$ on the integers represented by the following words: for $k = a(m+1), a(m+1)+1, \dots, a(m+1)+m-2$ consider $n$ with the greedy expansion of the form

$$ \langle n \rangle_m = (10^m)^a, \ 1(10^m)^a, \ 10(10^m)^a, \ \dots, \ 10^{m-2}(10^m)^a. $$
Using the matrix formula we obtain

$$ \text{Max}(a(m+1)+b) \geq R^{(m)}(n) = (1 \ 1) \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}^a \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 2^a, \quad \text{for } b \in \{0, 1, \dots, m-2\}. $$

For $k = a(m + 1) + m - 1$ the value of $R^{(m)}(n)$ at $n$ with the greedy expansion $\langle n \rangle_m = 10^{2m-1}(10^m)^{a-1}$ is equal to

$$ \text{Max}(a(m+1)+m-1) \geq R^{(m)}(n) = (1 \ 1) \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}^{a-1} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 2^a + 2^{a-2}. $$

For $k = a(m + 1) + m$ the value of $R^{(m)}(n)$ at $n$ with the greedy expansion $\langle n \rangle_m = 10^{m-1}(10^m)^a$ is equal to

$$ \text{Max}(a(m+1)+m) \geq R^{(m)}(n) = (1 \ 1) \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}^a \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 2^a + 2^{a-1}. $$

In the remaining part of this section we show that the above values are equal to $\text{Max}(k)$.

Let us describe what form of the greedy expansion an argument of the maxima may have. For that we introduce the following notions.

**Definition 5.1** Let $\mathcal{X} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ and $\tilde{\mathcal{X}} = \begin{pmatrix} \tilde{a} & \tilde{b} \\ \tilde{c} & \tilde{d} \end{pmatrix}$ be integer matrices with non-negative components. We say that $\tilde{\mathcal{X}}$ majores $\mathcal{X}$ (written $\tilde{\mathcal{X}} \succ \mathcal{X}$) if

$$ \tilde{a} \ge a, \quad \tilde{b} \ge b, \quad \tilde{a} + \tilde{c} \ge a + c \quad \text{and} \quad \tilde{b} + \tilde{d} > b + d. \qquad (14) $$

**Definition 5.2** We say that the string $10^{t_i} 10^{t_{i-1}} \cdots 10^{t_1}$ is forbidden for maximality, if there exists a word $10^{u_j} 10^{u_{j-1}} \cdots 10^{u_1}$ such that

$$ t_1 + t_2 + \cdots + t_i + i = u_1 + u_2 + \cdots + u_j + j, \quad u_1, u_j > 0, \qquad (15) \\ M(t_i)M(t_{i-1})\cdots M(t_1) < M(u_j)M(u_{j-1})\cdots M(u_1). $$

**Proposition 5.3** Let $n$ be an integer such that $\langle n \rangle_m = 10^{r_s} 10^{r_{s-1}} \cdots 10^{r_1}$ and

$$ \text{Max}(k) = R^{(m)}(n) \quad \text{and} \quad F_k^{(m)} \le n < F_{k+1}^{(m)}. $$

Then $10^{r_1} 10^{r_{l-1}} \cdots 10^{r_{l-i+1}}$ is not a string forbidden for maximality for any integers $l, i$, such that $1 \le l - i + 1 \le l \le s$.

**Proof:** We prove the proposition by contradiction. Let $\langle n \rangle_m = 10^{r_s} 10^{r_{s-1}} \cdots 10^{r_1}$ contain a string $10^{t_i} 10^{t_{i-1}} \cdots 10^{t_1}$ forbidden for maximality, i.e. there exists $l \le s$ such that $r_l = t_i$, $r_{l-1} = t_{i-1}$, ..., $r_{l-i+1} = t_1$, then the word

$$ 10^{r_s} \cdots 10^{r_{l+1}} 10^{u_j} 10^{u_{j-1}} \cdots 10^{u_1} 10^{r_{l-i}} \cdots 10^{r_1} $$
has the same length as the greedy expansion $\langle n \rangle_m$. The condition $u_1, u_j > 0$ ensures that the new word is a greedy expansion of some integer $\tilde{n}$. Put

$$ \mathbb{A} = \begin{cases} \mathbb{I}_2, & \text{if } l=s, \\ M(r_s) \cdots M(r_{l+1}), & \text{if } l<s, \end{cases} \quad \mathbb{B} = \begin{cases} \mathbb{I}_2, & \text{if } l-i=0, \\ M(r_{l-i}) \cdots M(r_1), & \text{if } l-i>0. \end{cases} $$

and

$$ \mathbb{X} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} = M(t_i) \cdots M(t_1) \quad \text{and} \quad \tilde{\mathbb{X}} = \begin{pmatrix} \tilde{a} & \tilde{b} \\ \tilde{c} & \tilde{d} \end{pmatrix} = M(u_j) \cdots M(u_1). $$

In this notation $R^{(m)}(n) = (1 \ 1)\mathbb{A}\mathbb{X}\mathbb{B}_{1}^{(0)}$ and $R^{(m)}(\tilde{n}) = (1 \ 1)\mathbb{A}\tilde{\mathbb{X}}\tilde{\mathbb{B}}_{1}^{(0)}$. Denote $(x \ y) = (1 \ 1)\mathbb{A}$ and $(z_u^0) = \mathbb{B}_{1}^{(0)}$. From the form of the matrices $\mathbb{A}, \mathbb{B}$ it can be easily seen that $x \ge y \ge 1$ and $z \ge 0, u \ge 1$. Since $\mathbb{X} \prec \tilde{\mathbb{X}}$, their components satisfy (14). We have

$$ \begin{aligned} R^{(m)}(\tilde{n}) - R^{(m)}(n) &= (x \ y) \begin{pmatrix} \tilde{a} & \tilde{b} \\ \tilde{c} & \tilde{d} \end{pmatrix} \begin{pmatrix} z \\ u \end{pmatrix} - (x \ y) \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} z \\ u \end{pmatrix} = \\ &= \begin{pmatrix} (\tilde{a} - a)x + (\tilde{c} - c)y, & (\tilde{b} - b)x + (\tilde{d} - d)y \end{pmatrix} \begin{pmatrix} z \\ u \end{pmatrix} \ge \\ &\ge \begin{pmatrix} (\tilde{a} + \tilde{c} - a - c)y, & (\tilde{b} + \tilde{d} - b - d)y \end{pmatrix} \begin{pmatrix} z \\ u \end{pmatrix} \ge (0 \ 1) \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 1. \end{aligned} $$

Therefore $R^{(m)}(\tilde{n}) > R^{(m)}(n)$, and $n$ was not the argument of the maxima. $\square$

The above proposition enables us to restrict the set of candidates for the arguments of the maxima. Let us recall that we consider $m \ge 3$, if not stated otherwise.

**Claim 5.4** Let $n$ have the greedy expansion $\langle n \rangle_m = 10^{r_s} \cdots 10^{r_1}$ of length $k$ and let $\text{Max}(k) = R^{(m)}(n)$. Then for every $i$ it holds that $r_i \le 2m$ or $r_i = 3m - 1$.

**Proof:** It is sufficient to show that the string $10^t$ where $t > 2m$ and $t \ne 3m - 1$ is forbidden for maximality. Consider the string $10^{u_2}10^{u_1} = 10^{t-m-1}10^m$. Both strings $10^t$ and $10^{u_2}10^{u_1}$ have the same length, and $u_1, u_2 > 0$. In order to verify

$$ M(t) = \begin{pmatrix} \lfloor \frac{t+1}{m} \rfloor & \lfloor \frac{t}{m} \rfloor \\ 1 & 1 \end{pmatrix} \prec M(u_2)M(u_1) = \begin{pmatrix} \lfloor \frac{t}{m} \rfloor + \lfloor \frac{t-1}{m} \rfloor - 2 & \lfloor \frac{t}{m} \rfloor + \lfloor \frac{t-1}{m} \rfloor - 2 \\ 2 & 2 \end{pmatrix} $$

it suffices to show that the inequality

$$ \left\lfloor \frac{t+1}{m} \right\rfloor \le \left\lfloor \frac{t}{m} \right\rfloor + \left\lfloor \frac{t-1}{m} \right\rfloor - 2 $$

is satisfied for $t > 2m$ and $t \ne 3m - 1$. $\square$

The above claim shows which strings of the type $10^t$ are forbidden for maximality. The following claims studies this question for some other types of strings.

**Claim 5.5** The string $10^{m-1}10^{3m-1}$ is forbidden for maximality.
**Proof:** The string $(10^m)^2 10^{2m-3}$ has the same length as $10^{m-1} 10^{3m-1}$ and the corresponding matrix, $M^2(m)M(2m-3) = \binom{4}{4}$, majores the matrix $M(m-1)M(3m-1) = \binom{3}{4}$ corresponding to the string $10^{m-1} 10^{3m-1}$. $\square$

**Claim 5.6** The string $10^{m-1} 10^{m-1}$ is forbidden for maximality.

**Proof:** The string $10^{2m-1}$ has the same length as $10^{m-1} 10^{m-1}$ and the corresponding matrix $M(2m-1) = \binom{2}{1}$ majores the matrix $M^2(m-1) = \binom{1}{2}$ corresponding to the string $10^{m-1} 10^{m-1}$. $\square$

**Claim 5.7** The string $10^{m-1} 10^{2m-1} 10^{m-1}$ is forbidden for maximality.

**Proof:** The string $(10^m)^2 10^{2m-3}$ has the same length and the corresponding matrix $M^2(m)M(2m-3) = \binom{4}{4}$ majores the matrix $M(m-1)M(2m-1)M(m-1) = \binom{3}{5}$ corresponding to the string $10^{m-1} 10^{2m-1} 10^{m-1}$. $\square$

**Claim 5.8** The string $10^{m-1} 10^{2m-1} 10^{2m-1}$ is forbidden for maximality for $m \ge 4$.

**Proof:** The string $10^{m-1} 10^{2m-1} 10^{2m-1}$ has the length $5m$ and the corresponding matrix is $M(m-1)M(2m-1)M(2m-1) = \binom{5}{8}$. Such matrix is majored by the matrix $M^3(m)M(2m-4) = \binom{8}{8}$ corresponding to the string $(10^m)^3 10^{2m-4}$, which has the same length $5m$. $\square$

**Claim 5.9** The string $10^{m-1} 10^{2m-1} 10^{3m-1}$ is forbidden for maximality.

**Proof:** The string $10^{m-1} 10^{2m-1} 10^{3m-1}$ with the corresponding matrix is $M(m-1)M(2m-1)M(3m-1) = \binom{7}{11}$ has the length as the string $10^{2m} 10^{2m} 10^{2m-3}$ whose matrix is $M^2(2m)M(2m-3) = \binom{12}{6}$. $\square$

**Remark 5.10** In searching the maximal values $\text{Max}(k)$ for $k \ge m+1$ one can restrict the consideration to integers $n$ such that in their greedy expansion $\langle n \rangle_m = 10^{r_s} \cdots 10^{r_1}$ the coefficient $r_1$ satisfies $r_1 = m$ or $r_1 = 2m$. For, $r_1 \le m-1$ implies that $R^{(m)}(10^{r_s} 10^{r_{s-1}} \cdots 10^{r_3} 10^{r_2+r_1+1}) \ge R^{(m)}(n)$, as follows from the matrix formula. Similarly, $r_1 = am+b$ with $a \ge 1, b \in \{1, \dots, m-1\}$, implies that $R^{(m)}(10^{r_s} 10^{r_{s-1}} \cdots 10^{r_2+b} 10^{am}) \ge R^{(m)}(n)$. Claim 5.4 moreover implies that $r_1 \in \{m, 2m\}$.

**Theorem 5.11** Let $m, a$ be integers $m \ge 3, a \ge 1$. Then

$$ \text{Max}(a(m+1)+b) = 2^a \quad \text{for } b \in \{0, 1, \dots, m-2\}, $$

$$ \text{Max}(a(m+1)+m-1) = 2^a + 2^{a-2} \quad \text{if } a \ge 2, $$

$$ \text{Max}(a(m+1)+m) = 2^a + 2^{a-1}. $$
**Proof:** The proof is done by induction on the length $k = a(m+1)+b$ of the greedy expansion. The veracity of the statement for the initial values has been established at the beginning of this section. We have also proved that the maxima are greater or equal to the mentioned values. It is therefore sufficient to show that these values are also upper bounds on the maxima.

Assume that $n$ is the argument of the maximum $\text{Max}(k)$. We show that the structure of strings of 0's in the greedy expansion $\langle n \rangle_m = 10^{r_s} 10^{r_{s-1}} \cdots 10^{r_1}$ is only of certain form. First suppose that $R_0^{(m)}(n) = 0$. Then

$$ \text{Max}(k) = R^{(m)}(10^{r_s} 10^{r_{s-1}} \cdots 10^{r_1}) = R^{(m)}(10^{r_{s-1}} \cdots 10^{r_1}) \le \text{Max}(k - r_s - 1), $$

and the statement follows from the induction hypothesis. It is therefore sufficient to consider $n$ such that $R_0^{(m)}(n) \ge 1$. According to Remark 2.2, the greedy expansion $\langle n \rangle_m$ of $n$ is lexicographically smaller than $\langle n_1 \rangle_m$. Together with Claim 5.6 it implies that

$$ \langle n \rangle_m = (10^{m-1})^x 10^y w, \quad \text{where } x \in \{0, 1\}, y \ge m, \tag{16} $$

and $w$ is the empty word or the greedy expansion of an integer.

We show that the coefficients $r_i$ (and in particular the exponent $y$) can take only certain values.

If there exists an index $i$ such that $0 \le r_i \le m-2$, then (16) implies $i < s$. Since $M(r_i) = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}$, we have $M(r_{i+1})M(r_i) = \begin{pmatrix} \frac{r_{i+1}}{m} \\ 1 \end{pmatrix} \begin{pmatrix} \frac{r_{i+1}}{m} \\ 1 \end{pmatrix}$. This implies

$$ \text{Max}(k) = R^{(m)}(10^{r_s} \cdots 10^{r_1}) \le R^{(m)}(10^{r_s} \cdots 10^{r_{i+1}} 10^{r_{i-1}} \cdots 10^{r_1}) \le \text{Max}(k - r_i - 1), $$

and the statement follows from the induction hypothesis.

Similarly, if there exists $i$ such that $m+1 \le r_i \le 2m-2$, then $M(r_i) = M(m)$, and therefore $\text{Max}(k) \le \text{Max}(k - r_i + m)$, and again the statement follows from the induction hypothesis. Therefore using Claim 5.4 and Remark 5.10 we can restrict our consideration to coefficients $r_s, r_{s-1}, \dots, r_2 \in \{m-1, m, 2m-1, 2m, 3m-1\}$ and $r_1 \in \{m, 2m\}$.

It follows that $y$ in (16) takes only values $y \in \{m, 2m-1, 2m, 3m-1\}$. We shall now discuss the possibilities according to the values of $x$ and $y$.

x = 1: Let us discuss the case $x = 1$. The condition $y \ge m$ and Claim 5.5 say that $y \in \{m, 2m, 2m-1\}$.

* Let $\langle n \rangle_m = 10^{m-1} 10^m w$, where the length of the word $w$ is $k - (2m+1)$. Since

$$ (1 \ 1) M(r_s) M(r_{s-1}) = (1 \ 1) \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} = 3(1 \ 1), $$

we have $\text{Max}(k) = 3R^{(m)}(w) \le 3\text{Max}(k - 2m - 1)$. We express $k = a(m+1)+b$, where $b \in \{0, 1, \dots, m\}$. Therefore

$$ \text{Max}(a(m+1)+b) \le 3\text{Max}((a-2)(m+1)+b+1). $$

We distinguish:
- If $b \in \{0, 1, \dots, m-2\}$, then using the induction hypothesis

$$ \mathrm{Max}(a(m+1)+b) \leq 3(2^{a-2} + 2^{a-4}) < 2^a, $$

as required.

- If $b = m-1$, then similarly $\mathrm{Max}(a(m+1)+m-1) \leq 3(2^{a-2} + 2^{a-3}) < 2^a + 2^{a-2}$.

- If $b = m$, then $\mathrm{Max}(a(m+1)+m) \leq 3 \cdot 2^{a-1} = 2^a + 2^{a-1}$.

* Let $\langle n \rangle_m = 10^{m-1}10^{2m}w$, where the length of the word $w$ is $k - (3m+1)$. Since

$$ (1 \ 1)M(r_s)M(r_{s-1}) = (1 \ 1) \binom{1 \ 0}{1 \ 1} \binom{2 \ 2}{1 \ 1} = 5(1 \ 1), $$

we have $\mathrm{Max}(k) = 5R^{(m)}(w) \leq 5\mathrm{Max}(k - 3m - 1)$. We again express $k = a(m+1)+b$, where $b \in \{0, 1, \dots, m\}$. We have therefore

$$ \mathrm{Max}(a(m+1)+b) \leq 5\mathrm{Max}((a-3)(m+1)+b+2). $$

We distinguish

- If $b \in \{0, 1, \dots, m-2\}$, then using the induction hypothesis

$$ \mathrm{Max}(a(m+1)+b) \leq 5(2^{a-3} + 2^{a-4}) < 2^a, $$

as required.

- If $b = m-1$, then $\mathrm{Max}(a(m+1)+m-1) \leq 5(2^{a-2}) = 2^a + 2^{a-2}$.

- If $b = m$, then $\mathrm{Max}(a(m+1)+m) \leq 5 \cdot 2^{a-2} < 2^a + 2^{a-1}$.

* Let now $\langle n \rangle_m = 10^{m-1}10^{2m-1}w$. Claims 5.7, 5.8 and 5.9 imply that the word $w$ is of the form $w = 10^m \tilde{w}$ or $w = 10^{2m} \tilde{w}$. Thus we distinguish:

- Let $\langle n \rangle_m = 10^{m-1}10^{2m-1}10^m \tilde{w}$. Since $(1 \ 1)M(m-1)M(2m-1)M(m) = 8(1 \ 1)$ and the length of the word $\tilde{w}$ is $k - 4m - 1$, we have

$$ \mathrm{Max}(k) \leq 8\mathrm{Max}(k - 4m - 1) \leq 2^3\mathrm{Max}(k - 3(m + 1)), $$

which implies the desired result.

- Let $\langle n \rangle_m = 10^{m-1}10^{2m-1}10^m \tilde{w}$. Since $(1 \ 1)M(m-1)M(2m-1)M(2m) = 13(1 \ 1)$ and the length of the word $\tilde{w}$ is $k - 5m - 1$, we have

$$ \mathrm{Max}(k) \leq 13\mathrm{Max}(k - 5m - 1) \leq 2^4\mathrm{Max}(k - 4(m + 1)), $$

which implies the desired result.

Note that Claim 5.8 is valid only for $m \geq 4$.

x = 0: Let us study the case $x = 0$. We have to consider $y \in \{m, 2m-1, 2m, 3m-1\}$.
* Let $\langle n \rangle_m = 10^m w$. Since $(1\ 1)M(m) = 2(1\ 1)$, we have $\text{Max}(k) = 2\text{Max}(k - (m+1))$, what was to be proved.

* Let $\langle n \rangle_m = 10^y w$, where $y \in \{2m-1, 2m, 3m-1\}$. In this case the complement of $n$ has the greedy expansion $\langle \bar{n} \rangle_m = 10^{m-1}\tilde{w}$ or $10^m\tilde{w}$, where $\tilde{w}$ is a greedy expansion of an integer. Such cases were already discussed before. Since $R^{(m)}(n) = R^{(m)}(\bar{n})$, the case is solved.

This completes the proof for $m \ge 4$. Recall that the assumption $m \ge 4$ was used at one point of the discussion. For $m=3$ we have to consider $\langle n \rangle_m = 10^{m-1}10^{2m-1}10^{2m-1}\tilde{w} = 10^210^510^5\tilde{w}$. The discussion splits into cases according to the prefix of $\tilde{w}$. Necessarily, $\tilde{w} = (10^5)^k 10^{r_i} \cdots 10^{r_1}$ for some $k \ge 0$, $r_i \ne 5$. Since it has been shown that $r_1 \in \{3, 6\}$, we must have $i \ge 1$.

If $r_i = 3$, then $\langle n \rangle_3$ contains the string $10^510^510^3$. The corresponding matrix is $M(5)M(5)M(3) = \binom{8}{5} = 8$ which is majored by $\binom{8}{8} = M(3)M(3)M(3)M(3)$ corresponding to the string $10^310^310^310^3$ of the same length as $10^510^510^3$. Thus $10^510^510^3$ is forbidden for maximality.

If $r_i = 6$, then $\langle n \rangle_3$ contains the string $10^510^510^6$. The corresponding matrix is $M(5)M(5)M(6) = \binom{13}{8} = 13$ which is majored by $\binom{16}{8} = M(6)M(3)M(3)M(3)$ corresponding to the string $10^610^310^310^3$ of the same length as $10^510^510^6$. Thus $10^510^510^6$ is forbidden for maximality.

If $r_i = 8$, then $\langle n \rangle_3$ contains the string $10^510^8$. The corresponding matrix is $M(5)M(8) = \binom{7}{4} = 7$ which is majored by $\binom{8}{4} = M(6)M(3)M(3)$ corresponding to the string $10^610^310^3$ of the same length as $10^510^8$. Thus $10^510^8$ is forbidden for maximality.

Last, if $r_i = 2$, then $\langle n \rangle_3$ contains the string $10^2(10^5)^j10^2$ for some $j \ge 2$. The corresponding matrix is $M(2)M^2(5)M(2) = \binom{F_{2j} F_{2j-1}}{F_{2j-1} F_{2j-2}}$ which is majored by $\binom{F_{2j+2} F_{2j+1}}{F_{2j+1} F_{2j}} = M^{j+1}(5)$ corresponding to the string $(10^5)^{j+1}$ of the same length as $10^2(10^5)^j10^2$. Thus $10^2(10^5)^j10^2$ is forbidden for maximality. $\square$

# 6 Comments and open problems

Although the numeration systems related to $m$-Bonacci numbers have been extensively studied from many different points of view, there remains a number of problems to be explored, even in the most simple Fibonacci case $m=2$.

One of these problems is to find a closed formula for the sequence $A(n)$ giving the least integer having $n$ representations as sums of distinct Fibonacci numbers, which is a sort of inverse to the function $R^{(2)}(n)$. Some results about $A(n)$ are given in [3, 4]. However, according to our knowledge, analogous function for $m$-Bonacci numeration system has never been studied.

Another interesting question related to $R^{(2)}$ is the function $rk(n)$ defined in [5], counting the number of occurrences of a value $n$ among numbers $R^{(2)}(F_k)$, $R^{(2)}(F_k+1)$, ..., $R^{(2)}(F_{k+1}-1)$ for sufficiently large $k$. The authors of [5] show that the function is well defined, give a recurrent formula using the Euler function and exact value for $n$ prime. The function $rk(n)$ illustrates the exceptionality of the Fibonacci case $m=2$, because similar function cannot be defined if $m \ge 3$. We have already seen that the number of occurrences of the value $R^{(m)}(n) = 1$ among $R^{(m)}(F_k)$, $R^{(m)}(F_k+1)$, ..., $R^{(m)}(F_{k+1}-1)$ increases with $k$ to infinity. Similarly, it can be shown for other values $R^{(m)}(n)$.

The literature often concentrates on the study of ambiguity in generalized Fibonacci numeration systems, where one allows coefficients only in $\{0, 1\}$. When omitting the limitation on
the coefficients, the problem becomes much more difficult. Even in case of the usual Fibonacci
system, no compact formula is known for the so-called Fibagonci sequence ($B(n)$)$_{n \in \mathbb{N}}$ counting
the number of representations of $n$ as sum of (possibly repeating) Fibonacci numbers.

One can also ask the question about numeration systems which allow coefficients ≥ 2 even in the greedy expansion of an integer. An example of these is the Ostrowski numeration system based on sequences defined by linear recurrences of second order with non-constant coefficients. Such numeration systems have been considered by Berstel [1] who shows that a formula similar to (5) is valid for counting the number of representations of *n*. Other properties of these numeration systems are to be explored.

Acknowledgements

The authors acknowledge partial support by Czech Science Foundation GA ČR 201/05/0169, and
by the grant LC06002 of the Ministry of Education, Youth, and Sports of the Czech Republic.

References

[1] J. Berstel, *An excercise on Fibonacci representations*, RAIRO Theor. Inf. Appl. **35** (2001) 491–498.

[2] M. Bicknell-Johnson, D. C. Fielder, *The number of representations of *N* using distinct Fibonacci numbers, counted by recursive formulas*, Fibonacci Quart. **37** (1999) 47–60.

[3] M. Bicknell-Johnson, *The least integer having *p* Fibonacci representations, *p* prime*, Fibonacci Quart. **40** (2002) 260–265.

[4] M. Bicknell-Johnson, *The smallest positive integer having $F_k$ representations as sums of distinct Fibonacci numbers*, in Applications of Fibonacci numbers **8** (1999) 47–52.

[5] M. Edson, L. Zamboni, *On representations of positive integers in the Fibonacci base*, Theoret. Comput. Sci. **326** (2004), 241–260.

[6] C. Frougny, *Fibonacci representations and finite automata*, IEEE Trans. Inform. Theory, **37** (1991), 393–399.

[7] P.J. Grabner, P. Kirschenhofer, R.F. Tichy, *Combinatorial and arithmetical properties of linear numeration systems*, Combinatorica **22** (2002), 245–267.

[8] P.J. Grabner, P. Liardet, R.F. Tichy, *Odometers and systems of numeration*, Acta Arith. **70** (1995), 103–123.

[9] L.J. Guibas, A.M. Odlyzko, *String overlaps, pattern matching, and nontransitive games*, J. Combin. Theory Ser. A **30** (1981), 208–220.

[10] W.H. Kautz, *Fibonacci codes for synchronization control*, IEEE Trans. Inform. Theory, **11** (1965), 284–292.

[11] P. Kocábová, Z. Masáková, E. Pelantová, *Integers with a maximal number of Fibonacci representations*, RAIRO Theor. Inf. Appl. **39** (2005), 343–359.