# 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.

• So $S_k$ is a function from $\mathbb{Z^+}$ to $\mathbb{Q}$, correct? In the first formula, you might have written $S_k(n)$ instead of $S_k?$ Jul 8, 2019 at 12:55

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