The maximum of $\binom{n}{x+1}-\binom{n}{x}$

Question

The following question comes from an American Olympiad problem. The reason why I am posting it here is that, although it seems really easy, it allows for some different and really interesting solutions. Do you want to give a try?

Let $n$ be one million. Find the maximum value attained by $\binom{n}{x+1}-\binom{n}{x}$, where $0<x<n$ is an integer.

---

Edit: I saw the answers below, and I can say that I posted this one because there is at least one really nice solution, which is not so "mechanical" :) The value of $n$ has no particular meaning, it stands just for a "sufficiently large integer"..

Answer 1

Let $$f(x)=\binom{n}{x+1}-\binom{n}{x},$$ then $$f(x)-f(x-1)=\frac{n!(4x^2-4nx+n^2-n-2)}{(x+1)!(n-x+1)!}$$

The roots of the quadratic are $$\frac{n\pm\sqrt{n+2}}{2}$$

Hence $f(x)>f(x-1)$ up to $\frac{n-\sqrt{n+2}}{2}$.

For $$x>\frac{n+\sqrt{n+2}}{2}$$

it is clear that $f(x)<0$.

So maximum $f(x)$ at $$x=\left\lfloor\frac{n-\sqrt{n+2}}{2}\right\rfloor=\left\lfloor\frac{1000000-\sqrt{1000002}}{2}\right\rfloor=499499$$

Answer 2

$$t_x=\binom n{x+1}-\binom nx=\frac{(n-2x-1)}{(x+1)}\binom nx$$ $$\frac{t_x}{t_{x-1}}=\frac{n-x+1}{(x+1)(n-2x+1)(n-2x)}=z$$ If $z\ge1$: $$\frac{n-x+1}{(x+1)(n-2x+1)(n-2x)}\ge1\implies x\le z_0(\text{say})$$ Then maximum occurs at : $$x=\lfloor z_0\rfloor$$

Answer 3

Note that $$ \begin{align} \binom{n}{x+1}-\binom{n}{x} &=\left[\frac{n-x}{x+1}-1\right]\binom{n}{x}\\ &=\frac{n-2x-1}{x+1}\binom{n}{x}\tag{1} \end{align} $$ $(1)$ is positive for $x\lt\frac{n-1}2$ and negative for $x\gt\frac{n-1}2$.

Furthermore, $$ \begin{align} &\hphantom{}\left[\binom{n}{x+1}-\binom{n}{x}\right]-\left[\binom{n}{x}-\binom{n}{x-1}\right]\\ &=\left(\left[\frac{n-x}{x+1}-1\right]-\left[1-\frac{x}{n-x+1}\right]\right)\binom{n}{x}\\ &=\frac{4x^2-4nx+(n+1)(n-2)}{(x+1)(n-x+1)}\binom{n}{x}\tag{2} \end{align} $$ $(2)$ is $0$ when $x=\frac{n\pm\sqrt{n+2}}2$. If this $x$ is an integer, then $\binom{n}{x+1}-\binom{n}{x}=\binom{n}{x}-\binom{n}{x-1}$. Otherwise, the maximum occurs somewhere between $x$ and $x-1$.

Thus, the maximum value for $(1)$ is where $x=\left\lfloor\dfrac{n-\sqrt{n+2}}2\right\rfloor$.

For $n=1000000$, $x=499499$. $$ \binom{1000000}{499500}-\binom{1000000}{499499}=9.582658295\times10^{301023} $$ whereas $$ \binom{1000000}{499499}-\binom{1000000}{499498}=9.582581749\times10^{301023} $$ and $$ \binom{1000000}{499501}-\binom{1000000}{499500}=9.582658257\times10^{301023} $$