Distinct-positive-integer subset-sum lower bound

ID: distinct-positive-integer-subset-sum-lower-bound

For , adding the largest integer creates at least new sums of subsets. If is the previous maximum, the values and for are distinct new sums above . Induction gives the displayed bound. Equality holds for , whose subset sums fill the interval of integers from zero to .

New to topics? Read the docs here!