Deriving the fact that the approximation $\log(n!) \approx n\log(n) - n + \frac{1}{2}\log(2\pi n)$ is $O(1/n)$. I get to begin with Stirling's approximation, for any $C \in \mathbb{Z}_{\geq 0}$, there exists some $N \in \mathbb{Z}_{\geq 0}$ such that $N > C$ and for all $n > N$:
\begin{align*}
    &\quad \left|n! - \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\right| \leq C \left|\frac{1}{n}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right| \\
    &\Rightarrow -C \frac{1}{n}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \leq n! - \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \leq C \frac{1}{n}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n \\
    &\Rightarrow -C \frac{1}{n}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n + \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \leq n! \leq C \frac{1}{n}\sqrt{2\pi n}\left(\frac{n}{e}\right)^n + \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \\
    &\Rightarrow \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(-C \frac{1}{n} + 1\right) \leq n! \leq \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(C \frac{1}{n} + 1\right)
\end{align*}
Now we are in a position to make further manipulations:
\begin{align*}
&\quad \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(-C \frac{1}{n} + 1\right) \leq n! \leq \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(C \frac{1}{n} + 1\right) \\
&\{\text{$\log$ is monotonic}\} \\
&\Rightarrow \log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(-C \frac{1}{n} + 1\right)\right) \leq \log\left(n!\right) \leq \log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(C \frac{1}{n} + 1\right)\right) \\
&\{\text{take the average of the upper ($U(n)$) and lower bounds ($L(n)$)}\} \\
&\{\text{$\log(n!) \approx f(n)$ means $|f(n) - \log(n!)| \leq K \left[U(n) - L(n)\right]$, where $0 \leq K \leq 1$}\} \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(C \frac{1}{n} + 1\right)\right) + \frac{1}{2}\log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(-C \frac{1}{n} + 1\right)\right) \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\left(\log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(C \frac{1}{n} + 1\right)\right) + \log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(-C \frac{1}{n} + 1\right)\right)\right) \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\log\left((\sqrt{2\pi n})^2\left(\frac{n}{e}\right)^{2n}\left(C \frac{1}{n} + 1\right)\left(-C \frac{1}{n} + 1\right)\right) \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\log\left(2\pi n\left(\frac{n}{e}\right)^{2n}\left(\frac{-C^2}{n^2} + 1\right)\right) \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\log\left(2\pi n\right) +  \frac{1}{2}\log\left(\frac{n^{2n}}{e^{2n}}\right) + \frac{1}{2}\log\left(1 - \frac{C^2}{n^2}\right) \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\log\left(2\pi n\right) +  \frac{1}{2}\log\left(n^{2n}\right) - \frac{1}{2}\log\left(e^{2n}\right) + \frac{1}{2}\log\left(1 - \frac{C^2}{n^2}\right) \\
&\Rightarrow \log(n!) \approx \frac{1}{2}\log\left(2\pi n\right) +  n\log\left(n\right) - n\log\left(e\right) + \frac{1}{2}\log\left(1 - \frac{C^2}{n^2}\right) \\
&\Rightarrow \log(n!) \approx  n\log\left(n\right) - n + \frac{1}{2}\log\left(2\pi n\right) + \frac{1}{2}\log\left(1 - \frac{C^2}{n^2}\right)
\end{align*}
From here I could expand $\log(1 + x)$ about $x = 0$ (note that $0 < \frac{C^2}{n^2} < 1$, as $C < n$, and $0 < n, C$, and also $C^2/n^2$ is pretty close to $0$ most of the time, as $n > C$). The first term of the Taylor series expansion for $\log(1 + x)$ about $x = 0$ is simply $x$.   
\begin{align*}
&\quad \log(n!) \approx  n\log\left(n\right) - n + \frac{1}{2}\log\left(2\pi n\right) + \frac{1}{2}\log\left(1 - \frac{C^2}{n^2}\right) \\
&\Rightarrow \log(n!) \approx  n\log\left(n\right) - n + \frac{1}{2}\log\left(2\pi n\right) - \frac{C^2}{2n^2}
\end{align*}
But this seems to suggest my error is $O(1/n^2)$? Isn't this approximation supposed to be $O(1/n)$? Please advise on where I went wrong.
 A: Everything you've written here is 'correct' — but let's take a closer look at what it means.  Your definition of $\approx$ says: "$\log(n!)\approx f(n)$ means that $\left|f(n)-\log(n!)\right|\leq K (U(n)-L(n))$ for some $0\leq K\leq 1$".  And we have $L(n) = n\log n-n+\log(2\pi n)+\log(1-\frac Cn)$ and $U(n)=n\log n-n+\log(2\pi n)+\log(1+\frac Cn)$.  So the difference between these terms — the bound you've put on the 'quality' of $\approx$ — is $\log(1+\frac Cn)-\log(1-\frac Cn)$. But the best you can say about this is that it's $O(\frac1n)$, so that's what your result is: $\log(n!)\in n\log n-n+\log(2\pi n)-\frac{C^2}{2n^2}+O(\frac1n)$.  And now there's no point in including the $-\frac {C^2}{2n^2}$ term, because the $O(\frac1n)$ term 'overwhelms' it.
A: Nothing justifies that a function is equivalent to the average of the left and right-hand sides in an inequality.
$n^2<n^3<n^4$ but that doesn't make $n^3\sim \dfrac{n^2+n^4}{2}$.
Just after you use the monotonicity of $\log$ you can already conclude by saying that $\log(1+\frac{C}{n})\leq \frac{C}{n}$.
