Let $s_n$ be the sum of the first part of all compositions of n. So $s_1$ = 1, $s_2$ = 3, and $s_3$ = 7. Find an explicit formula for $s_n$.
I came up with the following solution and was wondering whether it is correct:
Let i be the first part of a composition. Let $ 1 \leq i \leq n-1 $. Number of times i appears as a first part of the other compositions is the number of compositions of $(n-i) = 2^{n-i-1}$. Then sum of all first terms is a sum over all $i$ multiplied by the $i$ value and value of n itself (not included in the sum): $$s_n = n+ \sum_{i=0}^{n-1} i \ 2^{n-i-1} $$
Is my solution correct or am I missing something? Any help is greatly appreciated.
Yes, this argument is correct, and this sum simplifies to $2^n-1$. It might be cleaner to start the sum at $i=1$ instead of $i=0$.