Redundance in the Signed m-Bonacci Numeration System

Zuzana Masáková and Élise Vandomme Department of Mathematics FNSPE Czech Technical University in Prague Trojanova 13 120 00 Praha 2 Czech Republic

               zuzana.masakova@fjfi.cvut.cz

Abstract

We study redundance in the signed m-bonacci numeration system. We determine the number of representations of 0 in this system and describe the automaton accepting the language of such representations. We reveal a surprising connection between Fibonacci and Tribonacci numbers.

1 Introduction

Integers are usually represented as sums of powers of a base q ∈ ℕ for q ≥ 2. In particular, every x ∈ ℕ can be written as x = ∑_{j=1}^{n} a_{j}q^{j−1}. If a_{j} ∈ {0, 1, …, q − 1} and a_{n} ≠ 0, then such a representation of x is unique. One can replace the sequence (q^{j−1})_{j≥1} of powers of the base by any linear recurrence sequence (G_{j})_{j≥1}. For details about such representations for a general linear recurrence sequence (G_{j}) and conditions on uniqueness, see [?] or [?, Chapter 7].

Perhaps the first example of a possibility of representing integers in these so-called linear numeration systems is the well-known Zeckendorf numeration system [?], where for (G_{j}) we take the sequence of Fibonacci numbers G_{j} = F_{j}, where F_{1} = 1, F_{2} = 2, F_{j+2} = F_{j+1} + F_{j} for j ≥ 1. The representation of an integer x in the form x = ∑_{j=1}^{n} a_{j}F^{j} is unique if a_{j} ∈ {0, 1} where a_{j} · a_{j−1} = 0, i.e., the sequence of coefficients does not contain consecutive 1’s. This representation can be obtained by the greedy algorithm. Relaxing the condition on consecutive 1’s, the system becomes redundant even with the alphabet of digits {0, 1}. The function R(n) expressing the number of representations of n ∈ ℕ has been studied by several authors. Berstel [?] provided a formula for calculating R(n) based on the greedy representation of n. A different way of computation was given by Edson and Zamboni [?]. Kocábová et al. [?] and Stockmeyer [?] studied the function R(n) in more detail.

A similar study was performed for different linear recurrence sequences [?]. The m-bonacci sequence as a natural generalization of the Fibonacci case m = 2 was considered by Kocábová et al. [?] and Edson and Zamboni [?]. Second-order linear recurrences were studied by Edson [?]. In all these cases, the alphabet of digits was chosen to be the minimal one allowing representation of every integer. In the case of the m-bonacci system, this means the alphabet {0, 1}.

One can extend the study even more, to considering redundance when the alphabet contains more than the necessary number of digits. Considering such representations may have practical consequences, e.g., for the possibility to define algorithms for parallel addition or algorithms for fast multiplication using non-adjacent form or representations of minimal weight. Parallel addition for a numeration system with integer base q ≥ 3 was given by Avizienis [?]. For a signed binary system (with the alphabet {−1, 0, 1}), the algorithm was described by Chow and Robertson [?]. An algorithm for parallel addition in the Fibonacci system with alphabet {−1, 0, 1} was given by Frougny et al. [?]. Minimal weight expansions were studied, for example, by Heuberger [?] and Grabner [?]. Similar questions are examined by Frougny and Steiner [?] in systems with real algebraic base β which are directly connected to linear numeration systems [?].

In this paper we study the linear numeration system based on the m-bonacci sequence over the alphabet of digits {−1, 0, 1}. We show that the number r(k) of representations of 0 in the m-bonacci system over {−1, 0, 1} of length at most k is also a linear recurrence sequence and we determine the corresponding recurrence of order m + 1. The proof of this result uses the m-bonacci numeration system with the alphabet {0, 1, 2}. We also present the automaton accepting precisely the representations of 0 over {−1, 0, 1}.

2 Representations

Definition 1. Let m ∈ ℕ with m ≥ 2. Let (T_{k})_{k≥1} denote the m-bonacci sequence defined by

T_{k} = 2^{k−1} for k ∈ {1, …, m} and T_{k} = ∑_{j=1}^{m} T_{k−j} for k > m.

