1. Introduction

Let \(a_1,\dots,a_d\) be positive integers satisfying the condition

$$a_1\ge a_2\ge\dotsb\ge a_{d-1}\ge a_d=1.$$

Define a sequence \(\{T_n\}\) using a linear recurrent relation

$$T_n=a_1T_{n-1}+a_2T_{n-2}+\dotsb+a_dT_{n-d}.$$

The initial conditions have the form

$$T_0=1,\qquad T_n=1+a_1T_{n-1}+a_2T_{n-2}+\dotsb+a_nT_0$$

for \(n<d\). In this case, any positive integer \(N\) admits a unique greedy expansion with respect to the sequence \(\{T_n\}\) [1]:

$$N=\sum_{k=0}^{m(N)}\varepsilon_k(N)T_k. $$
(1.1)

The expansion (1.1) being greedy means that the inequalities \(0\le N-\sum_{k=m_1}^{m(N)}\varepsilon_k(N)T_k<T_{m_1}\) hold for any \(m_1<m(N)\).

Define the sets

$$\mathscr N_0 =\biggl\{n\colon\sum_{k=0}^{m(N)}\varepsilon_k(N)\equiv 0 \ (\operatorname{mod}2)\biggr\}, \qquad \mathscr N_1 =\biggl\{n\colon\sum_{k=0}^{m(N)}\varepsilon_k(N)\equiv 1\ (\operatorname{mod}2)\biggr\}$$

of positive integers with a given parity of the sum of the digits of the expansion with respect to the sequence \(\{T_n\}\).

Let

$$T_{i,j}(X)=\sharp\bigl\{n\le X\colon n\in\mathscr N_i,\,n+1\in\mathscr N_j\bigr\}.$$

Our objective is to prove the following theorem.

Theorem 1.

There exist effectively computable \(\lambda\) , \(0<\lambda<1\) , and \(C_{ij}\) ( \(C_{00}=C_{11}=-C_{10}=-C_{01}\) ) such that

$$T_{i,j}(X)=\biggl(\frac{1}{4}+C_{ij}\biggr)X+O(X^\lambda).$$

An explicit formula for the constants \(C_{ij}\) is rather complicated and is given below.

For the special case in which \(\{T_n\}\) is a Fibonacci sequence (\(d=2\), \(a_1=a_2=1\)), this problem was considered in [2], [3], where it was shown in two different ways that, in this case,

$$\begin{aligned} \, T_{i,j}(X)&=\frac{\sqrt{5}}{10}\,X+O(\log X) \qquad\text{for}\quad i=j, \\ T_{i,j}(X)&=\frac{5-\sqrt{5}}{10}\,X+O(\log X) \qquad\text{for}\quad i\ne j. \end{aligned}$$

It should also be noted that, in [4], [5], an analog of this problem for the binary number system was considered.

2. Auxiliary Results

In this section, we present some auxiliary results concerning expansions with respect to a sequence \(\{T_n\}\). Some of them are of independent interest.

Let us first obtain a bound for \(m(N)\). The following assertion holds [6, Theorem 2].

Proposition 1.

Let \(a_1,\dots,a_d\) be positive integers satisfying the condition

$$a_1\ge a_2\ge\dotsb\ge a_{d-1}\ge a_d.$$

Then the root \(\beta\) with the greatest absolute value of the equation

$$x^d-a_1x^{d-1}-a_2x^{d-2}-\dotsb-a_d=0 $$
(2.1)

is real, and \(\beta>1\). The absolute value of all other roots of equation (2.1) is less than 1. In other words, \(\beta\) is a Pisot number. Moreover, if \(T_\beta(x)=\beta x\ (\operatorname{mod}1)\) and \(d(1,\beta)=t_1t_2\dots\), where \(t_k=\lfloor\beta T_\beta^{k-1}(1)\rfloor\), and the process is terminated if zero is obtained at the next step, then \(d(1,\beta)=a_1\dotsb a_d\).

Note also that, in the proof of Theorem 2 in [6], it was also shown that (2.1) is the minimal polynomial for \(\beta\) under consideration. This implies that, to different linear recurrent sequences of the class under consideration, there correspond different \(\beta\).

