Q:

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

