For 0<s1<⋯<sn, adding the largest integer creates at least n new sums of subsets. If P=∑i<nsi is the previous maximum, the values P+sn and P+sn−si for i<n are distinct new sums above P. Induction gives the displayed bound. Equality holds for si=i, whose subsetsums fill the interval of integers from zero to n(n+1)/2.