I am given the result $R(s,t) \leq {s+t-2 \choose s-1}$ and asked to 'hence deduce' that $R(s) = O(\frac{4^s}{\sqrt{s}})$
My thoughts currently are: $R(s) \leq {2(s-1) \choose s-1} = \frac{(2s-2)(2s-3)\dots (s)(s-1)\dots 1}{((s-1)!)^2}$
$\Rightarrow R(s) \leq \frac{(2s-2)(2s-3)\dots s}{(s-1)!} $
Now I want to somehow show that $\frac{(2s-2)(2s-3)\dots s}{(s-1)!} \leq A* \frac{4^s}{\sqrt{s}}$ for some constant $A$
However I don't know how to do this and everything I've tried (mostly just expanding terms and approximating some of them) doesn't seem to work and takes much longer than 'hence deduce' suggests it should. I think I'm missing something really obvious and would appreciate it if someone could point out what that is, thank you in advance.
You can use Stirling's approximation: $n! \approx \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$. Since you want to gauge $\binom{2n}{n}$ (where $n=s-1$) you get: \begin{align} \binom{2n}{n} &= \frac{(2n)!}{n!n!} \\ & \approx \frac{\sqrt{2\pi 2n}\cdot\left(\frac{2n}{e}\right)^{2n}}{\left(\sqrt{2\pi n}\cdot\left(\frac{n}{e}\right)^n\right)^2} \\ & = \frac{\sqrt{4 \pi n} \cdot 4^n \cdot \left(\left(\frac{n}{e}\right)^n\right)^2}{2 \pi n \cdot \left(\left(\frac{n}{e}\right)^n\right)^2} \\ & = \frac{\sqrt{2} \cdot 4^n}{\sqrt{2 \pi n}} = \frac{4^n}{\sqrt{\pi n}} \end{align}