# Math Help - Proof by induction

1. ## Proof by induction

Show that for a set the sums of elements in the subsets of can produce any element of the set .

2. Originally Posted by usagi_killer
Show that for a set the sums of elements in the subsets of can produce any element of the set .

For n= 1 (and for n= 2,3 also) the result is easily checked, so assume the result is true for k up to n-1 and prove for k = n.

Now, let $1\le m\le \frac{m(m+1)}{2}$:

1) If $m\le \frac{(m-1)m}{2}$ then apply the inductive hypothesis to the subset $N:=\{1,2,...,n-1\}\subset\{1,2,...,n\}=\mathbb{S}$, otherwise;

2) $k\in \left\{\frac{n(n-1)}{2}+1,\frac{(n-1)n}{2}+2,\ldots,\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}\right\}$ , and then it's easy to see that $k=1+2+\ldots+(n-1)+k$ , with $1\le k\le n$

Tonio