Equivalence of OEIS A007729 and A174868
Michael J. Collins David Wilson

Chiral kinetic theory in curved spacetime
    Xu-Guang Huang
    December 30, 2023
=========================================


We verify the conjecture that the sixth binary partition function <cit.> is equal (aside from the initial zero term) to the partial sums of the Stern-Brocot sequence <cit.>:  
    0,1, 2, 4, 5, 8, 10, 13, 14, 18, 21, 26, 28, 33, 36, 40, 41, 46…
.


Let b'_k be the sixth binary partition function, which is the number of ways to write k as a sum

    k = ∑_i ≥ 0ε_i 2^i

with ε_i ∈{0,1,2,3,4,5}.
We obtain

    b'_2k = b'_k + b'_k-1 + b'_k-2

by counting the number of representations of 2k with ε_0 = 0,2 or 4; in each case we have a representation ε̂ of  2k-ε_0/2 by taking ε̂_i = ε_i+1, and the correspondence is clearly one-to-one. Also  b'_2k+1=b'_2k, since we can get a representation of 2k+1 only by taking a representation of 2k and adding 1 to ε_0. Thus
 
    b'_2k   = 2b'_k-1 + b'_k    (k ) 
    
    b'_2k   = 2b'_k-1 + b'_k-2   (k )

since b'_k-1 equals either b'_k or b'_k-2. 

We eliminate the even/odd repetition by defining b_k = b'_2k. Then b_0=1,b_1=2 and

    b_2k = 2b'_2k-1 + b'_2k   =    2b_k-1 + b_k
    
    b_2k+1 = 2b'_2k + b'_2k-1   = 2b_k + b_k-1 .

This is A007729. If we prepend a zero, defining b̂_0=0 and b̂_k = b_k-1 we obtain

    b̂_2k   = 2 b̂_k + b̂_k-1
    b̂_2k+1   = 2 b̂_k + b̂_k+1 .

The same recurrence with the same initial conditions gives A174868, the partial sums of the Stern-Brocot sequence <cit.>. The Stern-Brocot sequence itself can be defined by s_0=0, s_1=1, and

    s_2k   = s_k 
    
    s_2k+1   = s_k + s_k+1 .

The partial sums are σ_k = ∑_0 ≤ i ≤ k s_k. Letting  ℓ_j = s_2j-1+s_2j = 2s_j+s_j-1 we get

    σ_2k = ∑_1 ≤ j ≤ kℓ_j  = 2σ_k + σ_k-1

and similarly with  ℓ'_j = s_2j+s_2j+1 = 2s_j+s_j+1,

    σ_2k+1 = ∑_0 ≤ j ≤ kℓ'_j  = 2σ_k + σ_k+1 .



plainnat