Definition 2. Let A ⊂ ℕ be an alphabet. A positive integer n is represented by (a_{ℓ}a_{ℓ−1} ⋯ a_{1}) if n = ∑_{j=1}^{ℓ} a_{j}T_{j} with a_{j} ∈ A and a_{ℓ} ≠ 0. In that case, ℓ is the length of the representation. The number n represented by (a_{ℓ}a_{ℓ−1} ⋯ a_{1}) is called the value of (a_{ℓ}a_{ℓ−1} ⋯ a_{1}) and is denoted by val(a_{ℓ}a_{ℓ−1} ⋯ a_{1}). Let p_{A}(n) denote the number of representations of n over the alphabet A and by p_{A}(n, i) the number of representations of n of length exactly i over the alphabet A. If the alphabet is clear from the context, we simply write p(n) and p(n, i).

Our aim is to enumerate the representations of 0 in the m-bonacci system with the alphabet B = {−1, 0, 1}. Conveniently, we transfer the question to determine the number of representations in the system with the alphabet A = {0, 1, 2} of the number N_{k}, where (N_{k})_{k≥1} is the running sum of the sequence (T_{k})_{k≥1}, i.e.,

N_{k} = ∑_{j=1}^{k} T_{j} for k ≥ 1.

We set N_{0} := 0. In fact, adding 1 to every digit in a representation of 0 over B = {−1, 0, 1} of length k, we obtain a representation of N_{k} over the alphabet A = {0, 1, 2}. The exact relation of the two systems with alphabets A and B is explained in Section 4.

First, let us present some computer calculations of p(N_{k}) for the m-bonacci system with m = 2, 3, 4, and 5. We count the number of representations of N_{k} in the m-bonacci numeration system using the alphabet A = {0, 1, 2}.

\begin{aligned}& m = 2 \\ N_{i} & p(N_{i}) \\ 1 & 1 \\ 3 & 2 \\ 6 & 4 \\ 11 & 7 \\ 19 & 13 \\ 32 & 24 \\ 53 & 44 \\ 87 & 81 \\ 142 & 149 \\ 231 & 274 \\ 375 & 504 \\ 608 & 927 \\ 985 & 1705 \\ 1595 & 3136 \\ 2582 & 5768 \\ 4179 & 10609 \\ 6763 & 19513 \\ 10944 & 35890 \\ 17709 & 66012 \\ 28655 & 121415 \end{aligned}  \begin{aligned}& m = 3 \\ N_{i} & p(N_{i}) \\ 1 & 1 \\ 3 & 1 \\ 7 & 2 \\ 14 & 4 \\ 27 & 6 \\ 51 & 9 \\ 95 & 15 \\ 176 & 25 \\ 325 & 40 \\ 599 & 64 \\ 1103 & 104 \\ 2030 & 169 \\ 3735 & 273 \\ 6871 & 441 \\ 12639 & 714 \\ 23248 & 1156 \\ 42761 & 1870 \\ 78651 & 3025 \\ 144663 & 4895 \\ 266078 & 7921 \end{aligned}  \begin{aligned}& m = 4 \\ N_{i} & p(N_{i}) \\ 1 & 1 \\ 3 & 1 \\ 7 & 1 \\ 15 & 2 \\ 30 & 4 \\ 59 & 6 \\ 115 & 8 \\ 223 & 11 \\ 431 & 17 \\ 832 & 27 \\ 1605 & 41 \\ 3095 & 60 \\ 5967 & 88 \\ 11503 & 132 \\ 22174 & 200 \\ 42743 & 301 \\ 82391 & 449 \\ 158815 & 669 \\ 306127 & 1001 \\ 590080 & 1502 \end{aligned}  \begin{aligned}& m = 5 \\ N_{i} & p(N_{i}) \\ 1 & 1 \\ 3 & 1 \\ 7 & 1 \\ 15 & 1 \\ 31 & 2 \\ 62 & 4 \\ 123 & 6 \\ 243 & 8 \\ 479 & 10 \\ 943 & 13 \\ 1855 & 19 \\ 3648 & 29 \\ 7173 & 43 \\ 14103 & 61 \\ 27727 & 84 \\ 54511 & 116 \\ 107167 & 164 \\ 210686 & 236 \\ 414199 & 340 \\ 814295 & 485 \end{aligned}

Remark 3. Note the surprising fact in the column of results for the case m = 2: The number of representations of N_{k} = ∑_{j=1}^{k} F_{j} = F_{k+2} − 2 is equal to the k-th Tribonacci number T_{k}. This observation was first made by Vlašic [?]. This statement is included in Proposition 4 as the case m = 2.

