Summand minimality and asymptotic convergence of generalized Zeckendorf decompositions

Abstract

Given a recurrence sequence $H$, with $H_n=c_1{H}_{n-1}+\cdots +c_t{H}_{n-t}$ where $c_i\in {\mathbb{N}}_0$ for all $i$ and $c_1,c_t\ge 1$, the generalized Zeckendorf decomposition (gzd) of $m\in {\mathbb{N}}_0$ is the unique representation of $m$ using $H$ composed of blocks lexicographically less than $\sigma =(c_1,\dots ,c_t)$. We prove that the gzd of $m$ uses the fewest number of summands among all representations of $m$ using $H$, for all $m$, if and only if $\sigma$ is weakly decreasing. We develop an algorithm for moving from any representation of $m$ to the gzd, the analysis of which proves that $\sigma$ weakly decreasing implies summand minimality. We prove that the gzds of numbers of the form $v_0{H}_n+\cdots +v_{\ell }{H}_{n-\ell }$ converge in a suitable sense as $n\to \infty$, furthermore we classify three distinct behaviors for this convergence. We use this result, together with the irreducibility of certain families of polynomials, to exhibit a representation with fewer summands than the gzd if $\sigma$ is not weakly decreasing.

Version 3.0, 27 pages

References in corpus (5)

• Generalizing Zeckendorf's Theorem to f-decompositions
• The Average Gap Distribution for Generalized Zeckendorf Decompositions
• New Behavior in Legal Decompositions Arising from Non-positive Linear Recurrences
• Legal Decompositions Arising from Non-positive Linear Recurrences
• Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions

Cited by in corpus (3)

• Limiting Distributions in Generalized Zeckendorf Decompositions
• The extended Frobenius problem for Lucas series incremented by a Lucas number
• Zeckendorf's Theorem Using Indices in an Arithmetic Progression