9
$\begingroup$

Claim: ${3n-1\choose n-1}\le 6.25^n$.

  1. Why?

  2. Can the proof be extended to obtain a bound on ${(2d-1)n-1\choose n-1}$, with the bound being $f(d)^n$ for some function $f$?

(These numbers describe the number of some $d$-dimensional combinatorial objects; claim 1 is the case $d=2$, and is not my claim).

  • 0
    As was mentioned here, 6.25 is a t$y$po, and it should have been 6.75. Sorry...2011-06-08

4 Answers 4

6

First, lets bound things as easily as possible. Consider the inequality $\binom{n}{k}=\frac{(n-k)!}{k!}\leq\frac{n^{k}}{k!}\leq e^{k}\left(\frac{n}{k}\right)^{k}.$ The $n^k$ comes from the fact that $n$ is bigger then each factor of the product in the numerator. Also, we know that $k!e^k>k^k$ by looking at the $k^{th}$ term in the Taylor series, as $e^k=1+k+\cdots +\frac{k^k}{k!}+\cdots $.

Now, lets look at the similar $3n$ and $n$ instead of $3n-1$ and $n-1$. Then we see that $\binom{3n}{n}\leq e^{n}\left(3\right)^{n}\leq\left(8.15\right)^{n}$and then for any $k$ we would have $\binom{kn}{n}\leq\left(ke\right)^{n}.$

We could use Stirlings formula, and improve this more. What is the most that this can be improved? Apparently, according to Wolfram the best possible is $\binom{(k+1)n}{n}\leq \left(\frac{(k+1)^{k+1}}{k^k}\right)^n.$

(Notice that when $k=2$ we have $27/4$ which is $6.25$)

Hope that helps.

  • 0
    @Qiaochu: Thanks, much appreciated. At first I was really bothered by Lubos.2011-06-08
4

In the meanwhile, you may consider the following.

Suppose that $X$ is a binomial$((2d-1)n-1,p)$ random variable ($0 < p < 1$). Then, $ {\rm P}(X = n - 1) = {(2d-1)n-1 \choose n-1} p^{n-1}(1-p)^{n(2d-2)} \leq 1. $ Putting $z=1/p > 1$, we thus have $ {(2d-1)n-1 \choose n-1} \leq z^{n-1} \bigg(\frac{z}{{z - 1}}\bigg)^{n(2d - 2)} = \frac{1}{z}\bigg[\frac{{z^{2d - 1} }}{{(z - 1)^{2d - 2} }}\bigg]^n . $ So, we want to minimize $ \psi(z) = \frac{{z^{2d - 1} }}{{(z - 1)^{2d - 2} }},\;\; z > 1. $ In the case where $d=2$, we get $ {3n-1 \choose n-1} \leq \frac{1}{z}\bigg[\frac{{z^3 }}{{(z - 1)^2 }}\bigg]^n. $ Here, $\psi(z) = \frac{{z^3 }}{{(z - 1)^2 }}$ attains its minimum at $z=3$, where $\psi(z)=27/4$. Hence $ {3n-1 \choose n-1} \leq \frac{1}{3}\bigg(\frac{{27}}{4}\bigg)^n = \frac{1}{3}6.75^n . $

