26
$\begingroup$

Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$. Then can we prove $f(x)$ is a convex function on $[0,+\infty)$?

Updates:

1) It was pointed out by @user44191 that, observing $\binom{x}{i}=\binom{x-1}{i}+\binom{x-1}{i-1}$, the question is equivalent to $\binom{x-1}{1}+\binom{x-1}{2}+\dots+\binom{x-1}{2u}$ is convex on $[0,+\infty)$.

2) Pointed out by @FedorPetrov @GeraldEdgar @H.H.Rugh:
For $x<0$ each summand $\binom{x}{2i}$ is obviously convex, thus the question is equivalent to $f(x)$ is convex on $\mathbb{R}$.

3) Pointed out by @WłodzimierzHolsztyń‌​ski:
It has $(\Delta^2 f_u)(x) = 1+ f_{u-1}(x-2)$, where $(\Delta f_u)(x)=f_u(x)-f_u(x-1)$. Then we can conclude that $f(x)$ is discrete convex.

$\endgroup$
22
  • 3
    $\begingroup$ This might be easier if we separate each choice function into two choice functions separated by 1 - so you get a sum of choice functions from 1 to $2u$, not skipping anything (but with $x - 1$ on top). $\endgroup$
    – user44191
    Aug 15, 2016 at 4:18
  • 1
    $\begingroup$ I deleted a wrong answer. $\endgroup$ Aug 15, 2016 at 11:51
  • 1
    $\begingroup$ Let $\ h(x) := \binom xw + \binom x{w-2}+\ldots+\binom xk+\ldots\ $ where $\ 0\le k\equiv w\mod 2.\ $ Then one could try to prove that every $\ h_w\ $ is convex in the positive half-line $\ [0;\infty).\ $ Actually, it is true over non-negative integers, i.e. we have a discrete convexity already. $\endgroup$ Aug 15, 2016 at 23:06
  • 1
    $\begingroup$ I've done some numerical experiments with the function $f_n(x)=\binom{x}{0}+\binom{x}{2}+\cdots +\binom{x}{2n}$ which differs from yours by the additive constant $1=\binom{x}{0}$. This function is indeed convex, but it has some other striking features: it is nonnegative and it seems to have a zero locate in $(0,1)$, slightly above $0.4$. (I've verified this only for $n=1,2,3,4,5$. In particular this shows that $f''_n(x)$ vanishes somewhere in $(0,1)$ and may explain why it is so tricky to prove convexity. Also $f_n$ satisfies $\Delta^2_x f_n=f_{n-1}$ where $\Delta f(x):=f(x+1)-f(x)$. $\endgroup$ Aug 16, 2016 at 8:28
  • 1
    $\begingroup$ @Pietro: Let $0\leq x\leq1$. if $U_n(x)=\binom{x}{2n+1}$ then $U_1(x)<\frac16$ (easy to check), $\frac{(x-2n+1)(x-2n)}{(2n)(2n+1)}<1$ (each to check) and $U_n(x)=U_{n-1}(x)\frac{(x-2n+1)(x-2n)}{(2n)(2n+1)}$ imply $U_n(x)<\frac16$ by induction. $\endgroup$ Aug 18, 2016 at 23:32

4 Answers 4

10
$\begingroup$

This is not an answer to your question, is only an equivalent reformulation that seems promising. I write it as an answer only because of space constraints.

For any nonnegative integer $n$ and any $\newcommand{\bR}{\mathbb{R}}$ $x\in\bR$ we define

$$ a_n(x)=\sum_{k=0}^n \binom{x}{2k}, \;\;b_n(x)=\sum_{k=0}^n \binom{x}{2k+1},$$

where for any nonnegative integer $m$ we set

$$ \binom{x}{m}:=\frac{x(x-1)\cdots (x-m+1)}{m!}. $$

For $t\in (-1,1)$ and $x\in\bR$ the series

$$ F_x(t):=\sum_{k=0}^\infty \binom{x}{k}t^k $$

is the Taylor series at $t=0$ of the function $t\mapsto (1+t)^x$ and thus

$$ F_x(t)=(1+t)^x,\;\;\forall |t|<1. $$

The generating series of the even binomial coefficients $\binom{x}{2m}$ is then

