8
$\begingroup$

Is it possible to get a closed form expression, or an upper bound, for the following function $f$ which is given by an infinite summation:

$$ f(n) = \sum_{m=1}^\infty \bigg(\frac{m+n}{3}\bigg)^{m+n} \bigg(\frac{1}{m}\bigg)^m, $$ for $n > 0$? Also, $n$ can be assumed to be large if this is any help.

Note when $n=0$, it is simply $$ f(0) = \frac{1}{2}. $$

$\endgroup$
  • 1
    $\begingroup$ It looks like a some sort of factorial when graphed and the sum looks similar to a binomial series. $\endgroup$ – Jam Oct 29 '19 at 11:59
  • 1
    $\begingroup$ Is there anything that suggests the function has a closed form? $\endgroup$ – Jam Oct 29 '19 at 12:06
  • 2
    $\begingroup$ I see. Personally I don't actually think it's that simple and there are simpler series (e.g. $\sum_{i=1}^{\infty}\frac{x^{x}}{i^{i}}$) that don't have closed forms. You can possibly get a nice asymptotic for your series though. $\endgroup$ – Jam Oct 29 '19 at 12:15
  • 2
    $\begingroup$ The function growth is at least exponential. $$f(n) \geq \sum_{m=1}^{\infty} \left(\frac{m}{3}\right)^{m+n}\left(\frac{1}{m}\right)^m = \sum_{m=1}^{\infty} \frac{1}{3^m}\left(\frac{m}{3}\right)^n > \frac{1}{3^4}\left(\frac{4}{3}\right)^n.$$ $\endgroup$ – JoshuaZ Oct 29 '19 at 13:13
  • 2
    $\begingroup$ Using Stirling formula we have a problem with small values of $m$ . But how is the approximation $~\displaystyle f(n)\approx n!\left(\frac{3}{2}\left(\frac{e}{2}\right)^n - \left(\frac{e}{3}\right)^n\right)~$ for you ? Especially for small or large $n$ ? $\endgroup$ – user90369 Oct 30 '19 at 15:06
5
$\begingroup$

We can derive bounds and approximations for $f(n)$ that suggest properties that such a closed form must have.

$$f(n)=\sum_{i=1}^\infty\frac{\left(\frac{n+i}{3}\right)^{n+i}}{i^i} $$

When $n$ is fixed, the summands, $a_i$, are increasing over $(0,\frac{n}{2})$ but decreasing over $(\frac{n}{2},\infty)$. This can be shown by considering their derivatives. By bounding the summand with continuous curves and accounting for the peak at $n/2$, we can deduce that

$$f(n)\leq\int_{1/2}^{n/2-1/2}a_{i+1/2}\,\mathrm{d}i+ a_{n/2}+\int_{n/2+1/2}^{\infty}a_{i-1/2}\,\mathrm{d}i$$

Then, by substitution with $i\mapsto i\pm1/2$, $$f(n)\leq\int_{1}^{\infty}a_{i}\,\mathrm{d}i+ a_{n/2}$$

Rearranging $a_i$ to $\left(\frac{n+i}{3}\right)^{n}\cdot e^{-i\ln\left(\frac{3}{\frac{n}{i}+1}\right)}$ allows us to bound it by incorporating the inequality $1-\frac1x\leq \ln x \leq x-1$. Hence,

$$\left(\frac{n+i}{3}\right)^{n}\cdot e^{\frac{i\left(n-2i\right)}{n+i}}\leq a_i\leq \left(\frac{n+i}{3}\right)^{n}\cdot e^{\frac{n}{3}-\frac{2}{3}i}$$

Combining this upper bound with the previous integral inequality,

$$\begin{aligned}f(n)&\leq\frac{e^{\frac{n}{3}}}{3^{n}}\int_{1 }^{\infty }\frac{\left(n+i\right)^{n}}{e^{\frac{2}{3}i}}\,\mathrm{d}i+ \left(\frac{n}2\right)^{n} \\ &\leq \frac{3e^{n}}{2^{n+1}}\Gamma\left(n+1,\frac{2\left(n+1\right)}{3}\right)+ \left(\frac{n}2\right)^{n}\end{aligned}$$

where $\Gamma(s,x)=\int_1^\infty t^{s-1}e^{-t}\,\mathrm{d}t$ is the incomplete gamma function. When $x\gg 0$, we have $\Gamma(s,x)\approx x^{s-1}e^{-x}$. Hence, for large $n$, $$f(n)\approx \frac{3}{2e^{\frac{2}{3}}}\left(\frac{e^{\frac{1}{3}}}{3}\left(n+1\right)\right)^{n}+\left(\frac{n}{2}\right)^{n}$$


Update 2019-11-05. Improved bounds.

Expanding on @user90369's ingenious use of Stirling's approximation to bound $n^n$, we can use the existing upper and lower bounds for $n!$ to sandwich $n^n$. We can then choose the relevant bounds for the numerator and denominator of the summands of $f(n)$ to find the improved bounds