EDIT: For general $d$, the function $\psi(z)$ attains its minimum at $z=2d-1$ (indeed, $\psi(z) \to \infty$ as $z \downarrow 1$ or $z \to \infty$, and, as an elementary calculation shows, \psi'(z)=0 for $z=2d-1$). Hence, $ {(2d-1)n-1 \choose n-1} \leq \frac{1}{{2d - 1}}\bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^n . $

1

(First note Gadi's comment below the question.)

In my previous answer, I derived the inequality $ {(2d-1)n-1 \choose n-1} \leq \frac{1}{{2d - 1}}\bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^n , $ which is already more than needed because of the factor $1/(2d-1)$ (recall that in the case $d=2$ the right-hand side is equal to $(1/3)6.75^n$). However, this inequality can be further improved to $ {(2d-1)n-1 \choose n-1} \leq \bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^{n-1} , $ which is optimal since equality holds when $n=1$.

The last inequality can be proved by induction as follows (for $d \geq 2$ a fixed integer). First, we have equality when $n=1$. Next note that $ {(2d-1)(n+1)-1 \choose n} = \frac{{((2d - 1)n - 1)!}}{{(n - 1)!((2d - 2)n)!}}\frac{{(2d - 1)n}}{n}\frac{{\prod\nolimits_{k = 1}^{2d - 2} {((2d - 1)n + k)} }}{{\prod\nolimits_{k = 1}^{2d - 2} {((2d - 2)n + k)} }}. $ Since, for any $1 \leq k \leq 2d-2$, $ \frac{{(2d - 1)n + k}}{{(2d - 2)n + k}} \le \frac{{2d - 1}}{{2d - 2}}, $ it thus follows that $ {(2d-1)(n+1)-1 \choose n} \leq {(2d-1)n-1 \choose n-1} \frac{{2d - 1}}{1} \bigg(\frac{{2d - 1}}{{2d - 2}}\bigg)^{2d - 2} . $ Now, under the induction hypothesis that $ {(2d-1)n-1 \choose n-1} \leq \bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^{n-1} , $ we get $ {(2d-1)(n+1)-1 \choose n} \leq \bigg[\frac{{(2d - 1)^{2d - 1} }}{{(2d - 2)^{2d - 2} }}\bigg]^{n}, $ completing the proof.

  • 0
    Note that, in particular, {3n-1 \choose n-1} \leq 6.75^{n-1}\,(< 6.75^n).2011-06-09
-3

Just use the Stirling formula $n! \sim \sqrt{2\pi n} (n/e)^n$ for large $n$ and neglect the $\sqrt{2\pi n}$ factor for a while. That gives us a good estimate for your expression $(3n-1)! / [ (n-1)!(2n)! ] \sim (2n)^{-2n}(n-1)^{1-n} (3n-1)^{3n-1} $ Note that the powers of $e$ cancel. For large $n$, you may also approximate the bases of the powers simply by $2n,n,3n$, respectively. Then you get $\sim 2^{-2n} 3^{3n} = (27/4)^{n} $ because the powers of $n$ cancel, too. Note that $27/4 = 6.75$. I have only calculated the estimate - which is actually a better result because it shows that the number $6.75$ is exact in the large $n$ limit. To prove the inequality, you have to carefully watch whether the Stirling formula underestimates or overestimates it. At any rate, it's straightforward to check that the inequality holds for any positive $n$.

It's enough to check it explicitly for a few first small values of $n$, and for larger ones, it can be shown that the $(27/4)^n$ Ansatz is being approached from the right side by computing the sign of the first subleading correction to this approximation. If you enumerate the first few binomial coefficients over the approximation (which should be smaller than one) by Mathematica

[Table[Binomial[3 n - 1, n - 1]/(27/4)^n, {n, 1, 20}]] 

you will get

{0.14814815, 0.10973937, 0.091043032, 0.079482012, 0.071435685, 0.06542258, 0.060709598, 0.056887142, 0.053706089, 0.051005081, 0.048674402, 0.046636504, 0.04483482, 0.043226987, 0.041780567, 0.040470244, 0.039275935, 0.038181474, 0.037173681, 0.036241691}

The numbers are clearly smaller than one, and from the beginning, the decrease is uniform.

For your case of $d$ dimensions, the relevant surviving terms are replaced by $ \sim (2d-2)^{(2-2d)(n-1)} (2d-1)^{(2d-1)(n-1)} $ so $27/4$ gets replaced by $(2d-1)^{2d-1}/(2d-2)^{2d-2}$. For $d=2$, you get $3^3/2^2 = 27/4$. For $d=3$, you would get $5^5/4^4$, and so on.

Note that the proof only works for 27/4 = 6.75. This number couldn't be reduced further (6.25 is a typo) and any proof that replaces 6.75 by a larger number fails to prove the original assertion.