Sunday, January 05, 2014

Useful properties of the function $$f(x) = \frac{x}{x-k}$$

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}$$