Why is this binomial coefficient bounded thus? Source: Miklos Bona, A Walk Through Combinatorics.
$$ \forall k\geq 2,\binom{2k-2}{k-1}\leq4^{k-1}.$$
The RHS is the upper bound of the Ramsey number $R(k,k)$.
How can I prove the inequality without using mathematical induction? I've merely expanded the LHS to obtain $\frac{(2k-2)!}{(k-1)!(k-1)!}$.
 A: For every $0\leqslant i\leqslant n$, ${n\choose i}\leqslant\sum\limits_{t=0}^n{n\choose t}=2^n$. Use this for $n=2k-2$ and $i=k-1$.
A: Let $n=k-1$.
We have $\frac {2n!}{n!n!}$.
Then $2n\cdot (2n-1)\cdot(2n-2)\cdot(2n-3)\dotsm 3\cdot 2\cdot 1$.
Taking even terms $2n\cdot(2n-2)\cdot(2n-4)\dotsm 8\cdot 6\cdot 4\cdot 2$
we have 2 common in all term, so it is $\underbrace {2\cdot 2\dotsm2}_{\text{$n$ times}} \cdot n\cdot (n-1)\cdot(n-2)\dotsm 3\cdot2\cdot1 = 2^n \cdot n!$
After canceling with $n!$ we have left  $2^n \cdot (2n-1)\cdot(2n-3)\cdot(2n-5)\dotsm 5\cdot 3\cdot 1/n!$
We can see that $2n > 2n-1$, $2n-2> 2n-3$, etc.,
so the product of odd numbers is less than product of even numbers
therefore  $(2n-1)\cdot(2n-3)\cdot(2n-5)\dotsm 5\cdot 3\cdot 1/n! \le 2^n$,
so $\binom{2n}n \le 2^n \cdot 2^n = 4^n$
A: Consider a set $S$ with $2k-2$ elements. The set $S$ has $2^{2k-2}=4^{k-1}$ subsets. The number of subsets of S that have exactly $k-1$ elements is $\binom{2k-2}{k-1}$. Clearly the number of subsets of $S$ with $k-1$ elements is less than the total number of subsets of $S$. (@Did's answer is effectively the same as mine.)
