1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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?$ $\endgroup$
    – saulspatz
    Jul 8, 2019 at 12:55

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .