Bounding ${(2d-1)n-1\choose n-1}$ Claim: ${3n-1\choose n-1}\le 6.25^n$.


*

*Why? 

*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).
 A: 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.
A: 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 .
$$
A: (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.
