Sum decompositions
Task number: 4399
Answer
There are \(2^{n-1}\) decompositions of \(n\).Solution
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.