3 Representations in the m-bonacci system over {0, 1, 2}

Proposition 4. Let A = {0, 1, 2}, k, m ∈ ℕ with m ≥ 2 and k ≥ 1. The number p(N_{k}) of representations of N_{k} in the m-bonacci numeration system over the alphabet A satisfies the recurrence relation

p_{A}(N_{k}) = p_{A}(N_{k−1}) + p_{A}(N_{k−m}) + p_{A}(N_{k−m−1}) for k > m + 1  (1)

with p_{A}(N_{k}) = 1 for k ∈ {0, …, m − 1}, p_{A}(N_{m}) = 2 and p_{A}(N_{m+1}) = 4.

The proof of this result relies on the following lemma.

Lemma 5. Let k ∈ ℕ. The following inequalities hold:

N_{k} < T_{k} + T_{k+1} ≤ T_{k+2} for k ≥ 1,  (2)
2N_{k−2} < N_{k} for k ≥ 3,  (3)
N_{k} < 2T_{k+1} for k ≥ 1.  (4)

Proof. For the first inequality, we proceed by induction. It is easy to check that N_{1} < T_{1} + T_{2} ≤ T_{3}. Let k ≥ 2 and assume the results hold for k − 1. We have by definition and induction hypothesis that N_{k} = T_{k} + N_{k−1} < T_{k} + T_{k+1} ≤ T_{k+2}.

All the other inequalities follow from the first one. For the second inequality with k ≥ 3, we have

N_{k} = T_{k} + T_{k−1} + N_{k−2} > N_{k−2} + T_{k−1} + N_{k−2} > 2N_{k−2}.

For the last inequality, we just note that T_{k} < T_{k+1} for all k ≥ 1.

Proof of Proposition 4. First note that (2) and (3) imply that every representation of N_{k} has length in {k − 1, k, k + 1}. So

p(N_{k}) = p(N_{k}, k + 1) + p(N_{k}, k) + p(N_{k}, k − 1) for k ≥ 1.  (5)

Obviously, by definition of N_{k}, (1^{k}) is one of the representations of N_{k}.

We first take care of the initial conditions. For k ∈ {1, …, m − 1}, the number N_{k} = 2^{k} − 1 has a unique representation that is (1^{k}). For k = m, we have N_{m} = 2^{m} − 1 = T_{m+1}. Therefore, N_{m} can be represented only by (1^{m}) or (10^{m}). Finally, for k = m + 1, we can use the m-bonacci recurrence to write

N_{m+1} = ∑_{j=1}^{m+1} T_{j} = T_{m+2} + T_{1} = 2T_{m+1} = 2 ∑_{j=1}^{m} T_{j}.

Thus the representations of N_{k+1} are four, namely (1^{m+1}), (10^{m}1), (20^{m}), and (2^{m}). It is easy to check that these are the only ones. We can summarize it in Table 1.

For k ≥ m + 2, we will distinguish three cases according to the possible lengths of the representations.

\begin{matrix}k & p(N_{k}) & p(N_{k}, k + 1) & p(N_{k}, k) & p(N_{k}, k − 1) \\ 1 & 1 & 0 & 1 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ m − 1 & 1 & 0 & 1 & 0 \\ m & 2 & 1 & 1 & 0 \\ m + 1 & 4 & 1 & 2 & 1 \end{matrix}

Table 1: Initial conditions for the sequences p(N_{k}), p(N_{k}, k + 1), p(N_{k}, k), and p(N_{k}, k − 1).

Case 1: consider the representations (a_{k+1} ⋯ a_{1}) of N_{k} of length k + 1 and assume k ≥ m. In that case, a_{k+1} ≠ 2 because otherwise N_{k} = val(2a_{k} ⋯ a_{1}) ≥ 2T_{k+1}, which is in contradiction with (4). So a_{k+1} = 1 and val(a_{k} ⋯ a_{1}) = N_{k} − T_{k+1} = N_{k} − ∑_{j=0}^{m−1} T_{k−j} = N_{k−m}. This means that p(N_{k}, k + 1) is equal to the number of representations of N_{k−m} of length at most k. Since k − m + 1 < k, this number is equal to p(N_{k−m}). Thus

p(N_{k}, k + 1) = p(N_{k−m}) for k ≥ m.  (6)

