Let An be the total number parts that are equal to $~1~$ in all compositions of $~n~$. So $~A_1 = 1,~ A_2 = 2, ~A_3 = 5~,$ and $~A_4 = 12~$.
Prove that for all $~n ≥ 2~$, the recurrence relation $$A_{n+1} = 2A_n + {2^n}^{-2} $$ holds.
My work: I tried the following: take one composition of $n$ and fix one term, say $a_i$ . If $a_i$ = 1, subtract it. Then the number of $1$'s in composition of $n$ is $A_n$. I'm not sure where $2A_n$ is coming from. Also, we have many choices to pick $i$-th term.
For the term $2^{n-2}$, I was thinking that we can add $1$ anywhere to the the composition of $n$. But that is the furthest I got. Any explanation would be greatly appreciated.
Compositions of $n+1$ fall into two classes:
Compositions beginning with a $1$. There are $2^{n-1}$ such compositions, each beginning with a $1$, so we start with $2^{n-1}$ ones. The number of ones in the remaining parts is $A_n$, so the contribution from this case is $2^{n-1}+A_n$.
Compositions beginning with some number $k>1$. There are again $2^{n-1}$ such compositions (why?). Imagine taking the set of all such compositions and replacing each initial $k$ with $k-1$. The resulting set is the set of all compositions of $n$, so it seems like there should still be $A_n$ ones among these compositions. However, if $k=2$, then the transformation $k\to (k-1)$ created an extra one. The number of extra ones created is the number of compositions of $n+1$ starting with $2$, which is $2^{n-2}$. We must subtract these out, so the contribution from this case is $A_n-2^{n-2}$.
Adding these two contributions together, we get $A_{n+1}=2A_n+2^{n-2}$.
Perhaps a more direct method; by considering all possibilities for the first part of the composition of $n+1$, we get the recurrence $$ A_{n+1}=(2^{n-1}+A_n)+A_{n-1}+A_{n-2}+\dots+A_1 $$ Similarly, $$ A_n=(2^{n-2}+A_{n-1})+A_{n-2}+\dots+A_1 $$ Subtracting the two equations, you get $$ A_{n+1}-A_n=(2^{n-1}-2^{n-2})+A_n $$ which rearranges to what you want.