Boundary Layers in the Carry Distribution of Canonical k-bonacci Numeration

Author: Paul Higham
Date: 24 July 2026
Status: Preprint

This paper studies how carries propagate when adding one in canonical k-bonacci numeration systems. Although these systems become increasingly similar to ordinary binary arithmetic as k grows, the convergence is surprisingly subtle. The paper derives the exact limiting carry distribution, proves that the mean carry length is exactly two for every k, and identifies a travelling boundary layer that governs the leading deviation from binary behaviour.

Abstract

Canonical k-bonacci numeration represents integers by binary words avoiding a forbidden block of k consecutive ones. As k increases, this restriction becomes progressively weaker, suggesting that the associated arithmetic should approach ordinary binary arithmetic. In this paper we investigate the distribution of carry lengths arising when one is added to a uniformly chosen integer.

We derive an exact recurrence for the carry spectrum by exploiting the recursive decomposition of the admissible language. This recurrence yields rational generating functions whose common characteristic polynomial is that of the k-bonacci recurrence. Explicit formulae for the limiting carry probabilities are obtained from the dominant pole.

We show that the carry distribution admits two distinct first-order asymptotic corrections. For every fixed carry length, the probabilities differ from the binary distribution by a diffuse bulk correction. In addition, a moving boundary layer centred at carry length k contributes a correction concentrated in a narrow window whose rescaled profile converges to an explicit geometric limit.

The interaction between these two structures determines the asymptotic moments of the carry distribution. In particular, we prove that the limiting mean carry length is exactly 2 for every k ≥ 2, and derive the leading asymptotic behaviour of the variance. Thus the dominant deviation from binary arithmetic is generated by the first boundary layer, while the bulk contributes only a lower-order correction. The analysis suggests a general framework in which local statistics of recursive numeration systems are governed by homogeneous recurrences together with boundary forcing arising from the recursive decomposition of the underlying language.

Current version: July 2026. Comments and corrections are welcome.