$$ F^0_x(t)=\sum_{m\geq 0}\binom{x}{2m}t^{2m}= \frac{1}{2}\Bigl(\, F_x(t)+F_x(-t)\,\Bigr)=\frac{(1+t)^x+(1-t)^x}{2}. $$

The generating series of the odd binomial coefficients $\binom{x}{2m+1}$ is then

$$ F^1_x(t)=\sum_{m\geq 0}\binom{x}{2m+1}t^{2m}= \frac{1}{2}\Bigl(\, F_x(t)-F_x(-t)\,\Bigr)=\frac{(1+t)^x-(1-t)^x}{2}. $$

The generating series of the sequence

$$a_n(x)=\sum_{k=0}^n \binom{x}{2k} $$

is

$$ A_x(t)=\sum_{n\geq 0} a_n(x)t^{2n}=\frac{1}{1-t^2} F_x^0(t)=\frac{(1+t)^x+(1-t)^{x}}{2(1-t^2)}. $$

The generating series of $b_n(x)$ is $$ B_x(t)=\sum_{n\geq 0} b_n(x)t^{2n+1}=\frac{1}{1-t^2} F_x^1(t)=\frac{(1+t)^x-(1-t)^{x}}{2(1-t^2)}. $$

We have $\newcommand{\pa}{\partial}$

$$\pa^2_x A_x(t)=\sum_{n\geq 0} a_n''(x) t^{2n}. $$

The problem is equivalent to showing that, for any $x\in \bR$, the Taylor coefficients at $t=0$ of the function

$$[0,1)\ni t\mapsto \pa^2_xA_x(t) $$

are nonnegative, i.e. for any $x$, the function $t\mapsto \pa^2_x A_x(t)$ is absolutely monotonic on the $t$-interval $[0,1)$; for definition and properties of absolutely monotonic functions see Chap. IV of Widder's classical monograph The Laplace Transform.

Now observe that

$$ \pa^2_xA_x(t)=\frac{(1+t)^x\bigl(\,\log(1+t)\,\bigr)^2+(1-t)^x\bigl(\,\log(1-t)\,\bigr)^2}{2(1-t^2)}. $$

Actually we only need to prove that the even degree Taylor coefficients at $t=0$ of the function

$$ t\mapsto G_x(t)=(1+t)^x\frac{\log^2(1+t)}{1-t^2} $$

are positive for any $x\in\bR$.

Remark. As observed in comments to the question, we can instead study the convexity of the function

$$ c_n(x)=\sum_{j=0}^{2n}\binom{x}{j}.$$

The generating series $$ C_x(t) =\sum_{n\geq 0} c_n(x) t^{2n}, $$

is the even part of

$$ G_x(t)=\frac{(1+t)^x}{1-t}, $$

i.e.,

$$ C_x(t)=\frac{1}{2}\left( \frac{(1+t)^x}{1-t}+ \frac{(1-t)^x}{1+t}\right)=\frac{(1+t)^{x+1}+(1-t)^{x+1}}{2(1-t^2)} =A_{x+1}(t). $$

