betaFeedback

WorksMathematics

Perturbing the Conway sequence

Abstract

We study the alternating perturbation of Conway's nested recurrence, C(n)=C(C(n−1))+C(n−C(n−1))+(−1)nC(n)=C(C(n-1))+C(n-C(n-1))+(-1)^n for n≥3n\geq 3, with C(1)=C(2)=1C(1)=C(2)=1. We prove that the sequence is well defined and satisfies C(n)=ψ−3n+O(n/log⁡n)C(n)=ψ^{-3}n+O(n/\sqrt{\log n}), where ψ>1ψ>1 is the real root of ψ3=ψ2+1ψ^3=ψ^2+1.

Introduction

We consider the sequence (OEIS A399773 [5]) defined by

C(1)=C(2)=1,C(n)=C(C(n−1))+C(n−C(n−1))+(−1)n(n≥3).(1)C(1)=C(2)=1,\qquad C(n)=C(C(n-1))+C(n-C(n-1))+(-1)^n\quad(n\ge3). \tag*{(1)}

Without the alternating term, Conway’s recurrence has limiting ratio 1/21/2; see Mallows [1] and Kubo–Vakil [2]. The alternating perturbation changes this limiting ratio. Let ψ>1\psi>1 be the real root of ψ3=ψ2+1\psi^3=\psi^2+1, so that the candidate slope is ψ−3=0.317672196…\psi^{-3}=0.317672196\ldots. Throughout, log⁡\log denotes the natural logarithm.

Theorem 1. The recurrence (1) is well defined for every positive integer, and

C(n)=nψ3+O(nlog⁡n).(2)C(n)=\frac{n}{\psi^3}+O\left(\frac{n}{\sqrt{\log n}}\right). \tag*{(2)}

In particular, C(n)/n→ψ−3C(n)/n\to\psi^{-3}.

The motivation was Mantovanelli’s addition of (−1)n(-1)^n to Hofstadter’s QQ-recurrence [3]. In [4], we proved that the resulting sequence Q^\widehat{Q} is well defined and satisfies Q^(n)=n/2+O(n/log⁡n)\widehat{Q}(n)=n/2+O(n/\sqrt{\log n}), with this error order optimal. That proof uses binary words, Dyck paths, and plane forests. Here the argument instead combines exact values on a geometric subsequence with a quadratic estimate on the recursion tree.

Motivation and proof outline

The first terms are

C=1,1,1,3,1,3,3,3,3,5,3,5,3,5,5,5,….C=1,1,1,3,1,3,3,3,3,5,3,5,3,5,5,5,\ldots.

Although CC is not monotone, the graph of C(n)/nC(n)/n reveals a regular pattern of arches on a logarithmic horizontal scale (Figure 1). Examining selected local maxima of C(n)−ψ−3nC(n)-\psi^{-3}n led to two empirical families of indices,

Figure 1. C(n)/nC(n)/n for 103≤n≤22010^3 \le n \le2^{20}, with a logarithmic horizontal axis. The markers show the computed values at the reference indices TjT_j. The exact formulas proved in § 4 imply C(Tj)/Tj=ψ−3+O(Tj−1)C(T_j)/T_j = \psi^{-3} + O(T_j^{-1}).

(110,230,488,1042,2232,4788,…),(704,1516,3260,7006,15052,…).(110,230,488,1042,2232,4788,\ldots),\qquad(704,1516,3260,7006,15052,\ldots).

Starting at 488, they interleave as 488,704,1042,1516,2232,3260,…488,704,1042,1516,2232,3260,\ldots, with consecutive ratios appearing to approach ψ\psi. Since ψ3=ψ2+1\psi^3=\psi^2+1, it is natural to test the residual Tj−Tj−1−Tj−3T_j-T_{j-1}-T_{j-3}.

In the computed list, it alternated between −14-14 and 1212, beginning at j=3j=3. We therefore define the reference indices by

T0=488,T1=704,T2=1042,Tj=Tj−1+Tj−3−1+13(−1)j(j≥3).(3)\begin{aligned} T_0 &= 488,\quad T_1 = 704,\quad T_2 = 1042,\\ T_j &= T_{j-1} + T_{j-3} - 1 + 13(-1)^j \quad(j \ge3). \tag*{(3)} \end{aligned}

We shall prove exact formulas for C(Tj)C(T_j) and C(Tj−1)C(T_j-1) in § 4. In particular, C(Tj)=ψ−3Tj+O(1)C(T_j)=\psi^{-3}T_j+O(1), so the marked values of C(Tj)/TjC(T_j)/T_j approach ψ−3\psi^{-3} at order Tj−1T_j^{-1}.

A comparison with the shifted sequence

R(1)=R(2)=R(3)=1,R(n)=R(R(n−2))+R(n−1−R(n−2))(n≥4)R(1)=R(2)=R(3)=1,\qquad R(n)=R(R(n-2))+R(n-1-R(n-2))\quad(n\ge4)

also helped identify the local structure. This sequence satisfies R(n)=ψ−3n+O(1)R(n)=\psi^{-3}n+O(1) [6]. Jeffrey Shallit supplied a conjectural automaton for max⁡{C(n)−R(n),0}\max\{C(n)-R(n),0\} in Narayana numeration [7]. Its repeating patterns included the reference families already observed and suggested examining short windows around them. The windows led to the two tables used below; their values are established directly from (1).

The proof has two steps. First, the odd and even positions of CC give two nondecreasing sequences A,BA,B whose increments are 0 or 1. Around each sj=Tj/2s_j=T_j/2, a short table of their values, translated vertically by sj−3s_{j-3}, repeats according to the parity of jj. The recurrence reads neighboring entries as well as the centers, so these tables contain just the extra information needed for induction. The main difficulty is locating the left endpoint of the next window. At the first index where AA reaches a value vv, the preceding value is necessarily v−1v-1; this observation determines the endpoint from earlier tables.

