I am trying to upper bound the following sum:
$$\sum_{k=1}^{n/2} \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}}.$$
Based on numerical computations, it seems like the upper bound is a constant (there is also another complicated proof that suggested the upper bound should be a constant). Any idea how to prove this? Stirling's approximation does not seem to help: using Stirling's (in a loose way) I can show that the sum is $O(log n)$.
A related bound that would imply the bound on the above sum is to show that
$$ \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}} \leq \frac{c}{k^2}$$
for some constant $c$.
Thanks!
Best Answer
Lets do some rearranging. First split up the binomial notation: $$\frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}}=\frac{(n-2)!k^{k-2}(n-k)^{n-k-2}}{(k-1)!(n-k-1)!n^{n-3}}$$
Multiply the numerators and denominators to remove the $-1$'s and $-2$'s: $$=\frac{n!}{(n-1)n}\cdot\frac{k}{k!}\cdot\frac{n-k}{(n-k)!}\cdot\frac{k^{k}}{k^{2}}\cdot\frac{(n-k)^{n-k}}{(n-k)^{2}}\frac{n^{3}}{n^{n}}.$$
Now rearrange again so that Sterlings formula jumps out at us: $$=\frac{n}{(n-1)}\frac{n}{k\cdot(n-k)}\cdot\frac{n!}{n^{n}}\cdot\frac{k^{k}}{k!}\cdot\frac{(n-k)^{(n-k)}}{(n-k)!}.$$
Applying Sterlings formula roughly, this becomes $$\approx\frac{n}{(n-1)}\frac{n}{k\cdot(n-k)}\cdot\left(\sqrt{2\pi n}e^{-n}\right)\cdot\left(\frac{1}{\sqrt{2\pi k}}e^{k}\right)\cdot\left(\frac{1}{\sqrt{2\pi(n-k)}}e^{n-k}\right)$$
$$=\frac{n}{(n-1)\sqrt{2\pi}}\cdot\left(\frac{n}{k(n-k)}\right)^{3/2}$$
Now compare the last piece to the integral
$$\int_{1}^{n-1}\left(\frac{n}{x(n-x)}\right)^{3/2}dx.$$
This integral is bounded by a constant for every $n$ so the proof is finished. (The bound can be placed on the integral by a partition trick that yields an infinite geometric series.)
Hope that helps,