$\endgroup$
3
  • $\begingroup$ This is cute and leads to a rather elegant proof of convexity on $[0,1]$. Unfortunately, the most difficult interval seems to be $[1,2]$ :-( $\endgroup$
    – fedja
    Aug 16, 2016 at 15:59
  • 2
    $\begingroup$ I think I can do $x\ge 2$ this way too, though it is not so elegant. In principle, we can handle the remaining interval $[1,2]$ by brute force (it is not hard to get some bounds for the second derivatives of individual terms there that form a convergent series), but that would be outright ugly, so I'm not posting the details in the hope that somebody may have brighter ideas. $\endgroup$
    – fedja
    Aug 17, 2016 at 3:44
  • $\begingroup$ @fedja I've been trying myself to get a "clean" argument given that this is such a special circumstance and I have nor been successful so far. $\endgroup$ Aug 17, 2016 at 8:52
8
$\begingroup$

Since it looks like the best we have at the moment is a casework with some brute force estimates, I'll post it just to set the upper bound for the proof clumsiness.

Case 1: $0\le x\le 1$.

We have to show that the even coefficients of $F(t)=\frac{(1+t)^x\log^2(1+t)}{1-t^2}$ are non-negative. To this end, write $\log(1+t)=t\int_0^1\frac{du}{1+ut}$. Then it suffices to show that the even coefficients of $F_{u,v}(t)=\frac{(1+t)^x}{(1-t^2)(1+ut)(1+vt)}$ are non-negative. WLOG $u\le v$. Now write $$ \frac{1}{(1+ut)(1+vt)}=\frac{1}{(v-u)t}\left[\frac{1}{1+ut}-\frac{1}{1+vt}\right]=\frac{1}{(v-u)}\int_u^v\frac{dw}{(1+wt)^2}\,. $$ Thus, it is enough to consider $F_{w,w}$. Also, $\frac{1}{(1+wt)^2}=\frac{(1-wt)^2}{(1-w^2t^2)^2}$ and $\frac{(1+t)^x}{1-t^2}=\frac{1}{(1-t)^{x}(1-t^2)^{1-x}}$, so it is enough to show that the even coefficients of $(1-wt)^2(1-t)^{-x}$ are non-negative. However, the sequence $x, \frac{x+1}2, \frac{x+2}3,\dots$ is non-decreasing for $0\le x\le 1$, so the sequence of its partial products (which is exactly the sequence of the coefficients of $(1-t)^{-x}$) is log-convex and the result follows. Notice that in the last function only the first coefficient can be negative. Nevertheless, because of various other factors, this negativity can easily spread to other odd coefficients.

Case 2: $x\ge 2$.

It will suffice to show that all coefficients of $$ G(t)=\frac{(1+t)^y}{1-t^2}[(1+t)\log(1+t)]^2=\frac{1}{(1-t)^{y}(1-t^2)^{1-y}}[(1+t)\log(1+t)]^2=U(t)V(t)^2 $$ are non-negative. To this end, we will investigate first the coefficients of $V(t)$. We have $$ t^{-1}V(t)=1+\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k(k+1)}t^k\,. $$ Thus, the sum of absolute values of all coefficients of $t^{-1}V(t)$ equals $2$ and the sum of negative coefficients is at most $a=\sum_{k\text{ even}}\frac 1{k(k+1)}\le \frac 16+\frac 12\frac 13=\frac 13$. Here we used a simple inequality $$ \frac{1}{n(n+1)}+\frac{1}{(n+2)(n+3)}+\frac{1}{(n+4)(n+5)}+\dots \\ \le \frac{1}{n(n+1)}+\frac 12\left[\frac{1}{(n+1)(n+2)}+\frac{1}{(n+2)(n+3)}+\dots\right]=\frac{n+2}{2n(n+1)} \tag{$*$} $$ Hence, the sum of absolute values of all negative coefficients of $t^{-2}V(t)^2$ is at most $2a(2-a)\le \frac 23\frac 53=\frac{10}9$ and that bound would be attained only if there were no cancellations. However, the coefficient at $t^2$ is $2\times 1\times(-\frac 16)+(\frac 12)^2$, which already shaves off $1/4$ from the trivial bound mentioned. Hence, the sum of absolute values of all negative coefficients of $t^{-2}V(t)^2$ is below $1$. Also, $t^{-2}V(t)^2=1+t+\dots$.

Thus, it will suffice to show that the coefficients of $U(t)$ are non-negative, bounded by $1$, and have the property that the sum of any two adjacent coefficients is at least $1$.

Note now that the second expression for $U(t)$ implies the non-negativity property immediately. To establish the rest, just observe that $(1+t)^y=1+a_1 t-a_2 t^2+a_3 t^3-\dots$ with $1\ge a_1\ge a_2\ge\dots\ge 0$. Thus, the coefficients of $U(t)$ are $1,a_1,1-a_2, a_1+a_3, 1-a_2-a_4, a_1+a_3+a_3,\dots$ from which everything would follow either for trivial reasons, or from the properties of alternating series with diminishing terms, if we show that $a_1+a_3+a_5+\dots\le 1$. However, this sum is just $\frac 12[(1+t)^y-(1-t)^y]$ evaluated at $t=1$, i.e. $2^{y-1}$.

Case 3: $1\le x\le 2$.