Using the standard theory of linear recurrence relations with constant coefficients, we immediately obtain an asymptotic formula for \(T_n\).

Corollary 1.

The following asymptotic formula holds:

$$T_n\sim c\beta^n+O(1)$$

with some effectively computable constant \(c\ne 0\) .

This immediately implies a bound for \(m(N)\).

Corollary 2.

We have

$$m(N)=\log_\beta N+O(1).$$

By induction on \(n\), we can readily show that the inequality \(T_{n+1}<(a_1+1)T_n\) holds. In combination with the greedy condition of the expansion, this gives the bound \(\varepsilon_k(n)\le a_1\), \(0\le k\le m(N)\), for the coefficients of the expansion (1.1). Therefore, for every positive integer \(N\), the expansion (1.1) generates a finite word \(w(N)=\varepsilon_{m(N)}(N)\dotsb\varepsilon_0(N)\) over the alphabet \(\{0,1,\dots,a_1\}\). Obviously, not all finite words over the given alphabet are generated by greedy expansions of positive integers. We call the words generated by such expansions admissible.. We want to describe all admissible words.

Consider a graph containing \(d\) vertices labelled with the numbers \(0,1,\dots,d-1\). The edges of the graph have the following form:

  1. 1)

    \(a_1\) oriented loops at the vertex \(0\) that are labelled with the numbers from \(0\) to \(a_1-1\);

  2. 2)

    oriented edges from the vertex \(i\) to the vertex \(i+1\) that are labelled by the numbers \(a_{i+1}\);

  3. 3)

    \(a_{i+1}\) oriented edges from the vertex \(i\) to the vertex \(0\)

    labelled with the numbers from \(0\) to \(a_{i+1}-1\).

The construction of this graph was taken by us from the paper [7]. Denote the graph thus constructed by \(G(\beta)\). It has the following form.

To every finite path \(v_0\stackrel{c_{0}}{\longrightarrow}v_1\stackrel{c_{1}}{\longrightarrow}\dotsb \stackrel{c_{m-1}}{\longrightarrow}v_m\) in the graph \(G(\beta)\), one can assign the word \(c_0c_1\dotsb c_{m-1}\) composed of the labels of the path edges. The following assertion holds [7, Sec. 1.1], [8, Theorem 2.1 and Section 2.2].

Proposition 2.

The following assertions are equivalent:

  1. 1)

    a word \(w\) is admissible;

  2. 2)

    the word \(w\) is obtained from some path of the graph \(G(\beta)\) starting at the vertex 0;

  3. 3)

    every subword of the word \(w\) is lexicographically less than the word \(a_1\dotsb a_d\) .

3. Numbers with a specified ending of the expansion

Let \(w\) be an admissible word. Consider the set \(\mathbb N(w)\) of positive integers for which \(w(N)\) ends with the word \(w\). Let

$$N_w(X)=\sharp\bigl\{n\in\mathbb N\colon n\le X,\,n\in\mathbb N(w)\bigr\}.$$

In this section, we obtain an asymptotics for \(N_w(N)\).

The derivation of this asymptotics is based on the theory of generalized Rauzy tilings.

Let \(\beta^{(1)},\dots,\beta^{(r_1)}\) be the real conjugates to \(\beta\) and \(\beta^{(r_1+1)},\overline{\beta^{(r_1+1)}},\dots, \beta^{(r_1+r_2)}\), \(\overline{\beta^{(r_1+r_2)}}\) be the complex conjugates to \(\beta\).

Define the mapping \(\Phi\colon\mathbb N\to\mathbb R^{d-1}\) by the equality

$$\begin{aligned} \, \Phi(N) &=\biggl(\sum_{k=0}^{m(N)}\varepsilon_k(N)(\beta^{(1)})^k,\dots, \sum_{k=0}^{m(N)}\varepsilon_k(N)(\beta^{(r_1)})^k, \\ &\qquad\sum_{k=0}^{m(N)}\varepsilon_k(N)(\operatorname{Re}\beta^{(r_1+1)})^k, \sum_{k=0}^{m(N)}\varepsilon_k(N)(\operatorname{Im}\beta^{(r_1+1)})^k,\dots, \\ &\qquad\sum_{k=0}^{m(N)}\varepsilon_k(N)(\operatorname{Re}\beta^{(r_1+r_2)})^k, \sum_{k=0}^{m(N)}\varepsilon_k(N)(\operatorname{Im}\beta^{(r_1+r_2)})^k\biggr). \end{aligned}$$

