Balanced depth recurrences equal leaf work plus weighted tolls
ProvedCLRS.Chapter4RecursionTree.balanced_unrollLet and satisfy for every natural depth . Then for every ,
The initial value, arity, and toll may all be zero; no polynomial form or asymptotic regularity is assumed. The weighted sum is empty at depth zero. This is an exact numerical unrolling identity, available independently of any source program or heap representation.
Platform namespace. The imported Chapter 4 source declarations live under CLRS in this upload to avoid collisions with independently published compiler versions. The immutable source reference retains the original declaration names.
Catalog organization (2026-10-11). This record was retired from the active Chapter 4 catalog to focus the presentation on three algorithms and four reusable recurrence results. Its mathematical statement and proof status are unchanged, and existing imports and links remain valid. The retained results are CLRS.Chapter4RecursionTree.recurrence_tree_accounting. Supporting lemmas needed by the retained results are included in their accepted proof files.
import Definitions.Def_CLRS_Chapter4_RecursionTree import Definitions.Def_CLRS_Chapter4_Substitution import Std set_option autoImplicit false set_option backward.isDefEq.respectTransparency false set_option backward.defeqAttrib.useBackward true namespace CLRS end CLRS open CLRS namespace CLRS.Chapter4RecursionTree end CLRS.Chapter4RecursionTree open CLRS.Chapter4RecursionTree
theorem CLRS.Chapter4RecursionTree.balanced_unroll (arity : Nat) (cost toll : Nat → Nat)
(recurrence : ∀ depth, cost (depth+1) = arity*cost depth+toll depth) (depth : Nat) :
cost depth = arity^depth*cost 0 + weightedTolls arity depth toll := by sorry