# Elegant proof that $\left|(1-x)(2-x)(3-x)\cdots(n-x)\right| < n!$ for all $0<x<n+1$?

I am looking for a nice argument which shows that $$\left|\,(1-x)(2-x)(3-x)\cdots(n-x)\,\right| < n!$$ for all $$0 < x < n+1$$.

I've proven it already (cases based on the integer part of $$x$$), but am unsatisfied with my proof.

My proof, by request: If $$x \in \mathbb{Z}$$ then the LHS is zero. Therefore, let $$k < x < k+1$$ with $$0 \leq k \leq n$$ and $$k \in \mathbb{Z}$$. Then \begin{align} &|(1-x)(2-x)(3-x)\cdots(n-x)| \\ &< |1-(k+1)| |2-(k+1)| \cdots |k-(k+1)|\,|(k+1)-k||(k+2)-k| \cdots |n-k| \\ &= |k||k-1| \cdots |1| \, |1| |2| \cdots |n-k| \\ &= |1| |2| \cdots |n-k| \, |1| \cdots |k-1| |k| \\ &\leq |1| |2| \cdots |n-k| |n-k+1| \cdots |n| \\ &= n! \end{align}

I suspect there's a much nicer way to approach the problem, but I can't seem to find one. Any help is much appreciated!

• Induction ought to work – Mad Physicist Oct 2 '18 at 1:16
• Assume the first n-1 terms give < (n-1)!. Show that n-x < n and then that 1-x < 1! – Mad Physicist Oct 2 '18 at 1:18
• You should provide the proof you described, so that people don't waste their precious time duplicating your effort. Moreover, it will help to know what you consider an "unsatisf[ying]" solution. – Blue Oct 2 '18 at 1:28
• @MadPhysicist Perhaps I'm misunderstanding what you're saying. I can't see how we can assume that the first $n-1$ terms give $<(n-1)!$, since we don't necessarily have $0 < x < n$ when trying to prove the statement for $n+1$. If there's an easy way to work around this, I don't see it, unfortunately. – Samuel Li Oct 2 '18 at 1:39
• @DWade64 Yes - part of the reason I suspect there's a much nicer proof is that the $n!$ bound is very weak; for 1 < x < n, the LHS comes nowhere near $n!$. A much stronger bound (depending in a simple way on $x$) should exist, but I haven't found one yet. – Samuel Li Oct 2 '18 at 18:59

You can use induction here, due to the symmetry of the expression.

Suppose that $$\left|(1-x)(2-x)(3-x)\cdots(n-1-x)\right| < (n-1)!$$ for $$0 < x < n$$.

Then if $$0 < x < n$$, we have $$|n-x|< n$$, so $$|(1-x)(2-x)(3-x)\cdots(n-x)| < n!$$ by the inductive hypothesis.

And if $$n\le x, put $$y=n+1-x$$; now $$0, so we can use the inductive hypothesis on $$y$$, to get $$|(1-y)(2-y)(3-y)\cdots(n-y)| < n!$$ But $$|(1-y)(2-y)(3-y)\cdots(n-y)|$$ is just $$|(1-x)(2-x)(3-x)\cdots(n-x)|$$, with the terms reversed, so we are done.

• D'oh! Never thought to use the symmetry of the problem to patch the inductive proof. I think this is akin to what I was looking for. – Samuel Li Oct 3 '18 at 12:38

Suppose

$$\mid (1-x) (2-x) \cdots (n-x) \mid < n!$$

for all $$0 < x< n+1$$.

If $$0< x < n+1$$, then

$$\mid (1-x) (2-x) \cdots (n-x) (n+1-x) \mid < n! \mid n+1-x \mid < (n+1)!$$

If $$n+1, then let $$y=x-1$$ so $$n

$$\mid (1-x) (2-x) \cdots (n-x) (n+1-x) \mid = \mid (-y) (1-y) (2-y) \cdots (n-y) \mid \\ = \mid y \mid \mid (1-y) (2-y) \cdots (n-y) \mid\\ < \mid y \mid n!\\ < (n+1)!$$

That was the induction step, let's go back to the base case.

$$0 < x < 0+1\\ 0 < 1-x < 1\\ \mid (1-x) \mid = (1-x) < 1!=1$$

What you have is a nice, direct proof. I would only get rid of the absolute values, so that it becomes more obvious how each term is estimated.

So for $$x \in (k, k+1)$$ with an integer $$k$$, $$0 \le k \le n$$, we have $$|(1-x)(2-x)(3-x)\cdots(n-x)| \\ = (x-1)(x-2)\cdots(x-k) \, \times \, (k+1-x)(k+2-x) \cdots (n-x) \\ < (k)(k-1)\cdots (1) \, \times \, (1)(2) \cdots(n-k) \, .$$ In the second part of the product we can increase each factor by $$k$$, so that the expression is $$\le (k)(k-1)\cdots (1) \, \times \, (k+1)(k+2) \cdots(n) = n! \, .$$

Alternatively use that $$(k)(k-1)\cdots (1) \, \times \, (1)(2) \cdots(n-k) = k!(n-k)! = \frac{n!}{\binom nk} \le n! \, .$$

• More simply: the product is less than $m!(n-m)!$ and that is at most $n!$ because $1 \le \binom{n}{m} = n!/(m!(n-m)!)$. – marty cohen Oct 2 '18 at 6:20
• @martycohen: I have added it now, thanks for the suggestion. (I found the direct approach simpler – you would need a similar argument to show that $\binom nm \ge 1$). – Martin R Oct 2 '18 at 7:02
• I never noticed the possibility of using ${n \choose m}$ to bound the final result, and find it quite nice! Unfortunately I could only accept one answer, but an upvote to you. – Samuel Li Oct 3 '18 at 12:37