<s>[INST] How to find bounds in derivation of Stirling's Formula I'm reading a very nice note by Terry Tao on Stirling's Formula (https://terrytao.wordpress.com/2010/01/02/254a-notes-0a-stirlings-formula/).
At one point in the derivation he states:
$$ \text{“ } n \log\left(1 + \frac{x}{\sqrt{n}}\right) - \sqrt{n}x = -\int_0^x \frac{(x-y) \, dy}{(1 + y/ \sqrt{n})^2}$$
This gives a uniform upper bound
$$ n \log\left(1 + \frac{x}{\sqrt{n}}\right) - \sqrt{n} x \leq -cx^2$$
for some $c>0$, when $|x| \leq \sqrt{n}$ and
$$n \log\left(1 + \frac{x}{\sqrt{n}}\right) - \sqrt{n} x \leq -c|x|\sqrt{n} $$
for $|x|> \sqrt{n}. \text{''}$.
I've been playing around with the first equation a bit, and I don't understand where the upper bounds come from.
How to tell at a glance (as Tao seems to) that these upper bounds hold?
 [/INST] Assume $|x|\leq \sqrt{n}$. First, consider the case $x>0$. Observe
\begin{align}
-\int^x_0 \frac{(x-y)\ dy}{(1+y/\sqrt{n})^2} \leq -\int^x_0 \frac{(x-y)}{4}\ dy = -\frac{1}{8}x^2
\end{align}
because
\begin{align}
\left(1+\frac{y}{\sqrt{n}}\right) \leq \left(1+\frac{x}{\sqrt{n}}\right) \leq 2. 
\end{align}
In the case when $x<0$. Observe
\begin{align}
-\int^x_0 \frac{(x-y) dy}{(1+y/\sqrt{n})^2}= -\int^0_{-|x|} \frac{(|x|+y) dy}{(1+y/\sqrt{n})^2} \leq - \int^0_{-|x|} (|x|+y) dy = -\frac{x^2}{2}
\end{align}
since
\begin{align}
\left(1+\frac{y}{\sqrt{n}}\right) \leq 1.
\end{align}
Now, when $|x|> \sqrt{n}$. Consider the case $x>0$ and observe
\begin{align}
f(x):=n\log\left(1+\frac{x}{\sqrt{n}}\right)-\frac{3}{4}\sqrt{n} x \leq 0
\end{align}
because $f(\sqrt{n}) = n(\log 2- 3/4) \leq 0$ and $f'(x) \leq 0$ for all $x>\sqrt{n}$. Thus, it follows
\begin{align}
n\log\left( 1+ \frac{x}{\sqrt{n}}\right)-\sqrt{n} x< -\frac{1}{4}\sqrt{n}x.
\end{align}  
Lastly, when $x<-\sqrt{n}$ we need to be cautious what Tao actually means because $\log(1-|x|/\sqrt{n})$ is not defined unless we look at the function $\log||x|/\sqrt{n}-1|$ instead.  But then the left-hand side will be positive. So...Tao probably made a typo. 
Edit: He probably looked at the Taylor expansion to see that
\begin{align}
n\log\left(1+\frac{x}{\sqrt{n}}\right)= \sqrt{n} x - \frac{1}{2}x^2 + \frac{x^3}{3\sqrt{n}}-\ldots = \sqrt{n} x+ \mathcal{O}(x^2).
\end{align}
So when $x$ is small (in his case when $x/\sqrt{n}\leq 1$), it should follow that
\begin{align}
n\log\left(1+\frac{x}{\sqrt{n}}\right)-\sqrt{n} x= \mathcal{O}(x^2).
\end{align}
However, Taylor expansion approximation doesn't really work when you are far away from where you want to expand. But when $x$ is big (in your case $x/\sqrt{n}>>1$), it should be clear that
\begin{align}
n\log\left(1+ \frac{x}{\sqrt{n}}\right)-\sqrt{n} x 
\end{align} 
is dominated by $-\sqrt{n}x$ because $n\log(1+\frac{x}{\sqrt{n}})$ doesn't grow fast enough to overtake $-\sqrt{n}x$. 
</s>