# Number of ways to write a natural as a sum of naturals [duplicate]

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.

## marked as duplicate by Ross Millikan, hardmath, Tunk-Fey, user147263, CookieJul 18 '14 at 15:05

• – JimmyK4542 Jul 18 '14 at 14:27
• Thanks. It didn't show up in my searches because of wording, but I can see why you would be able to find it :) – Alec Jul 18 '14 at 14:30
• Although it is technically the same question as the one I linked to, this version is written much better. – JimmyK4542 Jul 18 '14 at 14:34
• Many Questions are about this, for example here. Of course it helps to know the technical term for such sums is compositions. – hardmath Jul 18 '14 at 14:40
• @JimmyK4542 - Hehe, thanks. Your answer also provided a method for solution with which I'm already familiar, so it immediately simplified the problem for me. Not to detract from the help of other answerers in this question, of course. – Alec Jul 18 '14 at 14:41

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