Show that $\prod_{k=0}^n |x-k| \le (n-1)!/2$ for $1 \le x \le n-1$.

Question

Let $n \ge 3$, $x \in \Bbb R$ such that $1 \le x \le n-1$. Show that $\prod_{k=0}^n |x-k| \le (n-1)!/2$.

For $n=3$, $1 \le x \le 2$ we want to show $|x(x-1)(x-2)(x-3)|=x(x-1)(2-x)(3-x) \le 1$. We see that some large bounds are easy to guess: $$ x(x-1)(2-x)(3-x) \le 2 \times 1 \times 1 \times 2=4 $$ but not precise enough. Another try: $$ x(x-1)(2-x)(3-x) \le x(3-x) \le 9/4 $$ the last inequality is from the study of $f(x)=x(3-x)$. Same problem. For $n=3$ and $1 \le x \le 2$ let $0 \le y=x-1 \le 1$. We get using AM-GM \begin{align} |x(x-1)(x-2)(x-3)| &= |(y+1)(y)(y-1)(y-2)|\\ &=y(1-y^2)(2-y)\\ &\le (\frac{3-y^2}{3})^3\\ &\le 1 \end{align}

For the general case I tried to use the same approach: let $1 \le x \le n-1$ ie. $0 \le y = (x-1)/(n-2) \le 1$. We have \begin{align} \prod_{k=0}^n |x-k| &= \prod_{k=0}^n |(n-1)y +1-k|\\ &= \prod_{k=0}^l |(n-1)y +1-k| \prod_{k=l+1}^n |(n-1)y +1-k|\\ &= \prod_{k=0}^l ((n-1)y +1-k) \prod_{k=l+1}^n (k-1-(n-1)y)\\ \end{align} where $l = \lfloor (n-1)y+1\rfloor$. Applying AM-GM doesn't really help here. Suppose $y<1$ ie. $l<n$, we see that $$ \prod_{k=0}^l ((n-1)y +1-k) \le \prod_{k=0}^l (n-k)=\frac{n!}{(n-l-1)!} $$ and $$ \prod_{k=l+1}^n (k-1-(n-1)y) \le \prod_{k=l}^{n-1} (k) = \frac{(n-1)!}{(l-1)!} $$ So $$ \prod_{k=0}^n |x-k|\le \frac{(n-1)!}{(l-1)!}\frac{n!}{(n-l-1)!} $$ The bound is too big... I also tried this approach: let $f(x)= \prod_{k=0}^n (x-k)$, $f'(x)=f(x)(\sum_{k=0}^n \frac{1}{x-k})$. I'm trying to find informations about $x$ such that $f'(x)=0$. Let $x \in \Bbb R - [|0,n|]$. So $\sum_{k=0}^n \frac{1}{x-k}=0$. But I'm stuck here.

My questions are:

1. Does someone have a hint or a proof?
2. Can someone give me some advice on how to handle such problems during an exam?

Thanks :)

Answer 1

Consider the function $$f(x)=\prod_{k=0}^n |x-k|, \qquad x\in[1, n-1].$$ This is just a absolute value of a polynomial on a bounded closed interval, and therefore by extreme value theorem it must have a maximum and a minimum at least once. Clearly the minimum value of $f$ is zero and achieve at each integer $1, 2, \cdots, n-1.$ Also, due to the absolute value $f(x)=f(n-x)$ and hence the graph of $f$ is symmetric about the vertical line $x=n/2.$

When $k\lt x\lt k+1$ for some $k\in\mathbb{N}$ in its domain, then by AM-GM inequality we have $$|x-k||x-(k+1)|\le\dfrac{1}{4}\left((x-k)+((k+1)-x)\right)^2=\dfrac14.$$ Or you can consider the minimum value of convex quadratic function $y=(x-k)(x-k-1)$ to get the same bound. Furthermore, we can find bounds for remaining factors by looking at distances. Hence $$1\lt|x-(k-1)|\lt2\lt|x-(k-2)|\lt3\lt\cdots\lt k \lt|x|\lt k+1$$ and $$1\lt|x-(k+2)|\lt2\lt|x-(k+3)|\lt3\lt\cdots\lt n-k-1 \lt|x-n|\lt n-k.$$

We can use these information to compute an upper bound for $f$ at any interval as follows.