The second step controls all indices between the reference points. Their spacing is comparable to their size, so monotonicity alone would leave a nonvanishing relative error. Expanding the recurrence on a binary tree gives weighted averages, with weights ψ−3,ψ−1\psi^{-3},\psi^{-1} corresponding to descents of three and one reference levels. The key comparison is between the paths 10 and 01: their weights agree, but they end at different functions. This relates an error in a sequence value to changes of the arguments in the tree. Summing squared changes over HH levels gives an O(H−1/2)O(H^{-1/2}) bound. The exact tables permit HH to be proportional to log⁡n\log n, yielding (2).

Sections 2–4 establish the parity properties, the first-passage lemma, and the local tables. Section 5 gives the tree estimate and completes the proof. The finite initial calculation is recorded in Appendix A.

Splitting the sequence

The perturbations at nn and n+2n+2 have the same sign, so they cancel when the corresponding recurrences are subtracted. This gives monotonicity separately on the odd and even positions.

Lemma 2. The recurrence (1) is well defined. Its values are positive and odd, and 1≤C(n)≤n−1(n≥2),C(n+2)−C(n)∈{0,2}(n≥1).1 \le C(n) \le n-1 \quad(n \ge2), \qquad C(n+2)-C(n) \in\{0,2\} \quad(n \ge1).

Both parity subsequences are unbounded, and each takes every positive odd integer value.

Proof. The values C(1)=C(2)=C(3)=1C(1)=C(2)=C(3)=1 start the induction for well-definedness. Let n≥4n \ge4, assume the earlier values are positive and odd with the stated bound, and put u=C(n−1)u=C(n-1). Then 1≤u≤n−21 \le u \le n-2, so both uu and n−un-u are earlier positive indices. The recurrence gives a positive odd value. If u≥2u \ge2, both arguments are at least 2, and

C(n)≤(u−1)+(n−u−1)+1=n−1.C(n) \le(u-1)+(n-u-1)+1=n-1.

If u=1u=1, then C(n−1)=1C(n-1)=1 and C(n)=2+(−1)n≤3≤n−1C(n)=2+(-1)^n \le3 \le n-1.

For the parity increments, use a separate induction on nn. The cases n=1,2n=1,2 give C(3)−C(1)=0C(3)-C(1)=0 and C(4)−C(2)=2C(4)-C(2)=2. For n≥3n \ge3, put u=C(n−1)u=C(n-1) and v=C(n+1)v=C(n+1). The preceding step gives v−u∈{0,2}v-u \in\{0,2\}, while subtraction yields

C(n+2)−C(n)=C(v)+C(n+2−v)−C(u)−C(n−u).C(n+2)-C(n)=C(v)+C(n+2-v)-C(u)-C(n-u).

If v=uv=u, this is C(n−u+2)−C(n−u)C(n-u+2)-C(n-u); if v=u+2v=u+2, it is C(u+2)−C(u)C(u+2)-C(u). In either case the induction hypothesis applies at a positive starting index smaller than nn.

If one parity subsequence were bounded, it would be eventually constant. Its fixed splitting value in (1) would then make the other parity eventually constant as well. Let the eventual odd and even values be a,ba,b, respectively. Both are positive and odd, and the recurrence at sufficiently large odd and even indices gives

a=C(b)+b−1≥b,b=C(a)+a+1>a,a=C(b)+b-1 \ge b,\qquad b=C(a)+a+1>a,

a contradiction. An unbounded nondecreasing sequence of odd integers starting at 1 and taking steps 0 or 2 visits every positive odd integer. □\square

Set A(0)=B(0)=0A(0)=B(0)=0 and, for k≥1k \ge1, define

A(k)=C(2k−1)+12,B(k)=C(2k)+12.(4)A(k)=\frac{C(2k-1)+1}{2},\qquad B(k)=\frac{C(2k)+1}{2}. \tag*{(4)}

Thus AA records the odd positions and BB the even positions, with C(2k−1)=2A(k)−1C(2k-1)=2A(k)-1 and C(2k)=2B(k)−1C(2k)=2B(k)-1. Both are slow: their successive increments belong to {0,1}\{0,1\}. They are unbounded and satisfy 0≤A(k),B(k)≤k0 \le A(k),B(k) \le k. Moreover, all four maps

A,B,x↦x−A(x),x↦x−B(x)A,\qquad B,\qquad x \mapsto x-A(x),\qquad x \mapsto x-B(x)

are nondecreasing and 1-Lipschitz. Consequently, compositions of these maps do not amplify absolute errors, a fact used in Section 5.

Substitution into (1) gives, for k≥2k \ge2,

A(k)=A(B(k−1))+B(k−B(k−1))−1,(5)A(k)=A(B(k-1))+B(k-B(k-1))-1, \tag*{(5)}
B(k)=A(A(k))+A(k+1−A(k)).(6)B(k)=A(A(k))+A(k+1-A(k)). \tag*{(6)}

For example, at position 2k−12k-1 the splitting value is C(2k−2)=2B(k−1)−1C(2k-2)=2B(k-1)-1. The two arguments in (1) are therefore 2B(k−1)−12B(k-1)-1 and 2(k−B(k−1))2(k-B(k-1)), giving (5).

Pinpointing first passages

To propagate a table to a new window, we must first locate its left endpoint k0k_0. Evaluating A(k0)A(k_0) by (5) requires B(k0−1)B(k_0-1), just outside that window. We overcome this difficulty by asking where AA first reaches the desired value vv.

Since AA is slow and nondecreasing, at the first index KvK_v where A(Kv)=vA(K_v)=v, its preceding value is necessarily A(Kv−1)=v−1A(K_v-1)=v-1. Substituting A(k−1)=v−1A(k-1)=v-1 into (6) at a trial index k−1k-1 suggests the candidate expression hv(k):=A(v−1)+A(k−v+1)h_v(k):=A(v-1)+A(k-v+1) for B(k−1)B(k-1). Feeding this candidate into (5) in turn yields a test function Φv(k)\Phi_v(k). In the application, this test can be evaluated from two earlier tables.

