In doing calculations involving computational complexity the following function came up:
$$f(x) = \lim_{N \rightarrow \infty} \frac{\sum_{n=1}^N n^x \log n}{N^{x+1} \log N}$$
for $x \in \mathbb{R}^+$. It appears to be true that
$$f(x) = \frac{1}{x+1}$$
but I am not sure how to prove this. Could anyone suggest an approach?
Answer
$f(x) = \displaystyle \lim_{N\to \infty}\dfrac{1}{N\log N}\left(\displaystyle \sum_{n=1}^N \left(\dfrac{n}{N}\right)^x\log n\right)=\displaystyle \lim_{N\to \infty}\dfrac{1}{N\log N}\left(\displaystyle \sum_{n=1}^N \left(\dfrac{n}{N}\right)^x\log\left(\dfrac{n}{N}\right)+\log N\displaystyle \sum_{n=1}^N\left(\dfrac{n}{N}\right)^x\right)= \displaystyle \lim_{N\to\infty}\dfrac{\displaystyle \int_{0}^1 t^x\log tdt}{\log N}+\displaystyle \int_{0}^1 t^xdt=0+\dfrac{1}{1+x}=\dfrac{1}{1+x}$
No comments:
Post a Comment