## Sum decompositions

Count how many decompositions of $$n$$ exist into an ordered sum of positive integers. For example, for $$n=3$$ these are $$1+1+1$$, $$1+2$$, $$2+1$$ and $$3$$.
There are $$2^{n-1}$$ decompositions of $$n$$.
Let $$R_n$$ denote the number of decompositions of the number $$n$$. We manually calculate $$R_0$$=1 (empty decomposition), $$R_1=1$$, $$R_2=2$$, $$R_3=4$$. This suggests that $$R_n=2^{n-1}$$ could hold for $$n>0$$. This is easy to prove by induction: when the decomposition starts with the number $$k$$, the remaining terms form the decomposition of the number $$n-k$$. So $$R_n=\sum\limits_{k=1}^n R_{n-k}$$, so by induction hypothesis $$R_n =R_0 + \sum\limits_{k=1}^{n-1} R_{n-k} = 1 + \sum\limits_{k=1}^{n-1} R_{k} = 1 + \sum\limits_{k=1}^{n-1} 2^{k-1} =1+\sum\limits_{k=0}^{n-2} 2^k = 2^{n-1}$$.
Alternatively we can solve the problem by combinatorial reasoning. Each decomposition can be obtained from $$1+1+1+\ldots+1$$ by joining some adjacent ones into groups. The breakdown into groups is clearly determined by which ones are at the end of the group. It may or may not end with the first $$n-1$$ ones; always ends with the last one. Hence there are $$2^{n-1}$$ options to terminate groups.