The number 3 can be written as $3$, $2+1$, $1+2$ or $1+1+1$ in four ways. In how many ways can the number $n$ be written?

Question

Attempt Let $x$ be any variable $X+0=n ; X+Y=n ; X+Y+Z=n ; \dots; X+Y+Z+A+\dots=n$ (sum of n-1 terms); $1+1+1+.......+1=n$ (sum of n terms). So total number of ways= $$(n-1) C (1-1)+(n-1) C (2-1)+\dots+(n-1) C (n-1)$$ This equation is correct & gives correct answer if we have a value of $n$ but equation in $n$ needs to be proven equal to $2^{n-1}$. Answer is $$2^{n-1}$$ What can be further done to solve it ?

Answer 1

Write down $n$ marks (e.g. "$x$"). Between any two $x$ you may put a "$+$" or not. Now replace each block of $x$ by their count, and you obtain a valid solution. (E.g., for $n=6$ we start with $xxxxxx$, then obtain prhaops $xx+x+xxx$ and finally $2+1+3$). As there are $n-1$ gaps between two consequtive $x$'s, we have $$2^{n-1}$$ ways to proceed.

Answer 2

Also to close the gap between your answer and the desired form, the combinatorial identity: $$ \sum_{k=0}^n \binom nk = 2^n$$ is fairly well known; the options of choosing any number of objects from a set is clearly counting the powerset of $n$ objects.