Case 2: consider the representations (a_{k} ⋯ a_{1}) of N_{k} of length k and assume k ≥ m + 1. If a_{k} = 2, then val(a_{k−1} ⋯ a_{1}) = N_{k} − 2T_{k} = N_{k−m−1}. The number of such representations is equal to the number of representations of N_{k−m−1}, and since k−m < k−1, this is equal to p(N_{k−m−1}). If a_{k} = 1, then val(a_{k−1} ⋯ a_{1}) = N_{k}−T_{k} = N_{k−1}. So the number of such representations is equal to p(N_{k−1}, k−1)+p(N_{k−1}, k−2). In conclusion, we get

p(N_{k}, k) = p(N_{k−m−1}) + p(N_{k−1}, k − 1) + p(N_{k−1}, k − 2)
= p(N_{k−m−1}) + p(N_{k−1}) − p(N_{k−1}, k).

Since k ≥ m + 1, we can use (6) to obtain p(N_{k−1}, k) = p(N_{k−m−1}) and thus

p(N_{k}, k) = p(N_{k−1}) for k ≥ m + 1.  (7)

Case 3: consider the representations (a_{k−1} ⋯ a_{1}) of N_{k} of length k − 1 and assume k ≥ m+2. We have a_{k−1} = a_{k−2} = ⋯ = a_{k−m+1} = 2. Indeed, let ℓ ∈ {1, …, m−1}. If the prefix of length ℓ − 1 of the representation is a concatenation of 2’s (i.e., a_{k−1} = ⋯ = a_{k+1−ℓ} = 2), then a_{k−ℓ} = 2. Otherwise, a_{k−ℓ} is equal to 1 or 0 and

2N_{k−ℓ−1} ≥ val(a_{k−ℓ−1} ⋯ a_{1}) = N_{k} − 2 ∑_{j=1}^{ℓ−1} T_{k−j} − a_{k−ℓ}T_{k−ℓ} ≥

≥ N_{k} − 2 ∑_{j=1}^{ℓ−1} T_{k−j} − T_{k−ℓ} = N_{k−ℓ−1} + T_{k} − ∑_{j=1}^{ℓ−1} T_{k−j} =

= N_{k−ℓ−1} + ∑_{j=k−m}^{k−ℓ} T_{j} > 2N_{k−ℓ−1}

which is a contradiction. Note that for the last inequality we have used (2) which is justified since k − ℓ − 1 ≥ k − m ≥ 2.

So the representation of N_{k} is of the form (a_{k−1} ⋯ a_{1}) = (2^{m−1}a_{k−m} ⋯ a_{1}) and

val(a_{k−m} ⋯ a_{1}) = N_{k} − 2 ∑_{j=k−m+1}^{k−1} T_{j} = N_{k−m} + T_{k} − ∑_{j=1}^{m−1} T_{k−j} = N_{k−m} + T_{k−m}.

If a_{k−m} = 2, then val(a_{k−m−1} ⋯ a_{1}) = N_{k−m−1}. The number of representations of N_{k} of this form is p(N_{k−m−1}, k − m − 1) + p(N_{k−m−1}, k − m − 2). If a_{k−m} = 1, then val(a_{k−m−1} ⋯ a_{1}) = N_{k−m}, and the number of corresponding representations is p(N_{k−m}, k − m − 1). Finally, a_{k−m} = 0 is not possible because it would imply

2N_{k−m−1} ≥ val(a_{k−m−1} ⋯ a_{1}) = N_{k−m} + T_{k−m} = N_{k−m−1} + 2T_{k−m}

which is in contradiction with (4). Here we use that k − m − 1 ≥ 1 from the assumption. Putting everything together, we obtain

\begin{matrix}p(N_{k}, k−1) = & p(N_{k−m−1}, k−m−1) + p(N_{k−m−1}, k−m−2) + p(N_{k−m}, k−m−1) \\ = & p(N_{k−m−1}) − p(N_{k−m−1}, k−m) + p(N_{k−m}, k−m−1). \end{matrix}

(8)

Now suppose that k ∈ {m+2, …, 2m}. Then 1 ≤ k−m−1 ≤ m−1 and from the initial conditions in Table 1 we have p(N_{k−m−1}, k−m) = 0 and p(N_{k−m}, k−m−1) = 0. It follows from (8) that p(N_{k}, k − 1) = p(N_{k−m−1}). With (6) and (7), it implies that

