Example 2: Let $1 \leqslant k<n$, consider all positive integer sequences of length $n$, and find the total number of terms $T(n, k)$ in these sequences that are equal to $k$. (29th IMO Shortlist)
The sequence has at least two terms, namely $n-k$ and $k$; at most $n-k+1$ terms, which include $k$ and $n-k$ ones. Let $T(p, n, k)$ denote the total number of terms equal to $k$ in all sequences of $p+1$ terms whose sum is $n$.
When $p=1$, there are only two sequences $\{n-k, k\}$, $\{k, n-k\}$, so $T(1, n, k)=2$. We now prove:
$$
T(p, n, k)=(p+1) C_{n-k-1}^{p-1} \cdot(p>1) .
$$

Assume the sequence consists of elements $x_{0}=k, x_{1}, x_{2}, \cdots, x_{p}$, where $x_{1}+x_{2}+\cdots+x_{p}=n-k$. The number of solutions to this equation is the number of combinations with repetition, which is $C_{n-k-1}^{p-1}$. Each solution can be seen as a $p$-term sequence, and then inserting $x_{0}$ into this sequence meets the requirement. There are $p+1$ different positions for $x_{0}$ to choose from, so there are $(p+1) C_{n-1}^{p-1}$ sequences. However, some of these sequences are identical. If the sequence has $q$ terms equal to $k$ besides $x_{0}$, swapping $x_{0}$ with any of these $k$ terms results in the same sequence, thus there are $q+1$ identical sequences, each containing $q+1$ $k$s. Therefore, when calculating the total number of terms equal to $k$, the final result remains unchanged, so $T(p, n, k)$
$$
\begin{array}{l}
=(p+1) C_{n-1}^{p-1} \text {. Thus } \\
T(n, k)=\sum_{j=1}^{n-k} T(p, n, k) \\
=2+\sum_{p=2}^{n-k}(p+1) C_{n-k-1}^{p-1} \\
=2+\sum_{p=2}^{n-1}\left(2 C_{n-k-1}^{p-1}-1\right. \\
\left.+(n-k-1) C_{n-k-2}^{p-2}\right) \\
=2 \cdot \sum_{p=0}^{n-k-1} C_{n-k-1}^{p} \\
+\left(n-k-1 \sum_{p=0}^{n-k-2} C_{n-k-2}^{p}\right. \\
=2 \cdot 2^{n-k-1}+(n-k-1) \cdot 2^{n-k-2} \\
=(n-k+3) \cdot 2^{n-k-2} . \\
\end{array}
$$