For every positive integer n, determine the total number of sequences of positive integers with the sum n.

Question

I have a problem with this exercise and was unable to find a solution for it. Any help is appreciated.

For a sequence of positive integers, s = ($s_1$,..., $s_k$), we define the length of s to be k and the sum of s to be $\Sigma_{i=1}^n$ $s_i$. For every positive integer n, determine the total number of sequences of positive integers with the sum n.

Answer 1

Suppose the sequence has length $k\leq n$. Then, we need to distribute $n-k$ objects among $k$ boxes (since each box needs at least $1$, so we take out $k$ from $n$). By stars and bars, this can happen in $n-1\choose k-1$ ways. So, the answer is $$\sum\limits_{k=1}^n{n-1\choose k-1}=2^{n-1}$$

Answer 2

Similar to Don Thousand's answer, but skips an intermediate step:

Imagine $n$ stars lined up in a row, so that there are $n-1$ gaps between adjacent stars. In each of the $n-1$ gaps you can choose to insert a bar or not (which gives you $2^{n-1}$ possible configurations). After doing so, the bars partition the $n$ stars into different groups of stars, whose sizes sum to $n$. Each configuration corresponds to a sequence $(s_1, \ldots, s_k)$ of some size $k \ge 1$ that sums to $n$.