• $k=1$: $\quad f(x)\lt2.\dfrac{1}{4}. 2.3.\cdots(n-1)=\dfrac{1}{2}(n-1)!$

• $k=2$: $\quad f(x)\lt3.2. \dfrac{1}{4}.2. \cdots(n-2)=\dfrac{3}{2}(n-2)!$

• $k=3$: $\quad f(x)\lt4.3.2. \dfrac{1}{4}.2. \cdots(n-3)=6(n-3)!.$

Similarly

• $k=r$: $\quad f(x)\lt\dfrac{1}{4}(r+1)!(n-r)!$

• $k=\lfloor n/2 \rfloor$: $\quad f(x)\lt\dfrac{1}{4}(\lfloor n/2 \rfloor+1)!(n-\lfloor n/2 \rfloor)!.$

It is pretty easy to see that the sequence $g(r)=\dfrac{1}{4}(r+1)!(n-r)!$ on $r=1, 2, \cdots, \lfloor n/2 \rfloor$ is decreasing since $$\dfrac{g(r+1)}{g(r)}=\dfrac{r+2}{n-r}\le1.$$

Hence the maximum strict upper bound of $f$ occurs on $(1,2)$ and $(n-2, n-1)$ and it is exactly $$g(1)=\dfrac{1}{2}(n-1)!.$$

Answer 2

I would like to solve a more general problem than this problem and that problem.

First, we find all local maxima of the function $f(x) =\prod_{k=0}^n |x-k|$ in the interval $0 \le x \le n$.

For each interval $[p,p+1)$ with $p\in \{0,...,n-1\}$ we prove that there exists 1 local maximum.

We guess the value of $v_0,v_1,...,v_n$ such that there exists $x_p \in [p,p+1)$ satisfying two following conditions $$v_0x = v_1(x-1) =...=v_n(x-k) \tag{1}$$ $$v_0+v_1+...+v_n=0\tag{2}$$ Solve these 2 conditions, we can have a solution (attention, this is not a unique solution, but we need only 1) as follows $$v_k=\frac{1}{x_p-k}$$ with $x_p \in [p,p+1)$ satisfying this equation $$\sum_{0 \le k \le n}\frac{1}{x_p-k} = 0 \tag{3}$$ Note: For information, it's easy to prove that the equation (3) has exactly one root in each interval $[p,p+1)$ where $p\in \{0,...,n-1\}$.

Now, we apply the AM-GM inequality for $v_k(x-k)$ with $0 \le k \le n$ (we notice that for $k >p$, $v_k$ is negative, then the terms $v_k(x-k)$ are all positive).

\begin{align} f(x) &=\prod_{0 \le k \le n}|x-k| \\ &= \frac{1}{\prod_{0 \le k \le n}|v_k|} \prod_{0 \le k \le n}v_k(x-k) \\ &\le \frac{1}{\prod_{0 \le k \le n}|v_k|} \left(\frac{\sum_{0 \le k \le n}v_k(x-k)}{n+1} \right)^{n+1} = \frac{1}{\prod_{0 \le k \le n}|v_k|k} \left(\frac{-\sum_{0 \le k \le n}kv_k}{n+1} \right)^{n+1} \end{align}

We note that,;from (1) and (3), we have \begin{align} -\sum_{0 \le k \le n}kv_k &= -\sum_{0 \le k \le n}\frac{k}{x_p-k} \\ &= n+1 - x_p\sum_{0 \le k \le n}\frac{1}{x_p-k} \\ &= n+1 \end{align}

Hence, $$f(x) \le \frac{1}{\prod_{0 \le k \le n}|v_k|} \left(\frac{-\sum_{0 \le k \le n}kv_k}{n+1} \right)^{n+1} = \prod_{0 \le k \le n}|x_p-k|\left(\frac{n+1}{n+1} \right)^{n+1} = \prod_{0 \le k \le n}|x_p-k|$$

The local maximum in $x \in [p,p+1)$ occurs when $x = x_p$ where $x_p \in [p,p+1)$ is the solution of (3).

Second, we prove that $f(x_0) \ge f(x_1) \ge ...\ge f(x_{[\frac{n}{2}]})$ and $f(x)$ is a symmetric function at $x = \frac{n}{2}$ (in other words, $f(x) = f(n-x)$).

