What are the techniques to evaluate the following sum
Sk(n):=∑k≤a1+a2+…+ak<n(a1+12a2+13a3+…+1kak)?
with positive integer constraints on ai, i.e. ai∈N+.
In the end I'm interested only in the leading coefficient (of polynomial in n), therefore I've tried to write
Sk(n)=∑k≤a1+a2+…+ak<n(11a1+12a2+13a3+…+1kak)
Sk(n)=∑k≤a1+a2+…+ak<n(12a1+13a2+14a3+…+11ak)
+⋮
Sk(n)=∑k≤a1+a2+…+ak<n(1ka1+11a2+12a3+…+1k−1ak)
−−−−−−−−−−−−−−−−−−−−−−−−−−
kSk(n)≤(1+logk)∑k≤a1+a2+…+ak<n(a1+a2+a3+…+ak)
Where ≤ comes from logarithm and from double-counting. Then, basically, I need to count all the ways to assemble an integer t∈[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 ks 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
No comments:
Post a Comment