I am reading a book where the following reduction is performed, but it's not explained exactly what is going on. I'm sorry if this is a dumb question, but I simply don't get how we are deriving the second line from the first line. Can anyone help me?
On
It is true that $$ S \ge \prod_{k=0}^K (n - 3 k) $$ and so \begin{align} S^3 & \ge \prod_{k=0}^K (n - 3 k) \cdot (n - 3 k) \cdot (n - 3k) \\ & \ge \prod_{k=0}^K (n - 3 k) \cdot (n - 3 k - 1) \cdot (n - 3k -2) = n! \end{align} if $n - 3K - 2 = 1$ or $K=n/3-1$.
On
In the first line we have nnn which has been replace by n*(n-1)(n-2) This is valid because we are saying that that S^3 is greater or equal to the first line and since nnn > n(n-1)*(n-2) for all n, it is a valid substitution.
The next 3 terms are (n-3)(n-3)(n-3) which is then replaced by (n-3)(n-4)(n-5). This is valid because (n-3)(n-3)(n-3)>(n-3)(n-4)(n-5) for all n.
The factors continue repeating 3 numbers and being replaced by 3 consecutive decreasing numbers. The new group of numbers is always less than the 3 numbers it replaced so the new group of numbers is always a valid substitution.
The advantage of these substitutions is that you can combine the numbers to equal n!
ok the reasoning goes as follows, whatever $S^3$ is, we know that $$ S^3\ge n*n*n*(n-3)*(n-3)*(n-3)\dots $$ but we also know that $n>(n-1),n>(n-2)$ and $(n-3)>(n-4),(n-3)>(n-5)$ and therefore we just plug in and get the following inequality $$ S^3\ge n*n*n*(n-3)*(n-3)*(n-3)\dots \ge n*(n-1)(n-2)*(n-3)(n-4)(n-5)\dots=n! $$ and thats it.
bests