The function
f(x) = x/(x-k) has some very useful properties -- especially when we restrict
x to Integers. Let me start with a simple question about Maxima and Minima of
f(x). Applying elementary Calculus may not be useful since
f(x) ↦ +∞ as
x ↦ k+ (goes to
-∞ from the other side and is discontinuous). A quick plot on WolframAlpha reveals the vertical asymptotes [
http://wolfr.am/JSXDdV].
Now lets move our attention to the case where
x is restricted to Integers. First lets consider the function
f(x) when
x takes on integers strictly greater than
k (i.e.
x > k). Notice that
f(x) is decreasing the maximum in this case occurs when
x = k+1. This gives us the following useful fact:
$$
f(n) = \frac{n}{n-k} \leq k+1 \,\,\,\,\,\,\, n \in \{ x\, | \, x > k \vee x \in \cal{I} \}
$$
The above inequality is quite handy in your combinatorial analysis tool book. Let me give you a simple application of this inequality by proving that
nlog(n) = O(log(n!)) (also recall that
log(n!) = O(nlog(n)) which means
nlog(n) = Θ(log(n!))).
$$
\begin{array}{lcl}
&& \frac{n}{n-k} \leq k+1 \,\,\,\,\,\, k \geq 1\\
&& \\
\rightarrow && n \leq (n-k)\times (k+1) \\
\rightarrow && n < (n-k) \times (k+k) = 2 (n-k)\times k
&& \\
&&\\
\rightarrow && n < 2(n-1)\times 1\\
\rightarrow && n < 2(n-2)\times 2\\
\rightarrow && n < 2(n-3)\times 3\\
&& \ldots \\
\rightarrow && n < 2(n-(n-1))\times (n-1) = 2(1\times (n-1)\\
&&\\
&&\mbox{multiplying all the above n-1 inequalities you get the following} \\
&&\\
\rightarrow&& n^{n-1} < \displaystyle\Pi_{k=1}^{n-1} 2(n-k)\times k = 2^n ((n-1)!)^2 \\
\rightarrow&& n^n < 2^n (n!)^2 \\
\rightarrow&& \log(n^n) < \log(2^n(n!)^2) = 2\log(n!) + n \\
\rightarrow&& n\log(n) < 2\log(n!) + n < 2\log(n!) + \log(n!) = 3\log(n!) \\
\rightarrow&& n\log(n) = O(\log(n!)) \,\, \Box\\
\end{array}
$$
