1
$\begingroup$

In the subset sum existance problem, we have a sequence of integers. We are given an integer $x$ that we should look for a possible subsequence that sum to $x$. For example, if we have the sequence $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ and $x = 39$ then we have a subsequence $\{ 10, 9, 8, 7, 5 \}$ that sums up to $39$.

I want to prove that any sequence $[1, n]$ have a subsequence sum for any $x \in [1, n(n + 1) / 2]$. In the previous example, $n = 10$ so that any $x$ between $1$ and $55$ inclusive can be found. I have made a program and tested that this is true. Now I want to determine a proof.

3 Answers 3

1

You have verified the inductive hypothesis. Suppose that for some $n$, this is true. That is any number $1 \le x \le \frac{n(n+1)}{2}$ can be written as a sum of a sub-sequence of $\{1,\ \cdots,\ n\}$.

For $n+1$, any terms lower than $\frac{n(n+1)}{2}$ can still be formed via the induction hypothesis by simply omitting the term $n+1$. Then for any sum $S$ between $\frac{n(n+1)}{2} + 1$ and $\frac{(n+1)(n+2)}{2}$, form the corresponding sum $S - (n+1)$ using the terms from $1$ to $n$ (which is possibly via inductive hypothesis). Appending $n+1$ will then give you any sum in desired interval.

1

We can prove it inductively by constructing the subsequences systematically.Denote the subset summing to $p$ by $S(p)$.

Define $I(k)=\left\{1+\sum_{i=0}^{k-1} (n-i),\sum_{i=0}^{k} (n-i) \right\}$, such that $I(1)=\{1,...,n\}$, $I(2)={n+1,...,2n-1}$, etc.

This is trivially true for $I(1)$. Assume sums to exist for $I(k)$ where $1\leq k. Observe that $S\left( \sum_{i=0}^{k} (n-i) \right)=\{n-k,n-k+1,...,n\}$. We can construct the sums for $I(k+1)$ by noting that if $p\in I(k+1)$, then $S(p)=\{m\}\cup S\left( \sum_{i=0}^{k} (n-i) \right)$, where $m=p-\sum_{i=0}^{k} (n-i). This completes the inductive step and the proof is complete.

1

Here is an alternative approach: consider the case for $n = 5$.

Then $n(n+1)/2 = 5(6)/2 = 15$.

Observe that we can write the numbers $1, \ldots, 15$ as follows:

$1, 2, 3, 4, 5,$

$1+5, 2+5, 3+5, 4+5,$

$1+4+5, 2+4+5, 3+4+5,$

$1+3+4+5, 2+3+4+5,$

$1+2+3+4+5$.

The number of elements summed for entries in the above rows, respectively, are: $1, 2, 3, 4, 5$.

By construction, they are distinct and increasing by one, beginning with $1$ and ending with $15$.

The above can be similarly written out for the general $n$ instead of $15$.