5
$\begingroup$

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!

  • 0
    @user It holds that $\sum_{k=1}^{n-1} \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}}=\sum_{k=1}^{n-1} \frac{\binom{n}{k}k^{k-1}(n-k)^{n-k-1}}{(n-1)n^{n-2}}=2$, so the sum is exactly $1$ for odd $n$ and a little bit larger than $1$ (converging to $1$ monotonically from above) for even $n$. Maybe someone can prove that result combinatorially.2015-11-29

1 Answers 1

3

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,

  • 0
    Thanks, Eric. This works out if I use the Stirling Series for $n!$ (from http://en.wikipedia.org/wiki/Stirling_series): $n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^ne^{\lambda_n}$ where \frac1{12n +1} < \lambda_n < \frac1{12n}. This is an exact expression for $n!$, it introducing additional $e^{-1/12n}$ type terms which go away in the limit anyway.2011-02-25