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$}

Question

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.

Answer 1

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.

Answer 2

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$$

Answer 3

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$.

Answer 4

$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.$$

Answer 5

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$.