$\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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