How to prove that any number from $0$ to $\frac{n(n+1)}{2}$ can be obtained as sum of subset of set {$1,2,3, ... ,n$} I tried to prove it using pigeon hole principle (by proving that $\frac{n(n+1)}{2}$ distinct numbers can be obtained as sum).
Edit :
some good answers are already posted. Thanks to all of them. Do share a proof using different methods . It's sad that i cannot accept more than one answer.
 A: By induction.  Easy to confirm for small $n$.  
Suppose the claim is true for $n-1$, so we can get every number from $0$ to $\frac {n(n-1)}2$ just using $\{0,1,\cdots, n-1\}$.  Now we add the element $n$ and we seek to get the numbers from $\frac {n(n-1)}2+1$ to $\frac {n(n+1)}2$.  But $$\frac {n(n+1)}2-\frac {n(n-1)}2=n$$ so subtracting $n$ from any of those numbers gets you into the previously solved range, so we are done.
A: The pigeonhole principle can't tell you that all of the holes are filled.  Induction is the way to go.  

All of the numbers from $0$ to $1$ can be formed as sums of subsets of $\{1\}$.
Now, assume that $k\in \mathbb N$ is such that all the numbers from 0 through $\frac {k(k+1)}2$ can be expressed as the sum of a subset of $1..k$.  Now, let $n$ between $0$ and $\frac {(k+1)(k+2)}2$.  
By induction, the proposition follows.


*

*If $n\le \frac {k(k+1)}2$, then it can be expressed as a sum of a subset of $1..k$ which is clearly also a subset of $1..(k+1)$

*If $\frac {k(k+1)}2<n\le \frac {(k+1)(k+2)}2$, then consider $n'=n-(k+1)$.  $0\le n'\le \frac {k(k+1)}2$, so $n'$ can be expressed as a sum of a subset of $1..k$.  Appending $(k+1)$ to that subset gives a subset of $1..(k+1)$ that adds to $n$.

A: $m\in\mathbb{N}^+$ can be written as a sum of distinct elements from $\{1,2,\ldots,n\}$ iff the coefficient of $x^m$ in
$$ (1+x)(1+x^2)\cdot\ldots\cdot(1+x^n)$$
is positive. On the other hand all the coefficients of 
$$ q_n(x)=\prod_{k=1}^{n}(1+x^k)$$
are positive. This can be shown by induction: the claim holds for $n=1$ and 
$$ q_{n+1}(x) = (1+x^{n+1})q_n(x), $$
so for any $m\in\left[0,\frac{n(n+1)}{2}\right]$ we have
$$ [x^m] q_{n+1}(x) \geq [x^m]q_n(x) > 0 $$
and for any $m\in\left[\frac{n(n+1)}{2}+1,\frac{(n+1)(n+2)}{2}\right]$ we have
$$ [x^m] q_{n+1}(x) = [x^{m-n-1}] q_n(x) > 0.$$
A: Induction.  
If $n>2$ then $n \le \frac {(n-1)n}2$ and $\frac {n(n+1)}2 - n = \frac {(n-1)n}2$.
Base Cases:
$n=0,1,2$ then $0 = \sum_{k \in \emptyset} k$
$n=1,2$ then $1=\sum_{k\in\{1\}} k$.
$n=2$ then $2=\sum_{k\in \{2\}}k$ and $3=\sum_{k\in \{1,2\}} k$.
Induction:
Assume true for $k = n-1$. That is, every integer, $m$ from $0$ to $\frac {(n-1)n}2$ is the sum of a subset of $\{1,2,....,n-1\}$.  Call such a subset $K_m$.
Now if $m \le \frac {(n-1)n}2$ then $m = \sum\limits_{k\in K_m\subset \{1,....,n-1\} \subset\{1,....,n\}} k$
And if $\frac {(n-1)n}2 < m \le \frac {n(n+1)}2$ then $0 \le m -n \le \frac {n(n-1)}2$.  So there is a set $K_{m-n}\subset \{1,2,....,n-1\}$ where $m-n = \sum\limits_{k\in K_{m-n}} k$.
And so $m = n + \sum\limits_{k\in K_{m-n}} k= \sum\limits_{k\in K_{m-n}\cup \{n\}\subset \{1,2,....n\}} k$.
A: We know that the sum of first $n$ natural numbers is $\dfrac{n(n+1)}{2}$.
So  , 
$$1+2+3+4+...+n =\dfrac{n(n+1)}{2}$$
By rearranging , we can show that :
$$\dfrac{n(n+1)}{2} -1 = 2+3+4+..+n$$
$$\dfrac{n(n+1)}{2} -2 = 1+3+4+..+n$$
$$\dfrac{n(n+1)}{2} -3 = 1+2+3+..+n$$
$$\vdots$$