The set

$$\mathscr T=\overline{\Phi(\mathbb N)}$$

is called the Rauzy fractal (the bar denotes the closure). The above construction of the Rauzy fractal was proposed in [9]; this is an analog of the construction of the Rauzy fractal used in [10] and based on greedy \(\beta\)-expansions of real numbers. The equivalence is shown in [9, Theorem 6].

Let \(\operatorname{Adm}_n(j)\) be the set of admissible words of length \(n\) for which the corresponding paths in the graph \(G(\beta)\) end at the vertex \(j\). For any word \(u\in\operatorname{Adm}_{d-1}(j)\), denote by \(\widetilde A_n(j)\) the set of words \(w\) of length \(n\) for which the word \(uw\) is admissible. Note that the admissibility of the word \(uw\) depends only on the existence, in the graph \(G(\beta)\), of a path that starts at the vertex at which the path corresponding to \(u\) ends. This means that \(\widetilde A_n(j)\) does not depend on the choice of \(u\) and is the set of admissible words of length \(n\) for which there is a corresponding path starting at \(j\). For every \(w\in\widetilde A_n(j)\), define the set

$$\mathscr R_{n,j}(w) =\overline{\Phi\biggl(\bigsqcup_{u\in\operatorname{Adm}_{d-1}(j)}\mathbb N(uw)\biggr)}.$$

Proposition 3.

For every \(n\) , one has the tiling

$$\mathscr T=\bigsqcup_{j=0}^{d-1}\bigsqcup_{w\in\widetilde A_n(j)} \mathscr R_{n,j}(w)$$

of the Rauzy fractal \(\mathscr T\) into sets \(\mathscr R_{n,j}(w)\) having no common interior points. Each of the sets \(\mathscr R_{n,j}(w)\) has a boundary of zero measure.

This assertion is proved in [11, Theorem 11]. The tiling thus constructed is called the Rauzy tiling of order \(n\).

Proposition 4.

Let \(j\in\{0,1,\dots,d-1\}\) . Then the following equality holds for any \(n\) and any word \(w\in\widetilde A_n(j)\) :

$$\operatorname{mes}\mathscr R_{n,j}(w) =\frac{\beta^{d-1-j-n}}{\sum_{l=0}^{d-1}\beta^l}\operatorname{mes}\mathscr T.$$

This assertion is proved in [9, Theorem 10].

Further, let us define a mapping \(S\) on the Rauzy fractal. Let \(\operatorname{Adm}(j)=\bigcup_n\operatorname{Adm}_n(j)\) be the set of words to which there correspond paths on the graph \(G(\beta)\) that begin at the vertex \(0\) and end at the vertex \(j\). Let \(\mathbb N(j)=\{n\in\mathbb N\colon w(n)\in\operatorname{Adm}(j)\}\). Here \(\mathbb N=\bigsqcup_{j=0}^{d-1}\mathbb N(j)\). As is known (see, for example, [7, Sec. 1.3]), there are vectors \(v_j\in\mathbb R^{d-1}\) such that \(\Phi(n+1)-\Phi(n)=v_j\). Write \(\mathscr T(j)=\overline{\Phi(\mathbb N(j))}\) and define the mapping \(S\colon\mathscr T\to\mathscr T\) of the Rauzy fractal into itself according to the rule \(S(x)=x+v_j\) if \(x\in\mathscr T(j)\). It turns out (see [7, Theorem 6], [12, Theorem 2]) that the mapping \(S\) is defined almost everywhere on \(\mathscr T\) (and is an exchange of the domains \(\mathscr T(j)\), \(j\in\{0,1,\dots,d-1\}\)).

Remark 1.

