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.

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!

share|improve this question
    
Numerics indicates that the upper bound is actually 2 attained for $n=2$. Furthermore the sum approaches 1 (quite quickly) for large $n$. –  Fabian Feb 24 '11 at 21:50
    
Thanks, Fabian. It'd be nice to be able to prove it. –  user7469 Feb 24 '11 at 23:18

1 Answer 1

up vote 3 down vote accepted

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,

share|improve this answer
    
I don't think we can just apply Stirling's formula like that. Especially for small $k$. –  Aryabhata Feb 25 '11 at 2:58
    
@Moron: I did say roughly didn't I? In all seriousness, using the actually error term in Stirlings formula, which is introducing a factor of $1+O(\frac{1}{k})$, will not change the answer, namely that it is bounded by a constant. –  Eric Naslund Feb 25 '11 at 3:02
    
All I meant was this needs to be justified. You are probably right, I suppose we can use inequalities like $c_1\sqrt{k}(k/e)^k \lt k!\lt c_2 \sqrt{k}(k/e)^k$, instead and what you wrote will go through... –  Aryabhata Feb 25 '11 at 3:12
    
Thanks, Eric. This works out if I use the Stirling Series for $n!$ (from 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. –  user7469 Feb 25 '11 at 4:09

Your Answer

 
discard

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