finite sum of powers

Question

Can you find what $\sum_{i=1}^{n}\left(n/i\right)^{i}$ is equal to? By simulation, I know that a loose upper bound is $2^n$. I am happy with a proof of such upper bound if an exact expression is not available.

Answer 1

Basically we are considering the sum $$ S(n)=\sum_{i=1}^n y(i) $$ where $$ y=\left(\frac{n}{x}\right)^x\quad,\quad x>0 $$ Of course $y$ depends on $n$ but to make the next part 'cleaner' I choose not to specify that in the name of the function. The derivative of $y$ can be found by applying $\ln$ (the natural logarithm) on both sides then use implicit differentiation and solve for $y'$ to get $$ y'=(\ln(n)-\ln(x)-1)\cdot y $$ since $y$ is always non-zero no matter what $x$ is this derivative can only be zero if $\ln(n)-\ln(x)-1$ is zero leading to that $$ x_{max}=\frac{n}{\text{e}} $$ The corresponding maximal value for $y$ may be calculated by plugging $x$ into the formula for $y$ and reduce the expression to get $$ y_{max}=\text{e}^{n/\text{e}}=q^n $$ where $q:=\text{e}^{1/\text{e}}\approx 1.444667861$ has been defined. With this we may find a very rough upper bound for the sum which is $$ S(n)=\sum_{i=1}^n y(i)\leq n\cdot y_{max}=n\cdot q^n $$ A little further analysis shows that for $n\geq 5$ we have $n\cdot q^n<2^n$ which proves that your upper bound holds for $n\geq 5$. It is easy to check that it holds for $n=1,2,3,4$.

My upper bound $n\cdot q^n$ is actually better for $n\geq 5$ and much better for large values of $n$. Nevertheless I suspect it can be improved considerably since for large $n$'s the sum $S(n)$ will have a value relatively close to the value of the definite integral $$ I(n)=\int_0^n y\ dx $$ and I suspect that $\frac{S(n)}{I(n)}$ tends to $1$ for $n$ going to infinity. But $y$ is to the best of my knowledge a very hard function to integrate. Just google $\int x^x\ dx$ to see how hard that one is and then expect $y=\frac{n^x}{x^x}$ to be at least as hard.

Answer 2

This is not a proof of anything but just the result of a very empirical approach based on numerical simulation.

What I did is to compute the value of $$S(n)=\sum_{i=1}^{n}\left(\frac{n}{i}\right)^{i}$$ for values of $n$ which are multiples of $100$ (from $100$ to $1000$). Plotting $\log[S(n)]$ versus $n$ effectively reveals a very linear trend.

While I was working, appeared the very interesting answer from String (to whom all the merit must be given) ; this gave me the idea of using a slightly more complex model than a pure geometric one.

So, I performed a linear regression $$\log[S(n)]=0.414161+0.367878 n+0.50082 \log (n)$$ which gives an excellent fit. Looking carefully at the numbers, it seems that $$2 \sqrt n e^{\frac {n}{e}}$$ is a quite close upper bound.

Added later

Reworking the numbers obtained from the empirical curve fit, a much better upper bound has been found. It write $$S(n)=\sum_{i=1}^{n}\left(\frac{n}{i}\right)^{i} \lt \sqrt n e^{\frac{n}{e}+\frac{1}{2}}$$