Lemma 3 (First passage). Let v≥3v\ge3, and write Kv=min⁡{k:A(k)=v}K_v=\min\{k:A(k)=v\}. For k≥vk\ge v, define

hv(k)=A(v−1)+A(k−v+1),Φv(k)=A(hv(k))+B(k−hv(k))−1.(7)\begin{aligned} h_v(k)&=A(v-1)+A(k-v+1),\\ \Phi_v(k)&=A(h_v(k))+B(k-h_v(k))-1. \tag*{(7)} \end{aligned}

Then Φv\Phi_v is nondecreasing and Φv(Kv)=v\Phi_v(K_v)=v. If k0−1≥vk_0-1\ge v and

Φv(k0−1)=v−1,Φv(k0+1)=v+1,\Phi_v(k_0-1)=v-1,\qquad\Phi_v(k_0+1)=v+1,

then

Kv=k0,A(k0−1)=v−1,B(k0−1)=hv(k0).K_v=k_0,\qquad A(k_0-1)=v-1,\qquad B(k_0-1)=h_v(k_0).

Proof. The bounds A(u)≤uA(u)\le u give 0≤hv(k)≤k0\le h_v(k)\le k, so all terms are defined. As kk increases by one, hv(k)h_v(k) increases by zero or one; the same is true of k−hv(k)k-h_v(k). Hence Φv\Phi_v is nondecreasing. At the first passage, A(Kv−1)=v−1A(K_v-1)=v-1. Since Kv≥v≥3K_v\ge v\ge3, equation (6) applies at Kv−1K_v-1 and gives

B(Kv−1)=A(v−1)+A(Kv−v+1)=hv(Kv).B(K_v-1)=A(v-1)+A(K_v-v+1)=h_v(K_v).

(5) at KvK_v now gives Φv(Kv)=v\Phi_v(K_v)=v. If Kv≤k0−1K_v\le k_0-1, monotonicity would imply Φv(Kv)≤v−1\Phi_v(K_v)\le v-1; if Kv≥k0+1K_v\ge k_0+1, it would imply Φv(Kv)≥v+1\Phi_v(K_v)\ge v+1. Both are impossible, so Kv=k0K_v=k_0, and the preceding values follow.

The equality at KvK_v is the essential point: it locates the first passage by testing Φv\Phi_v on either side of a proposed index. The identities with the true sequence values are used only at that first passage. Once it has been located, we know both A(k0)A(k_0) and B(k0−1)B(k_0-1) and can compute the rest of the window in order.

Exact values near the reference indices

Put sj=Tj/2s_j=T_j/2. Dividing (3) by two gives

