What is the number of different sums of the items of a set of consecutive natural numbers?

I have been playing around with sets of consecutive natural numbers like say $$S=\{1,2,3,...,10\}$$ and I have come up with this problem for which however I have not yet found an answer and I don't know if there is one. My problem is the following: Considering a set $$S=\{1,2,3,...,n\}$$ where $$n$$ is an arbitrary natural number, can we derive a formula that will indicate the number of different sums that will be produced by summing the items of the set $$S$$ in all different combinations? For example for the set $$S=\{1,2,3,4,5\}$$ we get: $$1+2=3\\ 1+2+3=6\\ 1+2+3+4=10\\1+3+4+5=13\\1+2+4+5=12\\1+2+3+4+5=15\\ 1+2+3+5=11\\1+4+5=10\\1+3+5=9\\1+3+4=8\\1+2+5=8\\1+2+4=7\\1+3=4\\1+4=5\\1+5=6\\ 2+3=5\\2+4=6\\2+5=7\\ 2+3+4=9\\2+3+5=10\\2+4+5=11\\ 2+3+4+5=14\\ 3+4=7\\3+5=8\\ 3+4+5=12\\ 4+5=9\\$$ So we have $$26$$ different summations and $$13$$ different sums(I hope I didn't make any mistake)

• To clarify your question: you allow sums of any number of terms? Commented Jul 17, 2022 at 18:07
• Further clarification question: you don't mention that terms in the sum have to be a string of consecutive numbers, but in your example, you only illustrate such subsets of $\{1, 2, \dots, n\}$. Is this part of the problem statement? Otherwise, you could obtain other sums like $1 + 3 = 4$. Commented Jul 17, 2022 at 18:12
• You can represent any number from $1$ to $n(n+1)/2$ this way, via a relatively simple induction proof, if you allow individual values. You might have to go from $3$ to $n(n+1)/2$ if the subsets have to have two or more elements. Commented Jul 17, 2022 at 18:41
• Specifically, if you can write $m$ as a sum of elements of your set, and $1$ isn’t in the set, you can add $1$ to the set to get a sum of $m+1.$ If $1$ is in your set, and $m<n(n+1)/2,$ then there is a $k$ in your set such that $k+1$ is not in your set. Remove $k$ and add $k+1,$ and you get a sum of $m+1.$ Commented Jul 17, 2022 at 18:46
• This is essentially a special case of a more general problem previously posted about distinct subset sums of an arbitrary set of integers. The Accepted Answer given there only provides weak upper and lower bounds on the count of distinct sums that might be achieved by subsets of fixed size $n$. Commented Jul 17, 2022 at 19:17

Here is an answer with the same content as Thomas Andrews' answer, but presented a bit more heuristically.

Since the sum of the first $$n$$ positive integers is given by $$\frac{n(n+1)}{2}$$, you can obviously make that sum with the $$n$$ integers. By removing one integer addend at a time, you can make a number which is $$1$$ smaller, and $$2$$ smaller, etc. all the way up to $$n$$ smaller, which will provide sums equal to all of the integers down to $$\frac{n(n+1)}{2}-n$$

But $$\frac{n(n+1)}{2}-n=\frac{n(n+1)}{2}-\frac{2n}{2}=\frac{n(n+1)-2n}{2}=\frac{n(n+1-2)}{2}=\frac{(n-1)n}{2}$$

You should recognize the final expression as the form of the sum of the first $$n-1$$ positive integers, which in any event is what you have when you remove $$n$$ as the addend from the set of the first $$n$$ integers.

You can reductively repeat this process to generate all smaller integer sums until you reach the set $$\{1,2\}$$, which can give you the sum $$3$$, but there is no way (using sums of two or more integers) that you can generate the sum $$2$$ or $$1$$.

Hence, the set of the first $$n$$ positive integers can generate $$\frac{n(n+1)}{2}-2$$ distinct sums.

Assuming you mean sums of $$2$$ or more elements, you can get any value between $$3$$ and $$n(n+1)/2.$$

If $$U\subsetneq \{1,2,3,\ dots,n\},$$ we can show either:

• $$1\not\in U,$$ or
• $$\exists k such that $$k\in U,$$ $$k+1\notin U$$

In the first case, we can create $$U’=U\cup\{1\},$$ and the second case we can set $$U’=U\setminus \{k\}\cup \{k+1\}.$$ In both cases: $$\sum_{j\in U’} j = 1+\sum_{j\in U} j.$$

On the case $$n=5,$$ we can construct a sequence:

\begin{align}3&=1+2\\4&=1+3\\5&=2+3\\6&=1+2+3\\7&=1+2+4\\8&=1+3+4\\9&=2+3+4\\10&=1+2+3+4\\11&=1+2+3+5\\12&=1+2+4+5\\13&=1+3+4+5\\14&=2+3+4+5\\15&=1+2+3+4+5 \end{align}

Note this sequence has the values satisfying $$n=4$$ for the values $$3$$ to $$10,$$ the values $$3$$ to $$6$$ only use values for $$n=3.$$

You can see how to extend this for $$n=6,$$ getting values $$16,\dots,21$$ via: \begin{align} 21-j&=1+2+3+4+5+6-j, j=1,\dots5,\\ 21&=1+2+3+4+5+6 \end{align}