Number of ways to write a natural as a sum of naturals

Question

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.

Answer 1

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

Answer 2

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