1

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.

Student
  • 41

2 Answers2

1

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

Claude Leibovici
  • 260,315
  • The simplicity of the expression $2\sqrt n\text{e}^{\frac{n}{e}}$ is very appealing. I see how you raised the value of $\text{e}^{0.414161}\approx 1.51$ to $2$ and how $\text{e}^{0.367878}\approx 1.4446658$ resembles the value of my constant $q$, but why do you suspect that $0.50082$ can be lowered to $0.5$ in order to give us the square root? – String Apr 24 '14 at 12:53
  • @String. Your answer was very inspring. What I did was very empirical based on a multilinear regression. After doing it, I tried, thanks to your points, to find "good" numbers. If we were speaking about estimation, factor $1.5$ is very good. Thanks for your ideas. Cheers. – Claude Leibovici Apr 24 '14 at 12:59
  • Thank you, I enjoyed your answer too and upvoted it right away! I reproduced the numerical fitting to the model $a\cdot\log(n)+b\cdot n+c$ and found the same constants as you did. But the differences between $2\sqrt{n}\text{e}^{\frac{n}{\text{e}}}$ and $S(n)$ seem to decrease slightly so I was just wondering whether the bound had been overtightened thus failing for larger values of $n$ ... – String Apr 24 '14 at 13:08
  • I am fully aware that your suggested bound needs to be proven (or disproven) as it is empirically based. I proved my bound, but I am positive that a much better bound exists! – String Apr 24 '14 at 13:12
  • @String. You are certainly right concerning the existence of a better bound. Your proof is excellent. I tried several CAS with no success at all. Cheers. – Claude Leibovici Apr 24 '14 at 13:14
  • @String. I found something still better $$S(n)=\sum_{i=1}^{n}\left(n/i\right)^{i} \lt \sqrt{n} e^{\frac{n}{e}+\frac{1}{2}}$$ – Claude Leibovici Apr 25 '14 at 03:41
0

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.

String
  • 18,395