How many ways can a natural number n be expressed as a sum of one or more positive integers, taking order into account? Q: The number 4 can be expressed as a sum of one or more positive integers, taking order into account, in 8 ways: 
\begin{array}{l} 4&=1+3&=3+1&=2+2&=1+1+2\\
&=1+2+1&=2+1+1&=1+1+1+1. \end{array}
In general, given $\mathbb n$ $\in$ $\mathbb N$, how many ways can $\mathbf n$ be so expressed?
Query: I managed to solve it via a combinatoric proof, but the solution provided is as such:
\begin{align} &~~Idea: n= x_1 + x_2 +...+x_k, k \in \mathbb N, x_k \gt 0.\\
 &\implies x_1 - 1 + x_2 - 1 +...+ x_k -1 = n - k\\ 
 &\implies x_1* + x_2* + ... + x_k* = n-k \qquad-(*) \end{align}
Since $H^n_r$ = \begin{pmatrix} r+n-1 \\ r \end{pmatrix}, we have $H^k_{n-k}$ = 
\begin{pmatrix} n-k+k-1 \\ n-k \end{pmatrix}
And the answer is as such: $$\sum_{k=1}^n H^k_{n-k} =$$ $$\sum_{k=1}^n \begin{pmatrix} n-1 \\ n-k \end{pmatrix} = 2^{n-1}$$.
I have no idea why $H^n_r$ is applied and also why $$\sum_{k=1}^n H^k_{n-k}$$ is used to derive the desired result $$2^{n-1}$$. Some explanation on this will be deeply appreciated.
 A: One way to see why the answer is $2^{n-1}$ directly is to write $n$ as a sum of $1$s:
$$ n = \underbrace{1 + 1 + 1 + ... + 1}_{n \textrm{ times}}. $$
Of course, this expresses $n$ as a sum of $1$s, but we want all expressions of $n$ as a sum of (ordered) positive numbers.  To do so, for each '$+$' in the expression above, we can choose whether or not to split the sum there to form a new summand.  For example, suppose $n = 8$.  Then we start with
$$ 8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1. $$
Now suppose we choose to split the sum at the 2nd, 3rd and 5th plus signs, highlighted below.
$$ 8 = 1 + 1 \color{red}{+} 1 \color{red}{+} 1 + 1 \color{red}{+} 1 + 1 + 1. $$
We now add up the $1$'s between the chosen plusses to form the summands,
$$ 8 = (1+1) \color{red}{+} 1 \color{red}{+} (1+1) \color{red}{+} (1+1+1) = 2 \color{red}{+} 1 \color{red}{+} 2 \color{red}{+} 3,$$
giving an expression of $8$ as a sum of positive integers.
In general, this clearly bijects to all expressions of $n$ as an ordered sum of positive integers.  Since there are $n-1$ plus signs between the $n$ $1$s, there are $2^{n-1}$ ways of choosing where to split the sum, and hence $2^{n-1}$ possible sums.
A: What you are looking for is compositions of $n$
Take a string of $1's,\;$ e.g.$\;   \large 1{\boxed.} 1\boxed. 1\boxed. 1$
In the $\;(n-1)\;$ boxes, either put a $+\;$ or a comma.
$1,\;\;1+1+1$ e.g. would represent $1+3$
Since you have $2$ choices for each box, # of compositions = $2^{n-1}$
A: Since your title carefully distinguishes between natural numbers (which include $0$) and positive integers (which do not, at least not for the English sense of "positive"), I think a formula should be given that gives the proper value (namely $0$, since at least one summand was required)  for $n=0$, and $2^{n-1}$ does not do that. A correct formula would be $\lfloor2^{n-1}\rfloor$, or you could just give the value as
$$
  \begin{cases}0&\text{if $n=0$,}\\2^{n-1}&\text{if $n>0$.}\end{cases}
$$
The proof can be simply by induction, where we need $n=0$ and $n=1$ as starting cases to capture the exceptional behaviour at $n=0$ (both starting cases are obvious). If we assume for $n>0$ proved that there $2^{n-1}$ compositions of $n$, then from each of them we can get two different compositions of $n+1$: one by increasing the final term by one, and another by adding a new term $1$ and the end. It is clear that the first method, applied to all compositions of $n$ gives all compositions of $n+1$ that do not have $1$ as final term, and the other method gives all compositions of $n+1$ that do have $1$ as final term. Together that gives all compositions of $n+1$, and each of them in just one manner; their number is then $2^{n-1}\times2=2^n$, as was to be proved.
Note that the inductive step cannot be applied to the case $n=0$, as there is no final term to modify there; this explains the exception at the start of the sequence.