p(N_{k}) = p(N_{k−1}) + p(N_{k−m}) + p(N_{k−m−1}) for k ∈ {m + 2, …, 2m}.  (9)

Now assume that k > 2m. Using (6) and (7) we deduce from (8) that

p(N_{k}, k − 1) = p(N_{k−m−1}) − p(N_{k−m−1}, k − m)+
+ p(N_{k−m}) − p(N_{k−m}, k − m + 1) − p(N_{k−m}, k − m) =
= p(N_{k−m−1}) − p(N_{k−2m−1}) + p(N_{k−m}) − p(N_{k−2m}) − p(N_{k−m−1})
= p(N_{k−m}) − p(N_{k−2m}) − p(N_{k−2m−1}).

Therefore, for k > 2m, we have

p(N_{k}) = p(N_{k−1}) + p(N_{k−m}) + p(N_{k−m}) − p(N_{k−2m}) − p(N_{k−2m−1}).

To conclude the argument, an easy induction on k shows the claim

p(N_{k}) = p(N_{k−1}) + p(N_{k−m}) + p(N_{k−m−1}) for k > m + 1,

since the base cases are treated in (9).

4 Representations of zero in the signed m-bonacci system

We are interested in the representations of 0 over the balanced alphabet B = {−1, 0, 1}. We let Z denote the set of such representations. For a fixed k ≥ 1,

\begin{matrix}i \\ v_{1} \\ u_{1} \\ v_{2} \\ u_{2} \\ 0 \\ 1 \\ −1 \\ −1 \\ 1 \\ −1 \\ 0 \\ 1 \\ 0 \end{matrix}

Figure 1: Automaton accepting representations of 0 over the alphabet {−1, 0, 1} in the Fibonacci numeration system.

we further let Z_{k} denote the set of representations of 0 of length at most k. Let us describe the number of such representations, i.e., r(k) = #Z_{k}. In order to determine r(k) for k ≥ 2m + 1, let us present the correspondence between the m-bonacci numeration systems with the alphabet of digits A = {0, 1, 2} and B = {−1, 0, 1} and then derive the recurrence for the sequence (r(k))_{k≥1}.

Proposition 6. Let A = {0, 1, 2} and B = {−1, 0, 1}, k, m ∈ ℕ with m ≥ 2 and k ≥ 1. The number r(k) of representations of 0 of length at most k in the m-bonacci numeration system over the alphabet B is given by

r(k) = ∑_{j=0}^{k} p_{B}(0, j) = p_{A}(N_{k}) − p_{A}(N_{k−m}) = p_{A}(N_{k−1}) + p_{A}(N_{k−m−1}) for k ≥ m + 1

and r(k) = p_{A}(N_{k}) = 1 for k ∈ {0, …, m}.

Proof. Any representation (b_{k} ⋯ b_{1}) of 0 over B = {−1, 0, 1} (with possible leading zeros) is in one-to-one correspondence with a representation (a_{k} ⋯ a_{1}) of N_{k} of length at most k over the alphabet A = {0, 1, 2}, setting a_{j} = b_{j} +1 for j = 1, …, k. By (5), we have r(k) = p_{A}(N_{k}, k)+p_{A}(N_{k}, k−1) = p_{A}(N_{k})−p_{A}(N_{k}, k+1). Using (6), we have r(k) = p_{A}(N_{k}) − p_{A}(N_{k−m}). The last equality in the statement of the proposition follows from the recurrence on p_{A}(N_{k}).

Corollary 7. The number r(k) of representations of 0 of length at most k in the m-bonacci numeration system over the alphabet B = {−1, 0, 1} satisfies

r(k) = r(k − 1) + r(k − m) + r(k − m − 1) for k ≥ m + 1  (10)

and r(k) = 1 for k ∈ {0, …, m}.

Remark 8. For further use, let us determine a set of initial values of the sequence (r(k))_{k≥0}. Obviously, the only representation of zero of length k ≤ m is (0^{k}), which is in accordance with the initial conditions of the recurrence (10). If k = m + 1, we have, besides the representation (0^{m+1}) also (1¯1^{m}) and (¯11^{m}), where we use ¯1 for −1 for lucidity of notation. We have r(m + 1) = 3 = r(m) + r(1) + r(0). For m + 2 ≤ k ≤ 2m we have from (10) that r(k) = r(k − 1) + 2, i.e., r(m + j) = 2j + 1 for j = 1, …, m.