Usually, this assertion is proved for a more general class of Rauzy fractals that are constructed using the basis of the so-called primitive unimodular Pisot substitutions. The reduction of the case under consideration to the general case can be found in [7, Secs. 2.3, 2.4]. Here it is required that \(\beta\) is a Pisot number (of degree \(d\)) and a unit of the ring \(\mathbb Z[\beta]\) and that the length of the word \(d(1,\beta)\) is equal to \(d\). The fact that \(\beta\) is a unit of the ring \(\mathbb Z[\beta]\) holds because \(a_d=1\), and the other conditions follow from Proposition 1.

The mapping \(S\) is not defined on points in the sets of the form \(\mathscr T(j_1)\cap\mathscr T(j_2)\). Note that the points of the form \(\Phi(n)\) with \(n\in\mathbb N\) do not belong to the boundaries of the sets of the form \(\mathscr T(j)\) (and even do not belong to the boundaries of sets of the form \(\overline{\Phi(\mathbb N(w))}\) for any admissible word \(w\)) [10, Corollary 1], and hence, for such points, the mapping \(S\) is well defined. Here \(S(\Phi(n))=\Phi(n+1)\).

Note also that the diagram

is commutative [9, Theorem 7].

Remark 2.

It can be shown [7, Theorem 7], [13, Theorem 7] that the Rauzy fractal \(\mathscr T\) represents a fundamental domain of some lattice \(L\). In this case, one can consider the natural projection \(\pi\colon\mathbb R^{d-1}\to\mathbb T^{d-1}=\mathbb R^{d-1}/L\). It turns out [12, Theorem 2 and Remark 5] that there exists a vector \(l\in\mathbb T^{d-1}\) whose coordinates in the basis of the lattice \(L\) are linearly independent over \(\mathbb Q\), together with the unit, and such that the equality \(\pi(S(x))=\pi(x)+l\ (\operatorname{mod}L)\) holds for every \(x\in\mathscr T\) for which the mapping \(S\) is defined.

Proposition 5.

The sets \(\mathscr R_{n,j}(w)\) are bounded remainder sets for the mapping \(S\) ; i.e., there exists a constant \(C\) depending only on \(\beta\) and such that the following inequality holds for all positive integers \(X\) :

$$\biggl|\sharp\bigl\{k\colon k\le X,\,S^k(0)\in\mathscr R_{n,j}(w)\bigr\} -\frac{\operatorname{mes}\mathscr R_{n,j}(w)} {\operatorname{mes}\mathscr T}\,X\biggr|\le C.$$

Moreover, \(C\) depends on \(\beta\) , but not on \(n\) , \(j\) , and \(w\) .

For the proof, see [9, Theorem 12].

Let \(w\) be an admissible word of length \(|w|\). Let \(J(w)\) be the set of vertices of the graph \(G(\beta)\) for which there is a path in \(G(\beta)\) beginning at a vertex \(j\) and labelled with the word \(w\). Let

$$\mathscr T(w)=\bigsqcup_{j\in J(w)}\mathscr R_{|w|,j}.$$

Proposition 6.

For every admissible word \(w\) , \(n\in\mathbb N(w)\) if and only if \(S^n(0)\in\mathscr T(w)\) .

Proof.

The proof can be found in [9, Theorems 13, 14]

By Proposition 3, the sets \(\mathscr R_{|w|,j}\) contained in \(\mathscr T(w)\) have no common interior points. Therefore, taking into account Proposition 4, we have

$$\operatorname{mes}\mathscr T(w) =\frac{\sum_{j\in J(w)}\beta^{d-1-j-|w|}}{\sum_{l=0}^{d-1}\beta^l} \operatorname{mes}\mathscr T.$$

In addition, taking into account Proposition 5, we see that the sets \(\mathscr T(w)\) are also sets of bounded remainder with respect to the mapping \(S\). Moreover, since \(\mathscr T(w)\) obviously contains at most \(d\) sets \(\mathscr R_{|w|,j}\), it follows that the corresponding bound for the remainder does not depend on the choice of the word \(w\). Combining this result with Proposition 6, we obtain the required information concerning the asymptotic of \(N_w(X)\).

Theorem 2.

There exists a constant \(C_1\) depending on \(\beta\) only and such that the following inequality holds for any admissible word \(w\) and any positive integer \(X\) :

