calculus - Evaluating weighted sum

What are the techniques to evaluate the following sum
$$S_k(n) := \sum\limits_{k \leq a_1 + a_2 + \ldots + a_k < n} \left(a_1 + \frac{1}{2}a_2 + \frac{1}{3}a_3 + \ldots + \frac{1}{k} a_k \right) \quad?$$
with positive integer constraints on $a_i$, i.e. $a_i \in \mathbb{N}_+$.

In the end I'm interested only in the leading coefficient (of polynomial in $n$), therefore I've tried to write

$$S_k(n) = \sum\limits_{k \leq a_1 + a_2 + \ldots + a_k < n} \left(\frac{1}{1}a_1 + \frac{1}{2}a_2 + \frac{1}{3}a_3 + \ldots + \frac{1}{k} a_k \right)$$
$$S_k(n) = \sum\limits_{k \leq a_1 + a_2 + \ldots + a_k < n} \left(\frac{1}{2}a_1 + \frac{1}{3}a_2 + \frac{1}{4}a_3 + \ldots + \frac{1}{1} a_k \right)$$
$$ + \qquad\qquad\qquad\qquad\qquad\qquad\qquad\vdots $$
$$S_k(n) = \sum\limits_{k \leq a_1 + a_2 + \ldots + a_k < n} \left(\frac{1}{k}a_1 + \frac{1}{1}a_2 + \frac{1}{2}a_3 + \ldots + \frac{1}{k-1} a_k \right)$$
$$--------------------------$$

$$k S_k(n) \leq (1 + \log k) \sum\limits_{k \leq a_1 + a_2 + \ldots + a_k < n} \left(a_1 + a_2 + a_3 + \ldots + a_k \right)$$

Where $\leq$ comes from logarithm and from double-counting. Then, basically, I need to count all the ways to assemble an integer $t \in [k, n -1]$ multiplied by $t$. Which is
$$ \sum \limits_{i=0}^{n-k-1} (i+k) \cdot {{i+k-1}\choose{k-1}}$$

For the big-O notation I only care for $$\sum\limits_{i=0}^{n-k-1} (i+k) \cdot \frac{1}{(k-1)!} n^k \approx\frac{1}{2\, (k-1)!}n^{k+2},$$
which in turn gives
$$S_k(n) \leq \frac{1+\log k}{2k!}n^{k+2}$$

I've run the MATLAB [for different $k$s and random sampling] to see if this is indeed an upper bound [for coefficient], and even $\frac{1+\log k}{k\cdot k!}$ seems to be.

Answer

Turned out we can produce a very neat expression after all.

I'll continue from evaluating the sum

$$\sum \limits_{i=0}^{n-k-1} (i+k) \cdot {{i+k-1}\choose{k-1}}$$

rewrite $$(i+k){{i+k-1}\choose{k-1}} = (i+k)\frac{(i+k-1)!}{i!(k-1)!} = k\frac{(i+k)!}{i!k!} = k{{i+k}\choose{i}}$$
therefore
$$\sum \limits_{i=0}^{n-k-1} (i+k) \cdot {{i+k-1}\choose{k-1}} = k \sum \limits_{i=0}^{n-k-1}{{i+k}\choose{i}}$$

[browsing Wikipedia a bit reveals the following identity]

$$\sum\limits_{r=0}^m {{n+r}\choose{r}} = {{n+m+1}\choose{m}}$$

Plugging $m = n-k-1, n = k$

$$\sum \limits_{i=0}^{n-k-1} (i+k) \cdot {{i+k-1}\choose{k-1}} = k{{n}\choose{n-k-1}} = k{{n}\choose{k+1}}$$

I take a step back, and re-introduce a Harmonic number $H_k$ instead of $1+\log k$.
$$kS_k(n) = H_k\cdot k \cdot {{n}\choose{k+1}}$$

and finally

$$S_k(n) = {{n}\choose{k+1}}H_k$$