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 typo, and it should have been 6.75. Sorry...2011-06-08

4 Answers 4