# How do I derive $n!$ from this series?

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? • what is S? you need to state the whole problem – user190080 Jun 24 '15 at 22:56
• Are you sure about that statement (it seems false) ? Where is it from ? Maybe give a bit more context. – Joel Cohen Jun 24 '15 at 22:56
• It's from Artificial Intelligence, a Modern Approach, 3rd ed. q. 3.5. The S is the state space. I will post a screencap. – picardo Jun 24 '15 at 22:58
• This follows by grouping like terms. Then use $(n-k) \le (n-k-l)$ (for appropriate $k,l$, of course). – copper.hat Jun 24 '15 at 22:59
• now wait...this is completely not what you wanted in the first place, $S^3\ge n!$ and not $S^3=n!$ – user190080 Jun 24 '15 at 23:00

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

• Ah, of course. I need to work on my inequalities... thank you. – picardo Jun 24 '15 at 23:19

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!

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

• ah, ok, that looks nicer, although it is $S^3\ge\dots$ – user190080 Jun 24 '15 at 23:14
• don't want to be a nitpicker, but the first $=$ needs to be a $\ge$ – user190080 Jun 24 '15 at 23:17
• Details, details, .. :-) – mvw Jun 24 '15 at 23:20