# How many different sums of k elements are in the range [1,n]? [closed]

For example, with k = 2 and n = 4, in [1,4] there are sums 1+2=3, 1+3=4, 1+4=5 (or 2+3=5),2+4=6, and 3+4=7 Thus, the answer is 5.

• what have you tried for larger values of k,n? Feb 3, 2022 at 23:03
• Hint: Figure out the smallest and largest sums, call them $m$ and $M$. By looking at more examples for various small $k$ and $n$, try to find a pattern describing which sums in the range $[m,M]$ are not attainable. Then prove your pattern holds in general, and count the number of numbers fitting that pattern. Feb 3, 2022 at 23:17
• What about $3+4 (=7)$ ? Feb 3, 2022 at 23:29
• Thank you, Adam, for spotting that mistake. Edited.
– John
Feb 4, 2022 at 10:58
• The body of the Question should be used to give a complete problem statement. Splitting the problem between title and body makes it hard to follow, so try to make the body text stand on its own. Also merely stating a problem is not enough to ask a suitable Question. You should put the problem in some sort of context: where it comes from, what you tried, or what about it interests you. Feb 20, 2022 at 0:01

For simplicity, lets consider the range $$[1,100]$$ and $$k=3$$. My smalliest number would be $$1+2+3 = 6$$ and my largest would be $$98+99+100 = 297$$. Notice that I can create any number between 297 and 6 just my taking my smallest number $$1+2+3=6$$ and adding an integer to the $$3$$. So lets say I want to create the number $$50$$ then, $$1+2+(3+44)=50$$. Therefore, the total number of valid creations is $$297-6+1=294$$.

Now let us generalize this:

The easiest way to get the smallest sum is by simply adding the smallest numbers together: $$1+2 +...+k = \sum_{i=1}^ki = \frac{k(k+1)}{2}$$

The easiest way to get the largest sum is pretty much the same, but instead we want to add the largest numbers: $$n+(n-1)+(n-2)+...+(n-k+1) = \sum_{i=0}^{k-1}(n-i)$$ Thus the total amount of possible numbers is: $$\sum_{i=0}^{k-1}n-\sum_{i=0}^{k-1}i -\frac{k(k+1)}{2}+1 =kn-\frac{k(k-1)}{2}-\frac{k(k+1)}{2}+1=k(n-k)+1$$

• Hello :) it's only a typo, we have $1+2+3=6\neq 5$. Feb 4, 2022 at 9:35
• @Jochen Good catch. Will fix. Feb 4, 2022 at 13:35
• @Stan: Assuming the $k$ numbers are elements in $[1,n]$ we also have to consider multiple occurrences of elements to form valid sums. Feb 5, 2022 at 18:26
• @epi163sqrt Based on the wording of the question "How many different sums of $k$ elements are in the range", I do not think we need to account for that. The sum of $2+5$ is the same as the sum of $6+1$ and so on. Feb 6, 2022 at 13:25
• @sStand: I think we should also consider in your example $k=3$ sums as $1+1+1=3$ and $100+100+100=300$ since we do not necessarily have to select pairwise different elements from $[1,100]$. Feb 6, 2022 at 14:52