Maximum value of the binomial coefficient as a polynomial

Question

What is the maximum (absolute) value of the binomial coefficient

$\begin{pmatrix}x \\ k\end{pmatrix} = \frac{1}{k!}x(x-1)(x-2)\dotsb(x-k+1)$

for real $x$ in the interval $0 \leq x \leq k-1$?

Answer 1

It's easy to see that the extremum in $(0,1)$ has the same magnitude as the one in $(k-1,k-2)$ and is more extreme than any of the other extrema. The extremum in $(0,1)$ occurs at $x_0=(1+o(1))/\ln k$ (by looking at the derivative), but I'll only assume it is $\Theta(1/\ln k)$. Write $x_0=z/\ln k$ and substitute this value into the function like this: $$f(x_0) = \frac{|x_0(x_0-1)\cdots(x_0-k+1)|}{k!} = \frac{z}{k\ln k} \exp\left(\sum_{j=1}^{k-1}\ln\left(1 - \frac{z}{j\ln k}\right)\right)$$ $$ = \frac{ze^{-z}}{k\ln k}(1+o(1)),$$ where the last step comes from expanding the inside log by Taylor series. The maximum of $ze^{-z}$ occurs for $z=1$, so the asymptotic value of the answer is $$ \frac{e^{-1}+o(1)}{k\ln k}.$$ We don't even need to prove $x_0=\Theta(1/\ln k)$ in advance since this expansion shows there is a maximum near $z=1$ and there can only be one maximum in $(0,1)$.

ADDED: Using $\ln(1-y)\le -y$, we obtain a rigorous upper bound $$f(x_0) \lt \frac{e^{-1}}{kH_{k-1}} \lt \frac{e^{-1}}{k\ln k},$$ where $H_t=\sum_{i=1}^t \frac1i$. Experimentally, the first bound is less than 10% high for $k\ge 10$.

Answer 2

I'm not sure it adds anything beyond what's in Brendan McKay's answer, but I'll flesh out my comment. The absolute value of the binomial coefficient we are interested in may be written (for $x \in (0,1)$ and $k>1$ ) as $\frac{x}{k}\prod_{i=1}^{k-1}(1 - \frac{x}{i}).$ Applying the AM-GM inequality to the displayed product, this is at most $\frac{x}{k}(1 - \frac{ xH_{k-1}}{k-1})^{k-1},$ which is in turn at most $$\frac{x e^{-H_{k-1}x}}{k}.$$ As Brendan McKay noted, this is at most $\frac{1}{ekH_{k-1}},$ but perhaps the expression $\frac{x}{k}(1 - \frac{ xH_{k-1}}{k-1})^{k-1}$ will give a better estimate for small $k,$ as that takes maximum value when $x = \frac{k-1}{kH_{k-1}},$ and the maximum value attained there is $\frac{1}{kH_{k-1}}(1-\frac{1}{k})^{k}$ (thanks to Emil Jerabek for a correction here).

Answer 3

Using Euler's reflection formula for the Gamma function, it's not hard to show

$\begin{pmatrix}x \\ k\end{pmatrix} = \frac{\sin \pi(k-x)}{\pi k} \begin{pmatrix}k-1 \\ x\end{pmatrix}^{-1} $

so that for $0 \leq x \leq k-1$,

$\left|\begin{pmatrix}x \\ k\end{pmatrix}\right|\leq \frac{1}{\pi k}$

but checking numerically, this bound doesn't seem to be very tight.

Answer 4

I'll post a sketch for now, and fill it in later. I use C(x) for $\binom{x}{k}$.

Taking derivative wrt x, I get C(x)(sum 1/(x-i)). Thus local extrema occur when one subsum of fractions equals the negative of the complementary sum. In the interval (0,1), one of these maxima occurs near x= 1/log(k- 1/2). I would try numerical evaluation at that value of x to get a feel for the size of the value you want.

Added: Some rough mental (and so error prone) calculation suggest 1/((logk)k^d) as the size of the maximum absolute value for some d less than 2 and likely d close to but greater than 1.