We shall estimate the second derivative of each $f_n(x)=x(x-1)\dots(x-n+1)/n!$ from below separately, to which end we will note that $f_2''(x)=1$, $f_4(x)=\frac 1{24}g(x)$ with $g(x)=x(x-1)(x-2)(x-3)$, and $f_n(x)=g(x)h_n(x)$ with $h_n(x)=(x-4)(x-5)\dots(x-n+1)/n!$ for $n=6,8,10,\dots$. To take care of $g(x)$, use the change of variable $x=\frac 32+z$, $-\frac 12\le z\le\frac 12$, and write $g(x)=(z^2-\frac 14)(z^2-\frac 94)=z^4-\frac 52z^2+\frac{9}{16}$. Note that $g(x)\ge 0$ on $[1,2]$, $g''(x)=-5+12z^2\ge -5$ on $[1,2]$ and $|g'(x)|=|z|\cdot|5-4z^2|\le \frac 52$ on $[1,2]$. Also, $h_n''(x)\ge 0$, $h(x)\le h(1)=\frac 1{2n(n-1)}$ and $|h'(x)|\le |h'(1)|=\frac 1{2n(n-1)}[\frac 13+\frac 14+\dots+\frac 1{n-2}]$. Using the Leibnitz rule $$ f_n''=gh_n''+2g'h_n'+g''h_n $$ and taking into account that the first term is non-negative, we get $$ f_n''\ge -5\frac 1{2n(n-1)}[1+(\frac 13+\frac 14+\dots+\frac 1{n-2})]\,. $$ Now it remains to show that the sum of the bounds on the right over even $n\ge 4$ is above $-1$. Rewrite this sum as $$ \frac 52\left[S_4+(\frac 13+\frac 14)S_6+(\frac 15+\frac 16)S_8+\dots\right] $$ where $S_n=\frac 1{(n-1)n}+\frac 1{(n+1)(n+2)}+\dots\le \frac{n+1}{2(n-1)n}$ by $(*)$. Thus, the whole sum is at most $\frac 52$ times $$ \frac 5{24}+\sum_{k\text{ odd}, k\ge 3}\frac {2k+1}{k(k+1)}\frac{k+4}{2(k+2)(k+3)}\\ \le \frac 5{24}+\max_{k\ge 3}\frac{(2k+1)(k+4)}{(2k+2)(k+3)}\sum_{k\text{ odd}, k\ge 3}\frac 1{k(k+2)}\le\frac 5{24}+\frac{13}{12}\frac 16 $$ because $$ \frac{(2k+1)(k+4)}{(2k+2)(k+3)}=1+\frac{k-2}{2(k+1)(k+3)}\le 1+\frac{1}{2(k+3)}\le\frac{13}{12} $$ for $k\ge 3$. It remains to note that $$ \frac 52\left[\frac 5{24}+\frac{13}{72}\right]=\frac{70}{72}<1\,. $$