s0=244,s1=352,s2=521,s_0=244,\qquad s_1=352,\qquad s_2=521,
sj=sj−1+sj−3+{6,j even,−7,j odd(j≥3).(8)s_j=s_{j-1}+s_{j-3}+ \begin{cases} 6,&j\text{ even},\\ -7,&j\text{ odd} \end{cases} \qquad(j\ge3). \tag*{(8)}

For each jj, the tables below record the values in a short window around sjs_j, after subtracting sj−3s_{j-3}. Their width is chosen so that every nested call needed at level jj can be read in the tables at levels j−1j-1 and $j-3.

Proposition 4. For every j≥3j\ge3, put z=sj−3z=s_{j-3}. At an even level jj, one has

tt−5-5−4-4−3-3−2-2−1-100
A(sj+t)−zA(s_j+t)-z111122222222
B(sj+t)−zB(s_j+t)-z112233333344

Table 9.

::: and at an odd level jj, one has

tt−1-1001122334455
A(sj+t)−zA(s_j+t)-z−4-4−3-3−3-3−2-2−2-2−2-2−1-1
B(sj+t)−zB(s_j+t)-z−3-3−2-2−2-2−2-2−2-2−2-2−2-2

caption:

:::

Here tt is the offset from sjs_j. The parity of the level jj selects the table, whereas its two rows correspond to the odd and even positions of CC. We prove the proposition by strong induction on jj. Three initial levels are needed because the step uses levels j−1j-1 and j−3j-3.

Starting the induction

Direct evaluation of (1) through index 32703270 gives the following values. Each row is read over the offsets of the appropriate table, in increasing order.

jjsjs_jsj−3s_{j-3}Values on the window
33758758244244AA: 240,241,241,242,242,242,243240, 241, 241, 242, 242, 242, 243; BB: 241,242,242,242,242,242,242241, 242, 242, 242, 242, 242, 242
4411161116352352AA: 353,353,354,354,354,354353, 353, 354, 354, 354, 354; BB: 353,354,355,355,355,356353, 354, 355, 355, 355, 356
5516301630521521AA: 517,518,518,519,519,519,520517, 518, 518, 519, 519, 519, 520; BB: 518,519,519,519,519,519,519518, 519, 519, 519, 519, 519, 519

Table initial.

Subtracting sj−3s_{j-3} gives (9)–(10). The largest parity index is s5+5=1635s_5+5=1635, corresponding to C(3270)C(3270). The program in Appendix A verifies these forty values.

Locating the left endpoint

Assume the proposition holds at levels 3,…,j−13,\ldots,j-1, where j≥6j\ge6, and write z=sj−3z=s_{j-3}.

Even levels. The source levels j−1,j−3j-1,j-3 are odd and use (10). Equation (8) gives

sj−z=sj−1+6,z=sj−4+sj−6−7.s_j-z=s_{j-1}+6,\qquad z=s_{j-4}+s_{j-6}-7.

We seek A(sj−5)=z+1A(s_j-5)=z+1. Set v=z+1v=z+1 and k0=sj−5k_0=s_j-5 in Lemma 3. For t=−6,−5,−4t=-6,-5,-4,

hv(sj+t)=A(z)+A(sj−1+t+6).h_v(s_j+t)=A(z)+A(s_{j-1}+t+6).

The first term is read at level j−3j-3 and the second at level j−1j-1. Using their known values, followed by the definition of Φv\Phi_v, gives

tt−6-6−5-5−4-4
hv(sj+t)h_v(s_j+t)z+1z+1z+1z+1z+2z+2
Φv(sj+t)\Phi_v(s_j+t)zzz+1z+1z+2z+2

Table 11.

For instance, the first column is

hv(sj−6)=(sj−6−3)+(sj−4−3)=z+1,h_v(s_j-6)=(s_{j-6}-3)+(s_{j-4}-3)=z+1,
Φv(sj−6)=A(z+1)+B(sj−1−1)−1=(sj−6−3)+(sj−4−3)−1=z.\begin{aligned} \Phi_v(s_j-6)=A(z+1)+B(s_{j-1}-1)-1 \\ &=(s_{j-6}-3)+(s_{j-4}-3)-1=z. \end{aligned}

The offsets used for hvh_v are (0,0),(0,1),(0,2)(0,0),(0,1),(0,2); those for Φv\Phi_v are (1,−1),(1,0),(2,0)(1,-1),(1,0),(2,0). They all lie between −1-1 and 55, so the earlier odd-level tables supply every entry. Since k0−1−v=sj−1−1>0k_0-1-v=s_{j-1}-1>0, the first and last columns of (11) locate the passage:

min⁡{k:A(k)=z+1}=sj−5,B(sj−6)=z+1.\min\{k:A(k)=z+1\}=s_j-5,\qquad B(s_j-6)=z+1.

For example, at j=6j = 6, s6=2394s_6 = 2394 and z=s3=758z = s_3 = 758. The initial tables locate the first occurrence of 759 at 2389:

h759(2388)=A(758)+A(1630)=241+518=759,h_{759}(2388) = A(758) + A(1630) = 241 + 518 = 759,
Φ759(2388)=A(759)+B(1629)−1=241+518−1=758,\Phi_{759}(2388) = A(759) + B(1629) - 1 = 241 + 518 - 1 = 758,
h759(2390)=A(758)+A(1632)=241+519=760,h_{759}(2390) = A(758) + A(1632) = 241 + 519 = 760,
Φ759(2390)=A(760)+B(1630)−1=242+519−1=760.\Phi_{759}(2390) = A(760) + B(1630) - 1 = 242 + 519 - 1 = 760.

Odd levels. Now j≥7j \ge7 is odd, and the source levels are even. We have

sj−z=sj−1−7,z=sj−4+sj−6+6.s_j - z = s_{j-1} - 7,\qquad z = s_{j-4} + s_{j-6} + 6.

To obtain A(sj−1)=z−4A(s_j - 1) = z - 4, take v=z−4v = z - 4 and k0=sj−1k_0 = s_j - 1. For t=−2,−1,0t = -2,-1,0,

hv(sj+t)=A(z−5)+A(sj−1+t−2),h_v(s_j + t) = A(z - 5) + A(s_{j-1} + t - 2),

and the earlier even-level tables give

t=−2t = -2t=−1t = -1t=0t = 0
hv(sj+t)h_v(s_j + t)z−4z - 4z−3z - 3z−3z - 3
Φv(sj+t)\Phi_v(s_j + t)z−5z - 5z−4z - 4z−3z - 3
{#eq:13}

The offsets used for hvh_v are (−5,−4)(-5,-4), (−5,−3)(-5,-3), (−5,−2)(-5,-2); those for Φv\Phi_v are (−4,−5)(-4,-5), (−3,−5)(-3,-5), (−3,−4)(-3,-4), all between −5-5 and 0. For example,

Φv(sj)=A(z−3)+B(sj−1−4)−1=(sj−6+2)+(sj−4+2)−1=z−3.\Phi_v(s_j) = A(z - 3) + B(s_{j-1} - 4) - 1 = (s_{j-6} + 2) + (s_{j-4} + 2) - 1 = z - 3.

Here v≥3v \ge3 and k0−1−v=sj−1−5>0k_0 - 1 - v = s_{j-1} - 5 > 0. Lemma 3 therefore gives

min⁡{k:A(k)=z−4}=sj−1,B(sj−2)=z−3.(9)\min\{k : A(k) = z - 4\} = s_j - 1,\qquad B(s_j - 2) = z - 3. \tag*{(9)}

Completing the tables

In either case we now know A(k0)A(k_0) and B(k0−1)B(k_0 - 1) at the left endpoint. Apply (6) and (5) alternately to obtain

B(k0),A(k0+1),B(k0+1),A(k0+2),…B(k_0),\quad A(k_0 + 1),\quad B(k_0 + 1),\quad A(k_0 + 2),\quad\ldots

The values already obtained in the new window determine the arguments of the next calls. The values at those arguments come from the known tables at levels j−3j - 3 and j−1j - 1.

For clarity, write k=sj+tk = s_j + t. If B(k−1)=z+bB(k - 1) = z + b, the two arguments used to compute A(k)A(k) have offsets

(b, 6+t−b)at an even level,(b, t−7−b)at an odd level,(b,\,6 + t - b)\quad\text{at an even level},\qquad(b,\,t - 7 - b)\quad\text{at an odd level},

relative to sj−3s_{j-3} and sj−1s_{j-1}, respectively. The functions read there are AA and BB. Once A(k)=z+aA(k) = z + a is known, the two arguments used to compute B(k)B(k) have offsets

(a, 7+t−a)at an even level,(a, t−6−a)at an odd level,(a,\,7 + t - a)\quad\text{at an even level},\qquad(a,\,t - 6 - a)\quad\text{at an odd level},

and both calls read AA. The two source value centers add to z+7z + 7 at an even level and to z−6z - 6 at an odd level. Including the −1-1 in (5), the resulting offsets from zz are therefore the sums of the two table entries plus 6, 7 in the even case and minus 7, 6 in the odd case, for A,BA,B, respectively.

The following table lists all source offsets. Each pair gives the offset at level j−3j - 3 first, then that at level j−1j - 1; the first AA-value was fixed by the first-passage argument. For example, at the start of an even-level table,

Even level jjOdd level jj
ttfor AAfor BBttfor AAfor BB
−5-5fixed(1,1)(1,1)−1-1fixed(−4,−3)(-4,-3)
−4-4(1,1)(1,1)(1,2)(1,2)00(−3,−4)(-3,-4)(−3,−3)(-3,-3)
−3-3(2,1)(2,1)(2,2)(2,2)11(−2,−4)(-2,-4)(−3,−2)(-3,-2)
−2-2(3,1)(3,1)(2,3)(2,3)22(−2,−3)(-2,-3)(−2,−2)(-2,-2)
−1-1(3,2)(3,2)(2,4)(2,4)33(−2,−2)(-2,-2)(−2,−1)(-2,-1)
00(3,3)(3,3)(2,5)(2,5)44(−2,−1)(-2,-1)(−2,0)(-2,0)
55(−2,0)(-2,0)(−1,0)(-1,0)

Table 1.

B(sj−5)=A(z+1)+A(sj−1+1)=(sj−6−3)+(sj−4−3)=z+1.B(s_j-5)=A(z+1)+A(s_{j-1}+1)=(s_{j-6}-3)+(s_{j-4}-3)=z+1.

At the start of an odd-level table,

B(sj−1)=A(z−4)+A(sj−1−3)=(sj−6+1)+(sj−4+2)=z−3.B(s_j-1)=A(z-4)+A(s_{j-1}-3)=(s_{j-6}+1)+(s_{j-4}+2)=z-3.

All offsets in the even case lie in the earlier odd window [−1,5][-1,5], and all offsets in the odd case lie in the earlier even window [−5,0][-5,0]. Reading these entries in order gives precisely (9)–(10), completing the induction and proving Proposition 4.

At t=0t=0, the proposition gives

A(sj)−sj−3B(sj)−sj−3j even24j odd−3−2(10)\begin{array}{c|cc} & A(s_j)-s_{j-3} & B(s_j)-s_{j-3} \\ j\ \text{even} & 2 & 4 \\ j\ \text{odd} & -3 & -2 \tag*{(10)} \end{array}

Since Tj=2sjT_j=2s_j, these are the exact identities

C(Tj)=Tj−3+{7,j even,−5,j odd,(11)C(T_j)=T_{j-3}+ \begin{cases} 7, & j\ \text{even},\\ -5, & j\ \text{odd}, \end{cases} \tag*{(11)}
C(Tj−1)=Tj−3+{3,j even,−7,j odd,(j≥3).(12)C(T_j-1)=T_{j-3}+ \begin{cases} 3, & j\ \text{even},\\ -7, & j\ \text{odd}, \end{cases} \qquad(j\ge3). \tag*{(12)}

The global estimate

The reference indices are geometrically spaced. To control the values between them, we expand the two recurrences through many levels and use a quadratic bound on the resulting weighted averages. The exact values from § 4 ensure that every argument in this expansion remains at the expected scale.

Geometric scales and bounded errors

Observe from (3) that Tj−1−133(−1)jT_j-1-\frac{13}{3}(-1)^j satisfies the homogeneous Narayana recurrence uj=uj−1+uj−3u_j=u_{j-1}+u_{j-3}. Its initial values are positive. The characteristic polynomial x3−x2−1x^3-x^2-1 has one real root ψ>1\psi>1; the other two roots are conjugate and have modulus ψ−1/2<1\psi^{-1/2}<1. The coefficient of ψj\psi^j in the solution is positive, since positivity excludes a negative coefficient and the positive recurrence keeps the terms bounded away from zero. It follows that, for some κ>0\kappa>0,

sj=κψj+O(1).(13)s_j=\kappa\psi^j+O(1). \tag*{(13)}

The sequence (sj)(s_j) is increasing: the initial values are increasing, and (8) gives sj−sj−1≥sj−3−7>0s_j-s_{j-1}\ge s_{j-3}-7>0. In particular, (11)–(12) give a bounded error from the line ψ−3n\psi^{-3}n on both parities at the selected indices.

By (10) and (8), for F=AF=A or BB and j≥3j\ge3,

∣F(sj)−sj−3∣≤4,∣sj−F(sj)−sj−1∣≤5.(14)\lvert F(s_j)-s_{j-3}\rvert\le4,\qquad\lvert s_j-F(s_j)-s_{j-1}\rvert\le5. \tag*{(14)}

Thus either map moves three reference levels down, while either complementary map moves one level down, with uniformly bounded errors. These shifts explain the weights ψ−3\psi^{-3} and ψ−1\psi^{-1}, whose sum is 1. The 1-Lipschitz property ensures that an error already present is not enlarged by further composition.

We also remove the shifts in (5)–(6), at a bounded cost:

−2≤A(k)−A(B(k))−B(k−B(k))≤0,(15)-2\le A(k)-A(B(k))-B(k-B(k))\le0, \tag*{(15)}
0≤B(k)−A(A(k))−A(k−A(k))≤1(k≥0).(16)0\le B(k)-A(A(k))-A(k-A(k))\le1 \qquad(k\ge0). \tag*{(16)}

For (15), replacing B(k−1)B(k-1) by B(k)B(k) leaves error −1-1 if the two values agree. Otherwise they differ by one, and the error is

−1−(A(B(k))−A(B(k)−1))+(B(k−B(k)+1)−B(k−B(k))),-1-\bigl(A(B(k))-A(B(k)-1)\bigr)+\bigl(B(k-B(k)+1)-B(k-B(k))\bigr),

which lies in [−2,0][-2,0]. For (16), removing the +1+1 in (6) changes one AA-value by zero or one. The cases k=0,1k=0,1 are checked directly.

The recursion tree

Fix an integer N≥1N\ge1. A node is labeled by a binary word ww recording the successive branch choices. The empty word ε\varepsilon labels the root. At node ww, we record an argument xwx_w and the function Fw∈{A,B}F_w\in\{A,B\} evaluated there. Choose Fε=AF_\varepsilon=A or BB and put xε=Nx_\varepsilon=N. Equations (15)–(16) suggest the following expansion:

Fw(xw0,Fw0)(xw1,Fw1)A(B(xw),A)(xw−B(xw),B)B(A(xw),A)(xw−A(xw),A)(17)\begin{array}{c|c|c} F_w & (x_{w0},F_{w0}) & (x_{w1},F_{w1})\\ \hline A & (B(x_w),A) & (x_w-B(x_w),B)\\ B & (A(x_w),A) & (x_w-A(x_w),A) \tag*{(17)} \end{array}

In each row the two child arguments add to xwx_w, while their evaluated values add to Fw(xw)F_w(x_w) with an error of absolute size at most 2. Branch 0 always leads to AA, whereas branch 1 switches AA and BB. All arguments lie in {0,…,N}\{0,\ldots,N\}.

Write ∣w∣0,∣w∣1\lvert w\rvert_0,\lvert w\rvert_1 for the numbers of zeros and ones in ww, and give the path the weight

ρw=ψ−3∣w∣0−∣w∣1,ρε=1.\rho_w=\psi^{-3\lvert w\rvert_0-\lvert w\rvert_1},\qquad\rho_\varepsilon=1.

For the linear model A(x)=B(x)=ψ−3xA(x)=B(x)=\psi^{-3}x, the argument at ww would be NρwN\rho_w. We therefore normalize by this scale:

Xw=xwNρw,Yw=Fw(xw)Nρw.(18)X_w=\frac{x_w}{N\rho_w},\qquad Y_w=\frac{F_w(x_w)}{N\rho_w}. \tag*{(18)}

At the root, Xε=1X_\varepsilon=1 and YεY_\varepsilon is A(N)/NA(N)/N or B(N)/NB(N)/N. Since xw0+xw1=xwx_{w0}+x_{w1}=x_w, we have the exact relation

Xw=ψ−3Xw0+ψ−1Xw1.(19)X_w=\psi^{-3}X_{w0}+\psi^{-1}X_{w1}. \tag*{(19)}

The corresponding relation for YY has a small error inherited from (15)–(16). The next lemma controls the root error from a common bound on XX and a bound on that one-step error.

A finite averaging estimate

The decisive feature of (17) is that reversing two branch choices preserves their weight but changes the function reached: 10 ends at AA and 01 at BB. At the latter node, AA supplies the next splitting argument. This lets us compare an AA-value with a nearby argument at the same scale. The proof turns that comparison into a bound by summing squared increments over the tree.

Lemma 5 (Tree averaging estimate). Construct (17) to depth H≥3H \ge3 and use (18). Suppose that

0≤Xw≤K(∣w∣≤H),∣Yw−ψ−3Yw0−ψ−1Yw1∣≤δ(∣w∣<H)0 \le X_w \le K \quad(|w| \le H), \qquad|Y_w-\psi^{-3}Y_{w0}-\psi^{-1}Y_{w1}| \le\delta\quad(|w|<H)

for constants KK and δ≥0\delta\ge0. Then, for either initial choice of AA or BB at the root.

∣Yε−ψ−3∣≤K51ψ4+15ψH−2+3Hδ.(20)|Y_\varepsilon-\psi^{-3}| \le K\sqrt{\frac{51\psi^4+15\psi}{H-2}}+3H\delta. \tag*{(20)}

Proof. Let Dw=Yw−ψ−3XwD_w=Y_w-\psi^{-3}X_w. At the root this is the required error Yε−ψ−3Y_\varepsilon-\psi^{-3}, and (19) shows that DD has the same averaging error as YY. Because DwD_w satisfies the weighted-mean relation only up to a residual bounded by δ\delta, its squared increments do not telescope cleanly across levels. To restore exact telescoping, we replace DwD_w by the exact backward average VwV_w of its terminal values at depth HH: set Vw=DwV_w=D_w there and define Vw=ψ−3Vw0+ψ−1Vw1V_w=\psi^{-3}V_{w0}+\psi^{-1}V_{w1} upwards. Since 0≤Yw≤Xw≤K0\le Y_w\le X_w\le K, both ∣Dw∣|D_w| and ∣Vw∣|V_w| are at most KK, and backward induction gives

∣Vw−Dw∣≤(H−∣w∣)δ.(21)|V_w-D_w|\le(H-|w|)\delta. \tag*{(21)}

For any quantity ZwZ_w, write EℓZw=∑∣w∣=ℓρwZw\mathbb{E}_{\ell}Z_w=\sum_{|w|=\ell}\rho_w Z_w. Define the mean square increment of XX and the mean square of VV by

eℓ=Eℓ[ψ−3(Xw0−Xw)2+ψ−1(Xw1−Xw)2],mℓ=EℓVw2.e_\ell=\mathbb{E}_{\ell}\left[\psi^{-3}(X_{w0}-X_w)^2+\psi^{-1}(X_{w1}-X_w)^2\right], \qquad m_\ell=\mathbb{E}_{\ell}V_w^2.

The exact average relation gives

ψ−3Xw02+ψ−1Xw12−Xw2=ψ−3(Xw0−Xw)2+ψ−1(Xw1−Xw)2.\psi^{-3}X_{w0}^2+\psi^{-1}X_{w1}^2-X_w^2=\psi^{-3}(X_{w0}-X_w)^2+\psi^{-1}(X_{w1}-X_w)^2.

Averaging and summing over the levels makes the left side telescope. Applying the same identity to VV, we obtain

∑ℓ=0H−1eℓ=EHXw2−Xε2≤K2,mℓ+1≥mℓ,mH≤K2.(22)\sum_{\ell=0}^{H-1}e_\ell=\mathbb{E}_{H}X_w^2-X_\varepsilon^2\le K^2,\qquad m_{\ell+1}\ge m_\ell,\qquad m_H\le K^2. \tag*{(22)}

Equivalently, XX and VV are bounded martingales along a path with branch probabilities ψ−3\psi^{-3}, ψ−1\psi^{-1}. In particular, the total mean square change is bounded independently of HH.

We now relate the errors DD to these increments. The two paths 10 and 01 satisfy

Fw10=A,Fw01=B,ρw10=ρw01=ψ−4ρw.F_{w10}=A,\qquad F_{w01}=B,\qquad\rho_{w10}=\rho_{w01}=\psi^{-4}\rho_w.

The weights are unchanged when the order is reversed, whereas the function labels are different. At w01w01 the next branch 0 uses AA as its splitting map, so xw010=A(xw01)x_{w010}=A(x_{w01}) and

A(xw01)Nρwψ−4−ψ−3Xw01=ψ−3(Xw010−Xw01).\frac{A(x_{w01})}{N\rho_w\psi^{-4}}-\psi^{-3}X_{w01}=\psi^{-3}(X_{w010}-X_{w01}).

The function x↦A(x)−ψ−3xx\mapsto A(x)-\psi^{-3}x is 1-Lipschitz, since its increment between u≤vu\le v lies between −ψ−3(v−u)-\psi^{-3}(v-u) and ψ−1(v−u)\psi^{-1}(v-u). Comparing it at xw10x_{w10} and xw01x_{w01}, with the same denominator Nρwψ−4N\rho_w\psi^{-4}, gives

∣Dw10∣≤∣Xw10−Xw01∣+ψ−3∣Xw010−Xw01∣.(23)|D_{w10}|\le|X_{w10}-X_{w01}|+\psi^{-3}|X_{w010}-X_{w01}|. \tag*{(23)}

Thus an error in an evaluated value is bounded by changes of the normalized arguments. Insert w1,w,w0w1,w,w0 between w10w10 and w01w01. The right side of (23) is at most

∣Xw1−Xw∣+∣Xw10−Xw1∣+∣Xw0−Xw∣+∣Xw01−Xw0∣+ψ−3∣Xw010−Xw01∣.\lvert X_{w1}-X_w\rvert+\lvert X_{w10}-X_{w1}\rvert+\lvert X_{w0}-X_w\rvert+\lvert X_{w01}-X_{w0}\rvert+\psi^{-3}\lvert X_{w010}-X_{w01}\rvert.

Its square is at most five times the sum of the five squares. For 0≤ℓ≤H−30\leq\ell\leq H-3, the weighted means of these squares are bounded, in the displayed order, by

ψeℓ,ψ4eℓ+1,ψ3eℓ,ψ4eℓ+1,ψeℓ+2.\psi e_\ell,\quad\psi^4 e_{\ell+1},\quad\psi^3 e_\ell,\quad\psi^4 e_{\ell+1},\quad\psi e_{\ell+2}.

For example, choosing the suffix 10 has weight ψ−4\psi^{-4}, which explains the factor ψ4\psi^4 in the second bound. In the last term, the coefficient ψ−6\psi^{-6} cancels the two prescribed zero-branch weights. Hence

EℓDw102≤5ψ4(eℓ+2eℓ+1+ψ−3eℓ+2).(24)\mathbb{E}_\ell D_{w10}^2\leq5\psi^4(e_\ell+2e_{\ell+1}+\psi^{-3}e_{\ell+2}). \tag*{(24)}

It remains to pass from the selected grandchild w10w10 to its parent. The two-step variance identity for VV is

mℓ+2−mℓ=Eℓ∑∣u∣=2ρu(Vwu−Vw)2.m_{\ell+2}-m_\ell=\mathbb{E}_\ell\sum_{\lvert u\rvert=2}\rho_u(V_{wu}-V_w)^2.

Keeping the nonnegative term with u=10u=10 gives

Eℓ(Vw10−Vw)2≤ψ4(mℓ+2−mℓ).\mathbb{E}_\ell(V_{w10}-V_w)^2\leq\psi^4(m_{\ell+2}-m_\ell).

Decompose

Vw=Dw10+(Vw10−Dw10)+(Vw−Vw10).V_w=D_{w10}+(V_{w10}-D_{w10})+(V_w-V_{w10}).

By (21), the middle term has absolute size at most HδH\delta. The inequality (a+b+c)2≤3(a2+b2+c2)(a+b+c)^2\leq3(a^2+b^2+c^2) therefore yields

mℓ≤3EℓDw102+3H2δ2+3ψ4(mℓ+2−mℓ).m_\ell\leq3\mathbb{E}_\ell D_{w10}^2+3H^2\delta^2+3\psi^4(m_{\ell+2}-m_\ell).

Sum over ℓ=0,…,H−3\ell=0,\ldots,H-3. Each mℓm_\ell is at least m0=Vε2m_0=V_\varepsilon^2. From (22) and (24),

∑ℓ=0H−3EℓDw102≤5ψ4(3+ψ−3)K2,∑ℓ=0H−3(mℓ+2−mℓ)≤2K2.\sum_{\ell=0}^{H-3}\mathbb{E}_\ell D_{w10}^2\leq5\psi^4(3+\psi^{-3})K^2,\qquad \sum_{\ell=0}^{H-3}(m_{\ell+2}-m_\ell)\leq2K^2.

For the second inequality, the sum telescopes to mH−2+mH−1−m0−m1m_{H-2}+m_{H-1}-m_0-m_1. Consequently,

(H−2)Vε2≤(51ψ4+15ψ)K2+3(H−2)H2δ2.(H-2)V_\varepsilon^2\leq(51\psi^4+15\psi)K^2+3(H-2)H^2\delta^2.

Taking square roots and using (21) once more at the root gives (20), since 1+3<31+\sqrt{3}<3.

The factor H−1/2H^{-1/2} comes from summing a square estimate over H−2H-2 levels: a fixed error at the root contributes at every level, while the total squared change stays bounded. We now use the reference values to allow a logarithmic choice of HH.

A logarithmic depth

Fix JJ by sJ≤N<sJ+1s_J\leq N<s_{J+1} and take H=⌊J/6⌋H=\lfloor J/6\rfloor, with JJ sufficiently large. For a path ww, put

d(w)=3∣w∣0+∣w∣1,ρw=ψ−d(w).d(w)=3\lvert w\rvert_0+\lvert w\rvert_1,\qquad\rho_w=\psi^{-d(w)}.

This counts the reference levels lost along the path. Since d(w)≤3H≤J/2d(w)\leq3H\leq J/2, all reference levels used below are at least 3. Monotonicity, the Lipschitz bounds, and (14) give by induction along a path

xw≤sJ+1−d(w)+5∣w∣(∣w∣≤H).(25)x_w\leq s_{J+1-d(w)}+5\lvert w\rvert\qquad(\lvert w\rvert\leq H). \tag*{(25)}

Indeed, if the current argument is at most si+es_i+e, either branch-0 map is at most si−3+e+5s_{i-3}+e+5, and either complementary map is at most si−1+e+5s_{i-1}+e+5. Each step adds at most 5 to the previous error.

Dividing (30) by NρwN\rho_w and using (18), uniformly in ww,

0≤Xw≤κψJ+1+O((H+1)ψ3H)N≤K0 \le X_w \le\frac{\kappa\psi^{J+1}+O((H+1)\psi^{3H})}{N} \le K

for a fixed constant KK. Here N≍ψJN\asymp\psi^J, whereas 3H≤J/23H\le J/2. Thus the first hypothesis of Lemma 5 holds. For the second, (20)–(21) give

∣Yw−ψ−3Yw0−ψ−1Yw1∣≤2Nρw≤2ψ3HN.\lvert Y_w-\psi^{-3}Y_{w0}-\psi^{-1}Y_{w1}\rvert\le\frac{2}{N\rho_w}\le\frac{2\psi^{3H}}{N}.

We may therefore take δ=2ψ3H/N\delta=2\psi^{3H}/N. For either root function F=AF=A or BB, the lemma gives

∣F(N)N−ψ−3∣≤K51ψ4+15ψH−2+6Hψ3HN=O(J−1/2).\left\lvert\frac{F(N)}{N}-\psi^{-3}\right\rvert\le K\sqrt{\frac{51\psi^4+15\psi}{H-2}}+\frac{6H\psi^{3H}}{N}=O(J^{-1/2}).

The second term is O(Jψ−J/2)O(J\psi^{-J/2}), and log⁡N=Jlog⁡ψ+O(1)\log N=J\log\psi+O(1). Hence

A(N)=ψ−3N+O(Nlog⁡N),B(N)=ψ−3N+O(Nlog⁡N).A(N)=\psi^{-3}N+O\left(\frac{N}{\sqrt{\log N}}\right),\qquad B(N)=\psi^{-3}N+O\left(\frac{N}{\sqrt{\log N}}\right).

Returning to C(2N)=2B(N)−1C(2N)=2B(N)-1 and C(2N−1)=2A(N)−1C(2N-1)=2A(N)-1 proves Theorem 1.

Further questions

Is the order n/log⁡nn/\sqrt{\log n} in Theorem 1 optimal? What is the corresponding normalized limsup? On the upper side of the limiting line, we conjecture a bounded error.

Conjecture 6. For every n≥111n\ge111,

C(n)<nφ3+2.C(n)<\frac{n}{\varphi^3}+2.

A combinatorial description of the intervals between the reference points could explain the shapes of the arches and help determine the optimal order of the error.

Acknowledgments

The author thanks Jeffrey Shallit for discussions and automata computations. The repeating patterns in an automaton he supplied suggested the search for the local tables used in the proof.

The finite initial calculation

The following Python 3 program verifies the three initial tables in Proposition 4 in integer arithmetic. The lists aa and bb contain the two rows for even and odd levels, and lo their first offsets.

C = [0, 1, 1]
for n in range(3, 3271):
    u = C[n-1]
    assert 1 <= u < n and 1 <= n-u < n
    C.append(C[u] + C[n-u] + (1 if n % 2 == 0 else -1))
    assert C[n] > 0 and C[n] % 2 == 1
    assert C[n] - C[n-2] in (0, 2)

s = [244, 352, 521, 758, 1116, 1630]
lo = [-5, -1]
aa = [[1,1,2,2,2,2], [-4,-3,-3,-2,-2,-2,-1]]
bb = [[1,2,3,3,3,4], [-3,-2,-2,-2,-2,-2,-2]]
for j in (3, 4, 5):
    e = j % 2
    for i in range(len(aa[e])):
        k = s[j] + lo[e] + i
        assert (C[2*k-1]+1)//2 == s[j-3] + aa[e][i]
        assert (C[2*k]+1)//2 == s[j-3] + bb[e][i]
print("PASS: all three initial tables")

References

  1. [1]C. L. Mallows, Conway’s challenge sequence, Amer. Math. Monthly 98 (1991), 5–20. doi:10.1080/00029890.1991.11995694.DOI
  2. [2]T. Kubo and R. Vakil, On Conway’s recursive sequence, Discrete Math. 152 (1996), 225–252. doi:10.1016/0012-365X(94)00303-Z.DOI
  3. [3]M. Mantovanelli, Dyadic self-similarity in a perturbed Hofstadter Q-recursion, preprint, 2026. arXiv:2603.16111v1.
  4. [4]B. Cloitre, The Mantovanelli–Hofstadter Sequence, preprint, 2026. arXiv:2604.06237.arxiv.org/abs/2604.06237
  5. [5]B. Cloitre, entry A399773, The On-Line Encyclopedia of Integer Sequences, 2026.
  6. [6]B. Cloitre, On the Mallows–Conway Sequence, manuscript, 2026.
  7. [7]J. Shallit, conjectural automaton for the positive part of C − R in Narayana numeration, private communication to B. Cloitre, October 2026.

Paper details

vlnc:W_rrvhrfnv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents