10
$\begingroup$

Let $f(z)=\binom{z}{n},$ where $\binom{z}{n}=\frac{z(z-1)\cdots(z-n+1)}{n!}$ and imagine $n\ge 0$. We can show it is convex when $z\ge n$, for example, by calculating $f''(z)$. In fact, it is true for $z\ge n-1$ as dxiv's answer says. But $z\ge n$ is good enough for combinatorial taste. I wonder could we show it is convex by algebraic or combinatorial methods or any other approaches? We may assume $f$ is defined on reals. But proofs for integers are very appreciated too.

$\endgroup$
5
  • 1
    $\begingroup$ I think you've got the details of what you are trying to prove wrong: $\binom{x}{2} = (x^2 - x)/2$ is convex not concave. Unless I've done my sums wrong, the second derivative of $\binom{x}{3}$ is $x-1$, so $\binom{x}{3}$ is concave on the interval $(-\infty, 1]$ and convex on the interval $[1, \infty)$. (Edit: I did do my sums wrong, but only in a harmless way: the division by $n!$ makes no difference $\ddot{\smile}$). $\endgroup$
    – Rob Arthan
    Sep 11, 2016 at 21:32
  • $\begingroup$ @RobArthan Sorry $z$ should be less $n$. I revised the question. Thanks for your comments! $\endgroup$
    – Connor
    Sep 11, 2016 at 21:35
  • $\begingroup$ But $\binom{x}{2}$ is convex, everywhere, including the non-empty closed interval $[0, 2]$ and $\binom{x}{3}$ is not concave on $[1, 3]$. $\endgroup$
    – Rob Arthan
    Sep 11, 2016 at 21:37
  • $\begingroup$ Here we may imagine $n$ is large enough. $\endgroup$
    – Connor
    Sep 11, 2016 at 21:39
  • $\begingroup$ Another integers-only proof is at Convexity of Binomial Term. $\endgroup$
    – dxiv
    Sep 12, 2016 at 18:47

2 Answers 2

8
$\begingroup$

Let $P(z) = n! f(z) = z(z-1)...(z-n+1)$ with $n \ge 1$. Since $n!$ is a strictly positive constant factor, $P(z)$ will have the same convexity properties as $f(z)$.

$P$ is a polynomial of degree $n$ and has $n$ distinct real roots $\{0,1,..,n-1\}$. It follows that its derivative $P'$ will have $n-1$ distinct roots in the interval $(0, n-1)$ and, for $n \ge 2$, $P''$ will have $n-2$ distinct real roots in the same interval. It follows that:

  • For $n \gt 2$ there will be at least one root of $P''$ in $(0,n-1)$, which means that $P''$ will change sign at least once (and in fact exactly $n-2$ times) in the interval. Therefore $P$ can be neither convex nor concave throughout the entire interval $(0,n-1)$.

  • $P''$ has no roots outside $(0,n-1)$, so $P$ will be either concave or convex on each side of the interval. Simple sign considerations show that $P$ is:

    • convex on $[n-1,\infty)$ for all $n \ge 1$
    • concave on $(-\infty,0]$ for $n$ odd, and convex on $(-\infty,0]$ for $n$ even.
$\endgroup$
1
  • $\begingroup$ Wish the downvoter had left a comment why. $\endgroup$
    – dxiv
    Sep 15, 2021 at 15:33
2
$\begingroup$

Interpret $f(z) = \binom zn$ as the number of combinations of $n$ objects that can be selected from a set of $z$ distinct objects where $n, z \in \mathbb Z$ and $z \geq n \geq 0$.

For $n = 0$, we have $f(z) = 1$, which is a convex function.

For $n \geq 1$, consider a set of $z+1$ distinct objects, $S_{z+1} = \{a_1, \ldots, a_z, a_{z+1}\}$. Then $\binom {z+1}n$ is the number of combinations of $n$ objects selected from $S_{z+1}$. We can partition these combinations into two sets:

  • The combinations in which $a_{z+1}$ is selected.
  • The combinations in which $a_{z+1}$ is not selected.

The number of combinations in the first partition is the number of ways to select $a_{z+1}$ from $\{a_{z+1}\}$ (namely $1$) times the number of ways to select the remaining $n-1$ elements from the $z$-element set $S_{z+1} \setminus \{a_{z+1}\}$, which is $\binom z{n-1}$. So there are $\binom z{n-1}$ combinations in this partition.

The number of combinations in the second partition is the number of ways to select $n$ objects from the $z$-element set $S_{z+1} \setminus \{a_{z+1}\}$, so there are $\binom zn$ combinations in this partition.

Adding together the size of the partitions gives the total number of combinations, so we have $$\binom z{n-1} + \binom zn = \binom {z+1}n.$$ (This is a well-known result but I wanted to make sure it was presented with a combinatorial explanation.) It follows that $$ \binom {z+1}n - \binom zn = \binom z{n-1} $$ and since $z+1 \geq n$ as well, $$ \binom {z+2}n - \binom {z+1}n = \binom {z+1}{n-1}. $$

Since $n - 1 \geq 0$, a similar argument to the one above (including the case $n-1=0$ and the case $n - 1 \geq 1$) shows that $$ \binom z{n-1} \leq \binom {z+1}{n-1}, $$ that is, $$ \binom {z+1}n - \binom zn \leq \binom {z+2}n - \binom {z+1}n. $$

We can extend this via induction to show that if $n \leq z_i < z_m < z_f$ then $$ (z_f - z_m) \left( \binom{z_m}n - \binom{z_i}n \right) \leq (z_m - z_i) \left( \binom{z_f}n - \binom{z_m}n \right). $$

It follows that $$ f(z_m) = \binom{z_m}n \leq \frac{z_f - z_m}{z_f - z_i} \binom{z_i}n + \frac{z_m - z_i}{z_f - z_i} \binom{z_f}n = (1-\lambda) f(z_i) + \lambda f(z_f) $$ where $0 < \lambda = \dfrac{z_m - z_i}{z_f - z_i} < 1$, which satisfies a reasonable definition of what it means for a function over integers to be convex over the integers greater than or equal to $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .