<s>[INST] Proving an equality involving compositions of an integer Let's consider various representations of a natural number $n \geq 4$ as a sum of positive integers, in which the order of summands is important (i.e. compositions).  The task is to prove the number $3$ appears altogether $n2^{n-5}$ times in all of them.
I know there're $2^{n-1}$ compositions of $n$. However, I have no clue as to how to count only those involving the number(s) $3$. I can't think of any sensible generating function for this. Maybe there's a nice combinatorial interpretation of the given formula, which I can't figure out? Could anyone lend me a hand with handling this problem?
 [/INST] It appears that the generating function approach is quite simple here. We have by inspection that the bivariate generating function of compositions with the number three marked is
$$M(z, u) = \sum_{q\ge 1}\left(\frac{z}{1-z} - z^3 + uz^3\right)^q.$$
Therefore the generating function of the total number of ocurrences is
$$\left.\frac{d}{du} M(z, u)\right|_{u=1}
= \left. \sum_{q\ge 1} q \left(\frac{z}{1-z} - z^3 + uz^3\right)^{q-1} \times z^3
\right|_{u=1}
\\= z^3 \sum_{q\ge 1} q \left(\frac{z}{1-z}\right)^{q-1}
= z^3 \frac{1}{(1-z/(1-z))^2}
= z^3 \frac{(1-z)^2}{(1-2z)^2}
\\ = z^3 \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right).$$
To conclude extract coefficients, getting
$$[z^{n-3}] \left(\frac{1}{1-2z} + \frac{z^2}{(1-2z)^2}\right)
= 2^{n-3} + [z^{n-5}] \frac{1}{(1-2z)^2}
\\ = 2^{n-3} + (n-4) 2^{n-5} = 4 \times 2^{n-5} + (n-4) 2^{n-5} = n 2^{n-5}.$$
</s>