An automaton accepting the representations of zero in the signed Fibonacci numeration system (m = 2, digits −1, 0, 1) was described by Frougny [?, Chap. 7];

\begin{matrix}i \\ v_{1} \\ v_{2} \\ v_{m−1} \\ v_{m} \\ u_{1} \\ u_{2} \\ u_{m−1} \\ u_{m} \\ 0 \\ 1 \\ −1 \\ −1 \\ −1 \\ 1 \\ 1 \\ −1 \\ 0 \\ 1 \\ 0 \end{matrix}

Figure 2: Automata accepting representations of 0 over the alphabet {−1, 0, 1} in the m-bonacci numeration system with m ≥ 2.

see Figure 1. The number of representations of 0 of length at most k is exactly the number of representations with k symbols where we allow leading zeros. Hence it corresponds to the number of length-k accepting paths in the automaton.

Here, we present an automaton recognizing representations of zero in the signed m-bonacci numeration system for m ≥ 2.

Proposition 9. Let A = (Q, B, δ, I, T) be a deterministic finite automaton with the set of states Q = {i, u_{1}, …, u_{m}, v_{1}, …, v_{m}}, alphabet B = {−1, 0, 1}, the set of initial and terminal states I = T = {i}. Define the transition function δ : Q×{−1, 0, 1} → Q,

\begin{matrix}(i, 0) & ↦ i, (i, −1) ↦ u_{1}, (i, 1) ↦ v_{1} \\ (u_{j}, 1) & ↦ u_{j+1}, (u_{m}, 0) ↦ u_{1}, (u_{m}, 1) ↦ i \\ (v_{j}, −1) & ↦ v_{j+1}, (v_{m}, 0) ↦ v_{1}, (v_{m}, −1) ↦ i, \end{matrix}

see Figure 2. Then A recognizes precisely the representations of 0 in the m-bonacci numeration system over the alphabet B.

In order to justify that the accepting paths correspond precisely to the representations of 0, we study the adjacency matrix 𝔸 of the automaton A. In an adjacency matrix of the automaton, the element 𝔸_{j,k} is defined as 1 if there is an edge from the state j to the state k, and 0 otherwise. Fixing the ordering of states of A from 1 to 2m + 1 as {i, u_{1}, …, u_{m}, v_{1}, …, v_{m}}, we have

𝔸 = (\begin{matrix}1 & v^{T} & v^{T} \\ u & C & O \\ u & O & C \end{matrix} ) ,

where v^{T} = (10 … 0) ∈ ℤ^{m}, u^{T} = (0 … 01) ∈ ℤ^{m}, O ∈ ℤ^{m×m} is the zero matrix and

C = (\begin{matrix}0 & 1 & 0 & ⋯ & 0 \\ 0 & 0 & 1 & & ⋮ \\ ⋮ & & ... & & 0 \\ 0 & & & 0 & 1 \\ 1 & 0 & ⋯ & 0 & 0 \end{matrix}) ∈ ℤ^{m×m}

is the companion matrix of the polynomial x^{m} − 1.

Lemma 10. The characteristic polynomial of 𝔸 is equal to

f(x) = (x^{m} − 1)(x^{m+1} − x^{m} − x − 1) = x^{2m+1} − x^{2m} − 2x^{m+1} + x + 1.

Proof. For the computation of the characteristic polynomial f(x) = − det(𝔸 − xI), we use the following statement about determinants of block matrices [?].

Let E, F, G, H be complex matrices of dimensions p × p, p × q, q × p, q × q, with

H invertible. Then for the determinant of (\begin{matrix}E & F \\ G & H \end{matrix}) we have

det (\begin{matrix}E & F \\ G & H \end{matrix}) = det(E − F H^{−1}G) det(H) .  (11)

We use the statement (11) in two steps. First set

E = (\begin{matrix}1 − x & v^{T} \\ u & H \end{matrix} ) , F = (\begin{matrix}v^{T} \\ O \end{matrix} ) , G = (u O) ,

H = C − xI = (\begin{matrix}−x & 1 & 0 & ⋯ & 0 \\ 0 & −x & 1 & & ⋮ \\ ⋮ & & ... & & 0 \\ 0 & & & −x & 1 \\ 1 & 0 & ⋯ & 0 & −x \end{matrix}) .

