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?

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}.$$
