Number of ways to write a natural as a sum of naturals Problem:
Let $n$ be a natural number, and $S(n)$ be the number of ways $n$ can be written as a sum of naturals.
For instance, $S(3) = 4$ because $3 = 2+1 = 1+2 = 1+1+1$ and these are four different ways.
Note that we count single-term sums, and different permutations.
Find and prove a simple formula for $S(n)$.
My attempts so far has been to try and do this with induction. By testing the first four cases, I have found that the pattern seems to be that $S(n) = 2^{n-1}$ but I'm unable to prove it.
I am open to other ways of doing this besides induction, of course. It just came to mind because of evaluation on naturals only.
 A: We consider a case where the number $n$ is expressed as a sum of $m$ natural numbers. The number of ways to do so is given by the coefficient of $x^n$ in
$$(x+x^2+x^3+...)^m$$
To illustrate this point, we look at a specific example, with n=4 and m=2. The expression is 
$$(x+x^2+x^3+x^4+...)(x+x^2+x^3+x^4+...)$$
There are $3$ ways to form $x^4$ in the above expression
$$x^{1+3}=x^4$$
$$x^{2+2}=x^4$$
$$x^{3+1}=x^4$$
and you can see that the coefficient of $x^4$ is indeed the number of ways to express $4$ as a sum of $2$ natural numbers.
 Since $1\le m\le n$,
$$S(n)=\sum^{n}_{m=1}[x^n](x+x^2+...)^m=\sum^{n}_{m=1}[x^{n-m}](1-x)^{-m}=\sum^{n}_{m=1}\binom{m+n-m-1}{n-m}=2^{n-1}$$
by the Binomial Theorem
A: What you're looking for is ordered tuples $(a_1,\ldots,a_k)$, $k=1,\ldots,n$ with $a_i>0$ such that $\displaystyle\sum_{i=1}^k a_i=n$. Now, an ordered tuple $(a_1,\ldots,a_k)$ with $a_i>0$ such that the sum is $=n$ is just a set of $k$ boxes with at least one ball inside, i.e. $n-k$ balls in $k$ boxes. This is known to equal $$\binom{n-k+k-1}{k-1}=\binom{n-1}{k-1}$$ so summing throughout gives $$\sum_{k=1}^n \binom{n-1}{k-1}$$
which is...?
