Доказать количество слагаемых (комбинаторика)

[fifa11]

Дано, что ${1}\leqslant {k} <n$. Докажите, что между всеми $2^{n-1}$ числа $n$ комбинациями число $k$ встречается как слагаемое всего $(n-k+3)2^{n-k-2}$ раз.
Пример: если $n=4, k=2$, тогда $2$ встречается один раз в комбинациях $2+1+1, 1+2+1, 1+1+2$, и два раза в комбинации $2+2$, всего $5$ раз.

[chessar]

Рассмотрим композиции числа $n-k$. Их количество равно $2^{n-k-1}$. Если теперь для каждой такой композиции $n-k=a_1+a_2+\cdots+a_m$ мы будем добавлять в каждую из позиций число $k$ (перед 1-ым слагаемым, между каждыми двумя слагаемыми и после последнего слагаемого), то получим все нужные нам композиции числа $n$, в которых встречается число $k$:

\begin{gather*} n=k+a_1+a_2+\cdots+a_m,\\ n=a_1+k+a_2+\cdots+a_m,\\ \cdots\\ n=a_1+a_2+\cdots+k+a_m,\\ n=a_1+a_2+\cdots+a_m+k\\ \end{gather*}
(и так для каждой композиции длин $m=1,2,\ldots,n-k$).

Для фиксированного $m$ количество композиций числа $n-k$ длины $m$ есть $C_{n-k-1}^{m-1}$, соответственно количество композиций длины $m+1$ числа $n$, в которые входит $k$ есть $(m+1)C_{n-k-1}^{m-1}$. И значит, искомое число композиций числа $n$, в которые входит $k$ есть сумма:
\begin{multline*} \sum_{m=1}^{n-k}(m+1)C_{n-k-1}^{m-1}=\\=\frac{1}{2}\left(\sum_{m=1}^{n-k}(m+1)C_{n-k-1}^{m-1}+\sum_{m=1}^{n-k}(n-k-m+2)C_{n-k-1}^{m-1}\right)=\\=\frac{n-k+3}{2}\cdot 2^{n-k-1}=(n-k+3)2^{n-k-2}. \end{multline*}

[fifa11]

Спасибо огромноеее