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

  • 1
    The maximum occurs between 0 and 1 (and symmetrically between $k-2$ and $k-1$). – Brendan McKay Jun 28 '14 at 16:48
up vote 11 down vote accepted

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

  • Yes, I put my answer in just before boarding my plane and couldn't fix it until landing ;). – Brendan McKay Jun 29 '14 at 0:47
  • I think you can get to the same point by using the AM-GM inequality on the displayed product in $\frac{x}{k}\prod_{i=1}^{k-2}\frac{k-i-x}{k-i}$ for $x \in (0,1).$ – Geoff Robinson Jun 30 '14 at 9:02

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

  • 2
    Actually, I believe that $\frac{x}{k}(1 - \frac{ xH_{k-1}}{k-1})^{k-1}$ takes maximum value for $x=(1-k^{-1})H_{k-1}^{-1}$, and the maximum value is $(kH_{k-1})^{-1}(1-k^{-1})^k$. – Emil Jeřábek Jun 30 '14 at 14:04
  • @Emil Jerabek: Yes, you are correct. – Geoff Robinson Jun 30 '14 at 15:27

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.

  • If you just want asymptotic results, I believe a straightforward analysis of $\sum\ln (x-j)$, splitting the sum into two parts, $j\le j_0$ and $j>j_0$, will produce a rather accurate estimate. – Christian Remling Jun 28 '14 at 20:05

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.

  • Isn't it the case that there is exactly one local extremum in $(i,i+1)$ for each integer $i$ with $0 \leq i \leq k-2$? This doesn't necessarily conflict with your answer. – Geoff Robinson Jun 28 '14 at 19:31
  • @Geoff, yes it is so. It is also clear the C(x) evaluated at thos middle extrema will be smaller by a factor of roughly at least 1/k than when evaluated at the extremal values in (0,1) or (as noted above by Brendan McKay) in (k-2,k-1). – The Masked Avenger Jun 28 '14 at 19:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.