CLRS §4.3: general lower substitution for smaller recursive children
ProvedCLRS.Chapter4Substitution.lower_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.lower_comparison (children : Nat → List Nat) (toll : Nat → Nat)
(cutoff : Nat) (cost candidate : Nat → Nat)
(smaller : SmallerChildren children cutoff)
(base : ∀ n, n < cutoff → candidate n ≤ cost n)
(recurrence : LowerRecurrence children toll cutoff cost)
(substitution : LowerCandidate children toll cutoff candidate) :
∀ n, candidate n ≤ cost n := by sorry