$$\frac{\sqrt{2\pi}e^{n}}{3^{n}e}\leq \frac{f(n)}{\sum_{i=1}^{\infty}\frac{\left(n+i\right)!\sqrt{\frac{i}{n+i}}}{3^{n}\cdot i!}} \leq \frac{e^{n+1}}{\sqrt{2\pi}3^{n}} \\ \\ \frac{\sqrt{2\pi}}{e\sqrt{n+1}} \leq \frac{f(n)}{\frac{e^{n}}{3^{n}}\sum_{i=1}^{\infty}\frac{\left(n+i\right)!}{3^{i}\cdot i!}} \leq \frac{e}{\sqrt{2\pi}} \\ \frac{\sqrt{2\pi}}{e\sqrt{n+1}} \leq \frac{f(n)}{e^{n}n!\left(\frac{3}{2}\cdot2^{-n}-3^{-n}\right)} \leq \frac{e}{\sqrt{2\pi}}$$

So - unless I'm mistaken, since I'm not great with asymptotic analysis - this means that $f(n)\in\mathcal{O}\left(\sqrt{n}\left(\frac{n}2\right)^n\right)$ and $f(n)\in\mathcal{\Omega}\left(\left(\frac{n}2\right)^n\right)$. This lends itself to the natural approximation $f(n)\approx k\sqrt{n}\left(\frac{n}{2}\right)^n$ or $f(n)\approx k\left(\frac{n}{2}\right)^n$, the best of which seems to be the good approximation

$$f(n)\approx 2.172\sqrt{n}\left(\frac{n}{2}\right)^n$$

$\endgroup$
  • 1
    $\begingroup$ By using Stirling's approximation twice and using the approximation $\frac{\sqrt{i}}{\sqrt{n+i}}\approx \frac{\sqrt{i}}{\sqrt{n}}$ when $n$ is large and then assuming $\sqrt{i}\ll (n+i)!, i!, 3^i$, we have $f(n)\approx \frac{e^{n}n!}{\sqrt{n}}\left(\frac{3}{2}2^{-n}-3^{-n}\right)$. $\endgroup$ – Jam Nov 4 '19 at 13:23
  • $\begingroup$ Very nice approximation and its great to see the techniques used in case I come across similar situations in future..thanks! $\endgroup$ – sonicboom Nov 4 '19 at 14:38
  • 1
    $\begingroup$ Footnote: I think the $2.172\ldots$ constant is $\frac{\sqrt{6\pi}}{2}$, which would fit given the relation to Stirling's approximation. $\endgroup$ – Jam Nov 5 '19 at 22:50
  • 1
    $\begingroup$ Footnote 2: I believe that this can be generalised to $\frac{1}{a^{n}}\sum_{i=1}^{\infty}\frac{\left(n+i\right)^{n+i}}{\left(ai\right)^{i}}\sim \frac{\sqrt{2a\pi n}}{a-1}\left(\frac{n}{a-1}\right)^{n}$. $\endgroup$ – Jam Nov 5 '19 at 23:05
5
$\begingroup$

Only a comment.

I am not sure if you will like this, because my commentary shows that it's unlikely that you will get a satisfying answer in relation to a closed form .

$$\sum\limits_{m=1}^\infty\left(\frac{m+n}{3}\right)^{m+n}\left(\frac{1}{m}\right)^m = \frac{1}{3^n}\sum\limits_{v=0}^\infty{\binom n v}n^{n-v}\left(\frac{d^{v+1}}{dx^{v+1}}\int\limits_0^\infty\frac{h(e^{\frac{t}{3}e^{x-t}})^n}{1-\ln h(e^{\frac{t}{3}e^{x-t}})}dt\right)\big{|}_{x=0}$$

$h(x)~$ is the infinite power tower . $\,$It's useful if $~n\in\mathbb{N}_0$ .

Conclusion: Lower bound and an upper bound make sense, especially an asymptotic formula.

I think the upper bound $~\displaystyle n!\left(\frac{3}{2}\left(\frac{e}{2}\right)^n-\left(\frac{e}{3}\right)^n\right)~$ for $~f(n)~$ could be a good start for looking for a better one.

$\endgroup$
  • $\begingroup$ Please explain how this suggests that a closed form is unlikely. $\endgroup$ – Jam Oct 29 '19 at 14:12
  • 1
    $\begingroup$ @Jam : Because of the integral, of course. And there is no need for downvotes, it's only a comment, a base for considerations, not a claim, not a proof. $\endgroup$ – user90369 Oct 29 '19 at 14:14
  • $\begingroup$ Interesting answer thanks! I have derived an upper bound now..it gives the rate of convergence which is sufficient for what I need. But I would still be interested to see if a closed form is possible or an ‘almost closed form’ if not. $\endgroup$ – sonicboom Oct 29 '19 at 15:23
  • $\begingroup$ @user90369 That upper bound is very nice, I would be interested to see how you derived it. $\endgroup$ – eurocoder Nov 4 '19 at 14:35
  • 1
    $\begingroup$ @eurocoder : You've accepted the other answer, so I think you've tested that it is a better approximation. That's good. But to answer your question: I only used the Stirling formula $~n!\approx (n/e)^n\sqrt{2\pi n}~$ , means: $~x^x\approx x!e^x/\sqrt{2\pi x}~$ with $~x\in\{n,m+n\}~$ . $\endgroup$ – user90369 Nov 4 '19 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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