CLRS §4.3: general upper substitution for smaller recursive children
ProvedCLRS.Chapter4Substitution.upper_comparisonLet be a finite ordered list of natural child sizes, let be the local toll, and let be a natural cutoff. At every , assume each listed child is strictly smaller than . Repeated children count with multiplicity.
Let be a cost and candidate bound. Assume at every base size and, for every ,
where both sums range over the listed children of . Then at every natural size. Unequal splits, empty child lists, and zero costs are permitted. This is a reusable numerical comparison principle; it does not assume an algorithm execution or a specific asymptotic form.
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.
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.Chapter4Substitution end CLRS.Chapter4Substitution open CLRS.Chapter4Substitution
theorem CLRS.Chapter4Substitution.upper_comparison (children : Nat → List Nat) (toll : Nat → Nat)
(cutoff : Nat) (cost candidate : Nat → Nat)
(smaller : SmallerChildren children cutoff)
(base : ∀ n, n < cutoff → cost n ≤ candidate n)
(recurrence : UpperRecurrence children toll cutoff cost)
(substitution : UpperCandidate children toll cutoff candidate) :
∀ n, cost n ≤ candidate n := by sorry