# Bounding ${(2d-1)n-1\choose n-1}$

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).

-
As was mentioned here, 6.25 is a typo, and it should have been 6.75. Sorry... –  Gadi A Jun 8 '11 at 18:26

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.

-
@Lubos: This is not "wrong," and there is nothing remotely incorrect here. This is the simplest approach that could be shown to a highschool student. Of course using Stirlings formula gives you something better, I even mentioned that in my answer from the beginning. Not only that I put in the best known result. Do you have no appreciation for the simplicity of an argument? –  Eric Naslund Jun 6 '11 at 17:01
@Lubos: Perhaps you don't understand. I never said that this proof gave 6.25. That was not the point. The point was that we can easily bound it by something of the form $c^n$ for every $k$, which was his second question. –  Eric Naslund Jun 6 '11 at 17:10
@Lubos: What is your problem? There is nothing wrong with this answer, and the argument, while non optimal still it is nice, and there is something to be learned. Now you claim that Chebyshev's estimates are useless.. somewhat tangential, and a point I could argue much more strongly against. If you are having a bad day do not take it on people you do not know on the internet. This is not the place for that. –  Eric Naslund Jun 6 '11 at 17:17
@Luboš Motl: whether or not you have a point, you're being a jerk about it. Cut it out or you'll be suspended. –  Qiaochu Yuan Jun 6 '11 at 18:08
@Qiaochu: Thanks, much appreciated. At first I was really bothered by Lubos. –  Eric Naslund Jun 8 '11 at 0:47

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 .$$

-
I like this approach! –  Eric Naslund Jun 6 '11 at 18:42
@Eric: Thanks... –  Shai Covo Jun 6 '11 at 18:53

(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.

-
Note that, in particular, ${3n-1 \choose n-1} \leq 6.75^{n-1}\,(< 6.75^n)$. –  Shai Covo Jun 9 '11 at 12:16

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.

-