Given $n \geq 1$, show that it can be written as a summation from $\mathbb{N}$ in ordered way in $2^{n-1}$ ways. I'm trying to give both inductive proof and combinatorial.
For inductive:
$P_1$: This is the base case when $ n = 1$ the ways are: $|\{\{1\}\}| = 1 = 2 ^ {1-1}$
Let's assume $P_n$ holds, that $n$ can be represented in $2^{n-1}$ ways.
$P_n \implies P_{n+1}$
Now I am stuck. I know that we can add 1 to all the summations that we have for $n$ to obtain $n+1$ but I know there may be also other ways and I don't know how to count for the fact that the choices are ordered.
Can someone give me a hint or help me out, thanks.
Imagine $n$ dots in a line, and let $G$ be the set of the $n-1$ interior gaps between consecutive dots. For any subset $S$ of $G$, there is a canonical ordered partition for which each part counts the consecutive dots between elements of $S$ (like "stars and bars"). It's easy to see this is a bijection between the partitions and subsets of $G$. How many subsets $S$ of $G$ are there altogether?
For an inductive argument, given a partition $P$ of $n-1$ (for example $6=4+2$), generate two partitions of $n$ as follows (1) add 1 to the last part of $P$ (e.g. $7=4+3$) and (2) insert a "$+1$" at the end of $P$ (e.g. $7=4+2+1$). The first type are the partitions of $n$ that don't end with a $1$ and the second type are the ones that do end with a $1$. So there are twice as many partitions of $n$ as of $n-1$.