$$\biggl|N_w(X)-\frac{\sum_{j\in J(w)}\beta^{d-1-j-|w|}} {\sum_{l=0}^{d-1}\beta^l}\,X\biggr| \le C_1. $$
(3.1)

4. Proof of the Main Theorem

Let

$$\varepsilon(n)=\begin{cases} 1, &n\in\mathscr N_0, \\ -1, &n\in\mathscr N_1. \end{cases}$$

Then it can readily be seen that the following equality holds:

$$T_{i,j}(X)=\sum_{n\le X}\frac{(-1)^i\varepsilon(n)+1}{2} \frac{(-1)^j\varepsilon(n+1)+1}{2}\,. $$
(4.1)

Proposition 7.

There is an effectively computable constant \(\lambda<1\) such that

$$\sum_{n\le N}\varepsilon(n)=O(n^\lambda). $$
(4.2)

For the proof of Proposition 7, see [14]. A description of \(\lambda\) in terms of the roots of some equation depending on the coefficients of the linear recurrent sequence is given ibidem. A more general result is also proved in [15]. In [16], the possibility of strengthening the bound for the remainder term to a logarithmic one is discussed.

Let

$$S(X)=\sum_{n\le X}\varepsilon(n)\varepsilon(n+1).$$

Multiplying out in (4.1), we obtain

$$T_{i,j}(X)=\frac{X}{4} +\sum_{n\le X}\frac{(-1)^{i+j}\varepsilon(n)\varepsilon(n+1)}{4} +\sum_{n\le X}\frac{(-1)^i\varepsilon(n)}{4} +\sum_{n\le X}\frac{(-1)^j\varepsilon(n+1)}{4}\,.$$

Taking into account (4.2) and the definition of \(S(X)\), we can represent the last expression in the form

$$T_{i,j}(X)=\frac{X+(-1)^{i+j}S(X)}{4}+O(X^{\lambda})$$

for some effectively computable \(\lambda\in(0;1)\).

Then it can readily be seen from (4.1) and (4.2) that, to prove Theorem 1, it suffices to prove the following assertion.

Proposition 8.

There exists an effectively computable constant \(C_\beta\) such that

$$S(X)=C_\beta X+O(\log X).$$

It can readily be seen here that \(C_{00}=C_{11}=(1/4)C_\beta\) and \(C_{01}=C_{10}=-(1/4)C_\beta\).

Let us pass to the proof of Proposition 8. For \(k\in\{0,1,\dots,d-1\}\), write \(w_{\max}^{(k)}=a_1\dotsb a_k\) (for \(k=0\), \(w_{\max}^{(0)}\) is the empty word). Write \(w_{\max}^{(d)}=a_1\dotsb a_{d-1}0\). Then it is easy to see that the word \(w_{\max}^{(k)}\) is admissible for any \(k\). Moreover, it is the maximum admissible word of length \(k\) with respect to the lexicographic order.

Let \(U\) be the set of admissible words of length \(d\) corresponding to paths of the graph \(G(\beta)\) starting and ending at the vertex \(0\) and different from the word \(w_{\max}^{(d)}\). It follows from the consideration of the graph \(G(\beta)\) that an admissible word belongs to \(U\) if and only if it does not end by any of the words \(w_{\max}^{(k)}\) (\(1\le k\le d\)). For \(u\in U\), \(k\in\{0,1,\dots,d-1\}\), and an integer nonnegative \(m\), define the word

$$w_{u,m,k}=u\underbrace{w_{\max}^{(d)}\dotsb w_{\max}^{(d)}}_mw_{\max}^{(k)}.$$

The words introduced in this way have the following important properties.

1) None of the words \(w_{u,m,k}\) ends with another word.

2) For any positive integer \(N\), the word \(w(N)\) (or a word derived from \(w(N)\) by adding a certain number of zeros from the left) ends with one of the words \(w_{u,m,k}\).

Thus, there is a representation of the set of positive integers as the disjoint union

$$\mathbb{N}=\bigsqcup_{u\in U}\bigsqcup_{m\ge 0} \bigsqcup_{k=0}^{d-1}\mathbb N(w_{u,m,k}). $$
(4.3)

