There is this a simple looking and intuitive statement but I am not sure how to start approaching this problem.
Let $S=\{s_1,s_2,\ldots,s_n\}$, where $s_1,s_2,\ldots,s_n>0$ such that $s_1+s_2+\ldots+s_n=k$. We need to show that if $k\leq2n-1$, then for every $i=1,\ldots,k$, $S$ has a subset whose elements sum to $i$.
I found an example where $k>2n-1$ to the statement above:
$1+2+3+4+5=15$, where we have $s_1=1, s_2=2, s_3=3, s_4=4, s_5=5$ and $n=5$
$i=1:1$
$i=2:2$
$i=3:3$
$i=4:4$
$i=5:5$
$i=6:1+5=2+4$
$i=7:2+5=3+4$
$i=8:3+5$
$i=9:4+5$
$i=10:1+4+5$
$i=11:2+4+5$
$i=12:3+4+5$
$i=13:1+3+4+5$
$i=14:2+3+4+5$
$i=15:1+2+3+4+5$
where $2n-1=2(5)-1=9$ and $k=15>2n-1=9$.
How can we show that if $k\leq2n-1$ then we must have example above?
My idea is to model the integers as unit integer 1. Let $s_1=s_2=\ldots=s_n=2$, then $s_1+s_2+\ldots+s_n=2n$. If we take away at least 1, from one of $s_1,s_2,\ldots,s_n$, then we have at least one of $s_1,s_2,\ldots,s_n$ equals to 1. Then we can easily get any $i=1,\ldots,k$ by combination of the sum of $2$'s and $1$'s.
But my working only works if $s_1=s_2=\ldots=s_n=2$. How to show for general $\{s_1,s_2,\ldots,s_n\}$?
Can we use prove by contradiction?
Can somebody please give some light in proving the statement?
Thanks.
EDITED
Thanks @Doug M for the hint:
Let's try by induction:
BASE CASE: $s_1=s_1$, then $i=k$ and $S$ has a subset whose elements sum to $k$.
INDUCTION HYPOTHESIS: Suppose $s_1+s_2+\ldots+s_N=K$ and if $K\leq2N-1$ then the statement be true.
Now we have $s_1+s_2+\ldots+s_N+s_{N+1}=K+s_{N+1}$ and suppose $K+s_{N+1}\leq2(N+1)-1=2N+1$
By the induction hypothesis, we have $K\leq2N-1$, then it implies $K+s_{N+1}\leq2N-1+s_{N+1}$
But then I am not sure how to show the statement is true for the set $\{s_1,s_2,\ldots,s_N+s_{N+1}\}$?
Suppose it holds for $<n$. We need to prove it for $n$. Let's choose an arbitrary example for $n$: $$\sum_{j=1}^n s_j=k\leq 2n-1$$
If the $s$ lot only contains ones, it's obvious. Otherwise we remove any $s_j>1$. The reduced lot of $n-1$ numbers adds up to $m=k-s_j\leq 2(n-1)-1$ (equal if k=2n-1 and we removed a 2). Note that $m\geq n-1$ and $s_j\leq n$. To construct numbers up to $m$ we can use the reduced lot (which we can because the statement holds for $n-1$). What about from $m+1$ to $k$? Let's call such a number $\ell$. We can construct $\ell-s_j$ from the reduced lot because $0\leq\ell-s_j\leq m$ (at least zero because $\ell\geq m+1\geq n$ and $s_j\leq n$; no more than $m$ because $\ell\leq k$, so $\ell-s_j\leq k-s_j=m$), and then we just add the $s_j$.