Friday, 4 November 2016

calculus - Evaluating weighted sum




What are the techniques to evaluate the following sum
Sk(n):=ka1+a2++ak<n(a1+12a2+13a3++1kak)?
with positive integer constraints on ai, i.e. aiN+.




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




Sk(n)=ka1+a2++ak<n(11a1+12a2+13a3++1kak)
Sk(n)=ka1+a2++ak<n(12a1+13a2+14a3++11ak)
+
Sk(n)=ka1+a2++ak<n(1ka1+11a2+12a3++1k1ak)



kSk(n)(1+logk)ka1+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,n1] 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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...