Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

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

share|improve this answer
    
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 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 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 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 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 at 13:14

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.