Note that det(H) = (−1)^{m}(x^{m} − 1). Also note that the product F H^{−1}G = (h_{j,k}) ∈ ℤ^{(m+1)×(m+1)} is a matrix that is null everywhere except for c_{1,1} = h_{1,m} with (h_{j,k}) = H^{−1} = det(H)^{−1}adj(H) where adj(H) is the adjugate matrix. Since the adjugate matrix is computed as the transpose of the cofactor matrix, we have

c_{1,1} = h_{1,m} = \frac{1}{(−1)^{m}(x^{m} − 1)}(−1)^{m+1} det (\begin{matrix}1 & 0 & … & 0 \\ −x & 1 & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ 0 & … & −x & 1 \end{matrix}) = \frac{−1}{x^{m} − 1} .

At this stage, we have

det(𝔸 − xI) = det(E − F H^{−1}G) det(H) = det(H) det (\begin{matrix}1 − x − c_{1,1} & v^{T} \\ u & H \end{matrix} ) .

We use (11) again, with redefined blocks E, F, G, E = (1−x−c_{1,1}), namely F = v^{T}, G = u. Realizing that F H^{−1}G = (c_{1,1}), we derive

\begin{aligned}−f(x) & = det(𝔸 − xI) = det(H)^{2}(1 − x − 2c_{1,1}) = \\ & = (x^{m} − 1)^{2}(1 − x − \frac{−2}{x^{m} − 1}) = −(x^{m} − 1)(x^{m+1} − x^{m} − x − 1), \end{aligned}

which proves the lemma.

Let us now demonstrate that the automaton presented in Figure 2 recognizes precisely the representations of 0 in the m-bonacci system over the alphabet B = {−1, 0, 1}.

Proof of Proposition 9. The language accepted by the automaton A depicted in Figure 2 can be described by the regular expression

0^{∗}(1(¯1^{m−1}0)^{∗}¯1^{m} + ¯1(1^{m−1}0)^{∗}1^{m})^{∗}0^{∗}

It can be directly checked with the use of the m-bonacci recurrence that every word of the above form corresponds to a representation of 0 in the sense of Definition 2. For every fixed k we thus have L_{k}(A) ⊆ Z_{k}. In order to check the opposite inclusion, it suffices to show that

#L_{k}(A) = #Z_{k} = r(k).

Consider the adjacency matrix 𝔸 of the automaton A. An accepting path in the automaton is a path both starting and ending in the initial state i. The number of such paths of length k, say s(k), is equal to (𝔸^{k})_{11}. We thus have s(k) := #L_{k}(A) = (𝔸^{k})_{11}. We will show that s(k) = r(k) by verifying that both sequences satisfy the same linear recurrence of order 2m + 1 with the same initial conditions s(j) = r(j) for j = 0, …, 2m.

The characteristic polynomial f of the matrix 𝔸 is computed in Lemma 10. By the Cayley-Hamilton theorem, we have

f(𝔸) = 𝔸^{2m+1} − 𝔸^{2m} − 2𝔸^{m+1} + 𝔸 + I = O,

where I, O ∈ ℤ^{(2m+1)×(2m+1)} are the identity and zero matrix, respectively. Multiplying the above by 𝔸^{k} for k ≥ 0, and considering the sequence s(k) = (𝔸^{k})_{11}, we have

s(k + 2m + 1) − s(k + 2m) − 2s(k + m + 1) + s(k + 1) + s(k) = 0 for k ≥ 0.

Let us verify that the sequence r(k) satisfies the same recurrence. From Corollary 7 we have for k ≥ 0 that

\begin{aligned}r(k + m + 1) − r(k + m) − r(k + 1) − r(k) & = 0, \\ r(k + 2m + 1) − r(k + 2m) − r(k + m + 1) − r(k + m) & = 0. \end{aligned}

Subtracting the two, we obtain

r(k + 2m + 1) − r(k + 2m) − 2r(k + m + 1) + r(k + 1) + r(k) = 0 for k ≥ 0,

as desired. The initial values r(0), …, r(2m) are determined in Remark 8 as r(j) = 1 for 0 ≤ j ≤ m and r(j + m) = 2j + 1 for 0 ≤ j ≤ m. It remains to determine s(0), …, s(2m). For that, we check directly the automaton A. We see that s(k) = r(k) for 0 ≤ k ≤ 2m which implies that s(k) = r(k) for every k ≥ 0.