It's easy to prove the second statement about the symmetry. For the first statement, for $x \in [p,p+1)$ with $p\in \{0,...,[\frac{n}{2}]-1\}$, we have

$$ f(x+1) = \prod_{0 \le k \le n}|(x+1)-k| = \frac{x+1}{|x-n|}\prod_{0 \le k \le n}|x-k| = \frac{x+1}{|x-n|} f(x)$$ As $x \in [p,p+1)$ with $p\in [0,...,([\frac{n}{2}]-1)]$, we have then $x< \frac{n+1}{2}$, so $\frac{x+1}{|x-n|} <1$ or $f(x+1) < f(x)$. We deduce that $$\max_{x \in [p+1,p+2)}f(x) = \max_{x \in [p,p+1)}f(x+1) < \max_{x \in [p,p+1)}f(x)$$ or for all $p\in \{0,...,[\frac{n}{2}]-1\}$ $$f(x_{p})>f(x_{p+1}) \tag{4}$$

Finally, we solve your problem, which corresponds to the case: find the maximum of $f(x)$ in the interval $ 1 \le x \le n-1$ (another particular case is where $0 \le x \le n$ was solved here ).

From (4), we have the function $f(x)$ attains its maximum value $f(x_1)$ in $x \in [1,n-1]$ when $x=x_1$ where $x_1 \in (1,2)$ is the root of the equation (3).

$$f(x) \le f(x_1) = \prod_{0 \le k \le n}|x_1-k| = x_1(x_1-1)(2-x_1) \prod_{3 \le k \le n}(k-x_1) \le \left(\frac{x_1 + (x_1-1) + 2(2-x_1)}{3} \right)^3 \frac{1}{2}\prod_{3 \le k \le n}(k-1) = \frac{(n-1)!}{2}$$

Because $x_1$ doesn't satisfy the condtion of AM-GM inequality ($x_1 = x_1-1 = 2(2-x_1)$), we conclude that $$f(x) < \frac{(n-1)!}{2}$$

Answer 3

It's easy to notice that the function $f(x) =\prod_{k=0}^n |x-k|$ is a symmetric function at $x = \frac{n}{2}$ (in other words, $f(x) = f(n-x)$). So, it suffice to prove $f(x) \le \frac{(n-1)!}{2}$ in the interval $x \in [1, \frac{n}{2}]$.

For $x \in [p,p+1)$ with $p\in \{0,...,[\frac{n}{2}]-1\}$, we have

$$ f(x+1) = \prod_{0 \le k \le n}|(x+1)-k| = \frac{x+1}{|x-n|}\prod_{0 \le k \le n}|x-k| = \frac{x+1}{|x-n|} f(x)$$ As $x \in [p,p+1)$ with $p\in [0,...,([\frac{n}{2}]-1)]$, we have then $x < \frac{n-1}{2}$, so $\frac{x+1}{|x-n|} <1$ or $f(x+1) < f(x)$.

We deduce that for all $p\in \{0,...,[\frac{n}{2}]-1\}$ $$\max_{x \in [p+1,p+2)}f(x) = \max_{x \in [p,p+1)}f(x+1) < \max_{x \in [p,p+1)}f(x)$$ or $$\max_{x \in [1,\frac{n}{2}]}f(x) = \max_{x \in [1,2)}f(x)$$ So, it suffices to prove $f(x) \le \frac{(n-1)!}{2}$ in the interval $x \in [1, 2)$. In this interval, we have $$f(x) = \prod_{0 \le k \le n}|x-k| = x(x-1)(2-x) \prod_{3 \le k \le n}(k-x) = x(x-1)(4-2x) \frac{1}{2}\prod_{3 \le k \le n}(k-x) \tag{1}$$ By AM-GM inequality, $$x(x-1)(4-2x) \le \left(\frac{x + (x-1) + 2(2-x)}{3} \right)^3 = 1 \tag{2}$$ and because $x \in [1, 2)$, then $$\prod_{3 \le k \le n}(k-x) \le \prod_{3 \le k \le n}(k-1) = (n-1)! \tag{3}$$

From (2) and (3), we deduce that (1) holds true. Hence, for all $x\in [1,n-1]$ $$f(x) \le \frac{(n-1)!}{2}$$

Note: The equality can't occur because the equality in (2) occurs if $x = x-1 = 4-2x$, which is impossible.