For any admissible word \(w\), denote by \(w'\) the lexicographically next admissible word. Then it can readily be seen that the following equality holds:

$$(w_{u,m,k})'=u'\underbrace{0\dots 0}_{md+k}. $$
(4.4)

For the word \(w=w_1\dotsb w_{|w|}\) (where \(w_i\in\{0,1,\dots,a_1\}\) are separate symbols of the word), write

$$\varepsilon(w)=(-1)^{w_1+\dotsb+w_{|w|}}.$$

It is clear that \(\varepsilon(N)=\varepsilon(w(N))\). Let us represent \(w(N)\) in the form \(w(N)=vw_{u,m,k}\). Then we have \((w(N))'=v(w_{u,m,k})'\). Therefore,

$$\varepsilon(n)\varepsilon(n+1) =\varepsilon(v)\varepsilon(w_{u,m,k})\varepsilon(v)\varepsilon((w_{u,m,k})').$$

Then, taking into account (4.4) and the definition of \(w_{u,m,k}\), we see that the following equality holds for any \(n\in\mathbb N(w_{u,m,k})\):

$$\varepsilon(n)\varepsilon(n+1) =\varepsilon(u)\varepsilon(u')(\varepsilon(w_{\max}^{(d)}))^m\varepsilon(w_{\max}^{(k)}).$$

Taking into account the definition of the words \(w_{\max}^{(k)}\), we obtain

$$\varepsilon(n)\varepsilon(n+1) =\varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k}. $$
(4.5)

Combining (4.3) and (4.5), we have

$$S(X)=\sum_{u\in U}\sum_{m\ge 0}\sum_{k=0}^{d-1} \varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k}N_{w_{u,m,k}}(X).$$

Note that the equality \(N_{w_{u,m,k}}(X)=0\) obviously holds for \(|w_{u,m,k}|>|w(X)|=m(X)\). Therefore,

$$S(X)=\sum_{u\in U}\sum_{m=0}^{|w(X)|}\sum_{k=0}^{d-1} \varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k}N_{w_{u,m,k}}(X).$$

Let

$$r_{w_{u,m,k}}(X)=N_{w_{u,m,k}}(X) -\frac{\sum_{j\in J(w_{u,m,k})}\beta^{d-1-j-|w_{u,m,k}|}}{\sum_{l=0}^{d-1}\beta^l}\,.$$

Then

$$S(X)=S_1(X)+S_2(X),$$

where

$$\begin{aligned} \, S_1(X) &=\sum_{u\in U}\sum_{m=0}^{|w(X)|}\sum_{k=0}^{d-1} \varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k} \\ &\qquad\qquad\times \frac{\sum_{j\in J(w_{u,m,k})}\beta^{d-1-j-|w_{u,m,k}|}}{\sum_{l=0}^{d-1}\beta^l}, \\ S_2(X)&=\sum_{u\in U}\sum_{m=0}^{|w(X)|}\sum_{k=0}^{d-1} \varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k}r_{w_{u,m,k}}(X). \end{aligned}$$

Applying Theorem 2, we see that there is a constant \(C_1\) depending on \(\beta\) only and such that

$$|r_{w_{u,m,k}}(X)|\le C_1.$$

Applying the triangle inequality and taking into account that

$$|\varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k}|=1,$$

we obtain

$$|S_2(X)|\le \sum_{u\in U}\sum_{m=0}^{|w(X)|}\sum_{k=0}^{d-1}C_1,$$

i.e.,

$$|S_2(X)|\le\sharp U\,dC_1|w(X)|.$$

Here it follows from the definition of the set \(U\) that its cardinality \(\sharp U\) does not depend on \(X\). Moreover, it follows from Corollary 2 that \(|w(X)|=O(\log X)\). Hence

$$S_2(X)=O(\log X).$$

Therefore, transposing the summation over \(m\) and \(k\) in the sum for \(S_1(X)\), we find that

$$S(X)=\sum_{u\in U}\sum_{k=0}^{d-1}\Sigma_{u,k}(X)X+O(\log X),$$

where