$\endgroup$
2
  • 1
    $\begingroup$ The case $x<1$ can also be settled without computation, by noting that $\ell(t):= \frac{1}{(1+t)^{1-x}}\left(\frac{\log(1+t)}{t}\right)^2$ is the Laplace transform of a nonnegative random variable $X$ possessing all moments (the first factor is the LT of $\Gamma(1,1-x)$, and $\log(1+t)/t$ is the LT of $g(x)=\int_{x}^\infty \frac{e^{-y}}{y}\,dy$), and $[t^{2u}] \frac{1}{1-t} \ell(t)$ is an even degree MacLaurin sum of $\ell$, evaluated at 1, and therefore exceeds $\ell(1)>0$. Can this observation be extended to give a more conceptual proof for the other cases? $\endgroup$
    – esg
    Aug 24, 2016 at 18:28
  • $\begingroup$ @esg I tried to follow that route but the function $\ell(t)$ just has the wrong monotonicity to be the Laplace transform of anything for $x>1$, so some extra idea is required to make it work :-(. $\endgroup$
    – fedja
    Aug 24, 2016 at 20:26
6
$\begingroup$

Here's an alternative proof based on probabilistic arguments (showing different aspects). Let $$f_n(x):=\sum_{j=0}^n { x \choose j}=[t^n]\,\frac{(1+t)^x}{1-t}\;\;,$$ and let $^\prime$ denote derivative with resp. to $x$.

We have to show that for even $n=2k$ the second derivative $f_{2k}^{\prime\prime}(x)=[t^{2k}] \frac{(1+t)^x}{1-t}\,(\log(1+t))^2$ is nonnegative. The basic observation used below is that $g(t):=\frac{\log(1+t)}{t}$ is the Laplace transform (LT) of a nonnegative random variable possessing all moments. The relation $g(t)=\int_0^1 \frac{1}{1+st}\,ds$ shows that $g$ is the LT of $U\cdot X_1$, where $U$ is uniform on $[0,1]$, $X_1$ is $\Gamma(1,1)=\exp(1)$ distributed (i.e. has LT $\frac{1}{1+t}$), and the factors are independent.

Case 1: $x<0$. In this case $(1+t)^x $ is the LT of $\Gamma(1, -x)$ . Thus $\ell(t):=(1+t)^x g(t)^2$ is the Laplace transform of a nonnegative rv and (for $k\geq 1$) $f_{2k}^{\prime\prime}(x)=[t^{2k-2}]\, \frac{1}{1-t} \ell(t)$ is an even degree MacLaurin sum of $\ell$, evaluated at $1$, and therefore exceeds $\ell(1)>0$.

Case 2: $x\geq 0$. Since $f_n(x+1)=f_n(x)+f_{n-1}(x)$ it will suffice to show that $f_n^{\prime\prime}(x)\geq 0$ for $x\in [0,1)$ and all $n$.

For $x=0$ all derivatives $f_n^{\prime\prime}(0)$ are nonnegative, since $a_r:=[t^r] (g(t))^2=2\,(-1)^r \frac{H_{r+1}}{r+2}$ , and $a_0=1>0$, $a_{2k}+a_{2k+1}\geq 0$.

Let $0<x<1$ and write $$(1+t)^x =1 +xt\,\frac{ (1+t)^x -1}{xt} =1 +xt\,h_x(t)$$ and accordingly $$f_n^{\prime\prime}(x)=[t^{n-2}] \frac{1}{1-t}\left(1+ x t\,h_x(t)\right)g(t)^2=f_n^{\prime\prime}(0)+ x [t^{n-3}]\frac{h_x(t)g(t)^2}{1-t}\;\;.$$ Here $h_x$ is the LT of $U\cdot X_{1-x}$, where $U$ is uniform on $[0,1]$, $X_{1-x}$ is $\Gamma(1,1-x)$ (LT $(1+t)^{x-1}$) distributed, and the factors are independent, thus $h_x(t)g(t)^2$ is again the LT of a random variable $Z$ posessing all moments.

(1) If $n$ is odd, $n-3$ is even and $f_n^{\prime\prime}(x)\geq f^{\prime\prime}(0)$, since the second term is nonnnegative by the same argument as above.

(2) If $n$ is even, $n-3$ is odd and the second term is the $Z$-expection of a decreasing function, and will therefore not increase if $Z$ is replaced by a stochastically larger random variable. Replacing $U\cdot X_1$ for $U\cdot X_{1-x}$ in the first factor replaces $g$ for $h_x$, makes $Z$ stochastically larger and we get $$f_n^{\prime\prime}(x)\geq f_n^{\prime\prime}(0)+ x [t^{n-3}]\frac{g(t)^3}{1-t}=f_n^{\prime\prime}(0)+x\,f_n^{\prime\prime\prime}(0)\;\;.$$ If $f_n^{\prime\prime\prime}(0)\geq 0$ we're done. If $f_n^{\prime\prime\prime}(0) <0$ it will suffice to show that $f_n^{\prime\prime}(0)+f_n^{\prime\prime\prime}(0)\geq 0$.

This amounts to showing that the (even) partial sums of the coefficients of $c(t):=(\log(1+t))^2 + (\log(1+t))^3 $ are nonnegative, and this can be done

EDIT: some details: the $n$-th coefficient $c_n=[t^n] c(t)$ of $c$ is $$c_n=\frac{(-1)^n}{n}\left(2 H_{n-1}-3(H_{n-1}^2-H_{n-1}^{(2)})\right)$$ Hence $$c_n+c_{n+1}=\frac{(-1)^n}{n(n+1)}\left(-3 H_{n-1}^2 + 8 H_{n-1} + 3 H_{n-1}^{(2)} -2\right)$$ Thus (for $2k\geq 2$) the even partial sums fall until $2k=n+1=12$ and rise thereafter. Since $[t^{12}]\frac{c(t)}{1-t}=\frac{26647}{221760}>0.12$, all even partial sums are nonnegative.

Finally, note that this proof also shows that $f_n$ is convex on $[0,\infty)$ for odd $n$.

$\endgroup$
5
$\begingroup$

(Here is a proof of the convexity of $\sum_{k=0}^n\binom{x}{k}$ on $[0,\infty)$ for any large $n$; with a bit more care the argument should work for all positive even integer $n$ on $[-1,\infty)$, which is the original problem)

We may consider the problem of showing the convexity of $S_n(x):=\sum_{k=0}^n\binom{x}{k}$ on $[-1,+\infty)$ for any positive even integer $n$, which is equivalent to the original, as observed. As also observed, since $S_n$ is smooth and each summand is convex for $x>n-1$, it is sufficient to prove the convexity on $[-1,n-1]$. For odd $n$, the convexity should be true only on $[0,+\infty)$ .

The sum $S_n$ is the $n$-th Taylor polynomial of the function $(1+t)^x$, centered at $t_0=0$ and evaluated at $t=1$. The corresponding remainder integral formula gives:

$$\sum_{k=0}^n\binom{x}{k}= 2^{x} - (n+1)\binom{x}{n+1}\int_0^1(1-t)^{n}(1+t)^{-n-1+x}dt.$$

So in order to prove convexity of the right-hand side on some interval $I=I_n$ we need to show the inequality

$$2^x(\log 2)^2 - \int_0^1(n+1)(1-t)^{n}(1+t)^{-n-1} \bigg[(1+t)^x\binom{x}{n+1}\bigg]''dt\ge0,$$

for $x\in I$ (here $'$ denotes derivative wrto $x$). Note that the integral weight $(n+1)(1-t)^{n}(1+t)^{-n-1}$ in front of the second derivative has mass less than $1$ (for a quick check: up to a sign, $ \int_0^1(1-t)^{n}(1+t)^{-n-1} dt$ is again an integral remainder of a Taylor expansion, namely of $\log(1+t)$, and in fact its value is exactly the remainder of the logarithmic series $\big|\log(2)-\sum_{k=1}^n(-1)^k/k\big|$, which is not larger that $1/(n+1)$.) Therefore $$\int_0^1(n+1)(1-t)^{n}(1+t)^{-n-1} \bigg[(1+t)^x\binom{x}{n+1}\bigg]''dt \le\sup_{0\le t\le 1} \bigg[(1+t)^x\binom{x}{n+1}\bigg]'' $$ $$=\sup_{0\le t\le 1} (1+t)^x\bigg[ \log^2(1+t)\binom{x}{n+1} +2\log(1+t) \binom{x}{n+1}'+\binom{x}{n+1}'' \bigg] $$ $$\le 2^x(1+\log 2)^2 \max\bigg\{\binom{x}{n+1}, \binom{x}{n+1}', \binom{x}{n+1}'' \bigg\}. $$

We can conclude that for a given positive integer $n$, $S_n(x)$ is convex for $x\in I$, provided the uniform norms of $\binom{x}{n+1}$, and of its first and second derivative on the interval $I$ is uniformly less than $1/6$. Since these uniform norms on $I=[0,n]$ converge to $0$ as $n\to\infty$, it follows the convexity of $S_n(x)$ on $[0,\infty)$ for any large $n$. (I do not have handy the relative convergence bounds, that should be classic in polynomial interpolation. For even $n$, by experiments it seems they are less than $1/6$ as soon as $n\ge8$).

Also note that the above weight concentrates around $t=0$, which suggests to break the integral into the two intervals $[0,\tau]$ and $[\tau, 1]$, to be estimated separately; this gives a much better estimate, of course, and should be of use in the original problem for even $n$, which required the bound for $x\in[-1,0]$ too.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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