How many instances of number $k$ in sums that add up to number $n$? Task in Combinatorics course:

$1 \leq k < n$. Prove that the number $k$ can be found $(n-k+3)2^{n-k-2}$ times in sums that add up to $n$.

Example: $n=4, k=2$.
$1+1+2$
$1+2+1$
$2+1+1$
$2+2$
These are the sums that add up to $4$ and the number $2$ can be found $5$ times.
Thus far, I have tried making sense of that formula. $n-k$ is the number or countables left if we have one $k$. $2^{n-1}$ is how many sums that add up to $n$ there are in total so in the second half of the formula it could be $2^{n-1}2^{k-1}$ that would add up to $2^{n-k-2}$. But none of that comes together. Why would there be a $+3$ in the first half.
 A: A composition which sums to $n$ corresponds to the placement of either a comma or an addition sign in each of the $n - 1$ spaces between successive ones in a row of $n$ ones.
$$1 \square 1 \square 1 \square \cdots \square 1 \square 1 \square 1$$
Since there are $2$ ways to fill each of the $n - 1$ spaces, there are $2^{n - 1}$ compositions of the number $n$.
We are told that one of the summands is $k$.  That means there is a block of $k$ consecutive ones.  Such a block must begin in one of the first $n - k + 1$ positions.  Of these, two are at the ends of the row and $n - k - 1$ include neither end of the row.  We will consider cases, depending on the position of the block.
If the first summand is $k$, there is a block of exactly $k$ ones at the start of the row.  That block must be immediately followed by an addition sign.  That leaves $n - k$ ones and $n - k - 1$ spaces where either a comma or an addition sign can be placed.  Hence, there are $2^{n - k - 1}$ such compositions.
If the last summand is $k$, there is a block of exactly $k$ ones is at the end of the row.  That block must be immediately preceded by an addition sign.  That leaves $n - k$ ones and $n - k - 1$ spaces where either a comma or an addition sign can be placed.  Hence, there are $2^{n - k - 1}$ such compositions.
If the summand $k$ does not appear in the first or last position of the composition, there are $n - k - 1$ places where the block of exactly $k$ consecutive ones could begin.  The block must be immediately preceded and immediately followed by addition signs.  That leaves $n - k$ ones and $n - k - 2$ spaces where either a comma or an addition sign can be placed.  Hence, there are $(n - k - 1)2^{n - k - 2}$ such compositions.
Since these cases are mutually exclusive and exhaustive, the number of times the summand $k$ appears in compositions of $n$ is
\begin{align*}
2 \cdot 2^{n - k - 1} + (n - k - 1)2^{n - k - 2} & = 4 \cdot 2^{n - k - 2} + (n - k - 1)2^{n - k - 2}\\
& = (n - k + 3)2^{n - k - 2}
\end{align*}
Note that we have implicitly used the hypothesis that $k < n$ in order to separate the cases where $k$ is the first summand, $k$ is the last summand, and $k$ is neither the first nor last summand.
A: We have the marked generating function
$$Q(z,u) = \sum_{q=1}^n
\left(z+\cdots+z^{k-1} + u z^k + z^{k+1} + \cdots\right)^q.$$
The term $u^p z^m$ represents a composition that sums to $m$ and
contains $p$ instances of the number $k.$ Hence we differentiate with
respect to $u$ and set $u=1$ to get the count. Differentiation yields
$$\sum_{q=1}^n
q \left(z+\cdots+z^{k-1} + u z^k + z^{k+1} + \cdots\right)^{q-1}
z^k.$$
Set $u=1$ to get
$$[z^n] z^k \sum_{q=1}^n q \frac{z^{q-1}}{(1-z)^{q-1}}.$$
Note that with $k\ge 1$ we may extend $q$ beyond $n$ without getting  any
additional contributions to the coefficient extractor. This yields
$$[z^n] z^k \sum_{q\ge 1} q \frac{z^{q-1}}{(1-z)^{q-1}}
= [z^{n-k}] \frac{1}{(1-z/(1-z))^2}
\\ = [z^{n-k}] (1-z)^2 \frac{1}{(1-2z)^2}
\\ = [z^{n-k}] \frac{1}{(1-2z)^2}
- 2 [z^{n-k-1}] \frac{1}{(1-2z)^2}
+ [z^{n-k-2}] \frac{1}{(1-2z)^2}
\\ = (n-k+1) 2^{n-k} - 2(n-k) 2^{n-k-1} + (n-k-1) 2^{n-k-2}
\\ = (4n-4k+4-4n+4k+n-k-1) 2^{n-k-2}
= (n - k + 3) 2^{n-k-2}.$$
This is with $n-k\ge 2.$ We get for $k=n-1$
$$(n-k+1) 2^{n-k} - 2(n-k) 2^{n-k-1}
= 2\times 2 - 2 = 2$$
which is true because the compositions are $(1,n-1)$ and $(n-1,1).$ We
get for $k=n$
$$(n-k+1) 2^{n-k} = 1$$
which is also true because there is just one composition $(n).$
A: Fix $k$ and let $a_n$ be the number of $k$s that appear among all ($2^{n-1}$) ordered partitions of $n$.  Then $a_n=0$ for $n<k$, $a_k=1$, and conditioning on the first part $i$ yields recurrence relation
$$a_n = \sum_{i=1}^n ([i=k]2^{n-i-1} + a_{n-i}) = 2^{n-k-1} + \sum_{i=1}^{n-k} a_{n-i} \quad \text{for $n > k$}.$$
Let $A(z) = \sum_{n=0}^\infty a_n z^n$ be the ordinary generating function.  Then
\begin{align}
A(z) 
&= \sum_{n=0}^{k-1} 0 z^n + 1z^k + \sum_{n=k+1}^\infty \left(2^{n-k-1} + \sum_{i=1}^{n-k} a_{n-i}\right) z^n \\
&= z^k + \sum_{n=k+1}^\infty 2^{n-k-1} z^n + \sum_{i=1}^\infty z^i \sum_{n=i+k}^\infty a_{n-i} z^{n-i} \\
&= z^k + \frac{z^{k+1}}{1-2z} + \sum_{i=1}^\infty z^i A(z) \\
&= z^k + \frac{z^{k+1}}{1-2z} + \frac{zA(z)}{1-z}.
\end{align}
So
\begin{align}
A(z) 
&= \frac{z^k(1-z)^2}{(1-2z)^2} \\
&= z^k \left(\frac{1}{4}+\frac{1/2}{1-2z}+\frac{1/4}{(1-2z)^2}\right) \\
&= z^k \left(\frac{1}{4}+\frac{1}{2}\sum_{n=0}^\infty(2z)^n+\frac{1}{4}\sum_{n=0}^\infty\binom{n+1}{1}(2z)^n\right) \\
&= z^k \left(1+\frac{1}{2}\sum_{n=1}^\infty(2z)^n+\frac{1}{4}\sum_{n=1}^\infty(n+1)(2z)^n\right) \\
&= z^k +\sum_{n=k+1}^\infty \left(2^{n-k-1}+(n-k+1)2^{n-k-2}\right)z^n \\
&= z^k +\sum_{n=k+1}^\infty (n-k+3)2^{n-k-2}z^n,
\end{align}
which immediately implies that
$a_n = (n-k+3)2^{n-k-2}$ for $n>k$.