$$\Sigma_{u,k}(X)=\sum_{m=0}^{m(X)} \varepsilon(u)\varepsilon(u')(-1)^{m(a_1+\dotsb+a_{d-1})+a_1+\dotsb+a_k} \frac{\sum_{j\in J(w_{u,m,k})}\beta^{d-1-j-|w_{u,m,k}|}}{\sum_{l=0}^{d-1}\beta^l}\,.$$

Since \(|w_{u,m,k}|=(m+1)d+k\), it follows that the last equality can be represented in the form

$$\Sigma_{u,k}(X) =\frac{\varepsilon(u)\varepsilon(u')(-1)^{a_1 +\dotsb+a_k}\beta^{-1-k}}{\sum_{l=0}^{d-1}\beta^l} \sum_{m=0}^{m(X)}(-1)^{m(a_1+\dotsb+a_{d-1})} \beta^{-md}\sum_{j\in J(w_{u,m,k})}\beta^{-j}.$$

Further, note that it is easy to derive that any path in \(G(\beta)\) corresponding to a word \(u\) must end at the vertex \(0\) from the fact that the word \(u\in U\) does not end with \(w_{\max}^{(k)}\). In addition, the word \(w_{\max}^{(k)}\) with \(k>0\) is admissible and, corresponding to it, there is a path in the graph \(G(\beta)\) starting at the vertex \(0\). Therefore, every path corresponding to the word \(u\) can be continued to a path corresponding to the word \(uw_{\max}^{(k)}\). Hence we see that \(J(w_{u,m,k})=J(u)\) and

$$\Sigma_{u,k}(X) =\frac{\varepsilon(u)\varepsilon(u')(-1)^{a_1 +\dotsb+a_k}\beta^{-1-k}}{\sum_{l=0}^{d-1}\beta^l} \sum_{m=0}^{m(X)}(-1)^{m(a_1+\dotsb+a_{d-1})}\beta^{-md}\sum_{j\in J(u)}\beta^{-j}.$$

Write

$$C_{u,k}=\frac{\varepsilon(u)\varepsilon(u')(-1)^{a_1+\dotsb+a_k}\beta^{-1-k}} {\sum_{l=0}^{d-1}\beta^l} \sum_{m=0}^\infty(-1)^{m(a_1+\dotsb+a_{d-1})}\beta^{-md}\sum_{j\in J(u)}\beta^{-j}.$$

Taking into account the formula for the sum of an infinite geometric progression, we obtain

$$C_{u,k}=\frac{\varepsilon(u)\varepsilon(u')(-1)^{a_1+\dotsb+a_k}\beta^{-1-k}} {\sum_{l=0}^{d-1}\beta^l(1-(-1)^{a_1+\dots+a_{d-1}}\beta^{-d})} \sum_{j\in J(u)}\beta^{-j}.$$

Write

$$C_\beta=\sum_{u\in U}\sum_{k=0}^{d-1}C_{u,k}.$$

Note that all constants \(C_{u,k}\), and thus also all constants \(C_\beta\), are effectively computable.

To complete the proof of Proposition 8, it remains to prove that

$$|C_\beta-\sum_{u\in U}\sum_{k=0}^{d-1}\Sigma_{u,k}(X)|X=O(\log X). $$
(4.6)

For the proof of this bound, it suffices to prove that

$$|C_{u,k}-\Sigma_{u,k}(X)|X=O(\log X).$$

When taking into account the definitions of \(C_{u,k}\) and \(\Sigma_{u,k}\), we see that the last bound is equivalent to

$$X\sum_{m=|w(X)|+1}^\infty(-1)^{m(a_1+\dotsb+a_{d-1})}\beta^{-md}=O(\log X). $$
(4.7)

Summing the infinite geometric progression again, we obtain

$$X\sum_{m=|w(X)|+1}^{\infty}(-1)^{m(a_1+\dots+a_{d-1})}\beta^{-md}\le \frac{C_2X}{\beta^{d|w(X)|}}$$

with some constant \(C_2\). When taking into account Corollary 2, we see that the last value is \(O(X^{1-d})\) and, therefore, \(O(\log X)\), which proves (4.7), and hence also (4.6), which completes the proof of Proposition 8, and hence also of Theorem 1.