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

$$

## No comments:

Post a Comment