Why the sequence of Bernstein polynomials of $\sqrt x$ is increasing?

As noted by Paata Ivanishvili, if $f$ is concave on $[0,1]$, then the Bernstein polynomials $B_n(f,p)$ are increasing in $n$. Here is a probabilistic proof:

Let $I_j$ for $j \ge 1$ be independent variables taking value 1 with probability $p$ and $0$ with probability $1-p$. Then $X_n:=\sum_{j=1}^n I_j$ has a binomial Bin$(n,p)$ distribution and the Bernstein polynomial can be written as $B_n(f,p)=E[f(X_n/n)]$. Now for every $j \in [1,n+1]$, the random variable $Y_j=Y_j(n)=X_{n+1}-I_j$ also has a Bin$(n,p)$ distribution and $$ {X_{n+1}} = {\sum_{j=1}^{n+1} (Y_j/n)} \, .$$ For concave $f$, Jensen's inequality gives $$ f \left(\frac{\sum_{j=1}^{n+1} (Y_j/n)}{n+1} \right) \ge \left(\frac{\sum_{j=1}^{n+1} f(Y_j/n)}{n+1} \right) $$ whence $$B_{n+1}(f,p)=E f \left(\frac{X_{n+1}}{n+1}\right)=E f \left(\frac{\sum_{j=1}^{n+1} (Y_j/n)}{n+1} \right) \ge E \left(\frac{\sum_{j=1}^{n+1} f(Y_j/n)}{n+1} \right) =B_n(f,p) $$

While nothing will beat the brilliant probabilistic proof given in Yuval Peres's answer, a more conventional argument goes as follows. Write $$a_{n,k} = \tbinom nk x^k (1-x)^{n-k} $$ and $$ p_{n,k} = \tfrac{k}{n} $$ Observe that $$ \tfrac{k}{n} = (1 - p_{n,k}) \tfrac{k}{n-1} + p_{n,k} \tfrac{k-1}{n-1} . $$ Thus, if $f$ is concave, then $$ f(\tfrac{k}{n}) \geqslant (1 - p_{n,k}) f(\tfrac{k}{n-1}) + p_{n,k} f(\tfrac{k-1}{n-1}) . $$ Multiply this by $a_{n,k}$ and add up to get $$ \begin{aligned} p_n(x) & = \sum_{k=0}^n a_{n,k} f(\tfrac{k}{n}) \\ & \geqslant \sum_{k=0}^n a_{n,k} \Bigl( (1 - p_{n,k}) f(\tfrac{k}{n-1}) + p_{n,k} f(\tfrac{k-1}{n-1}) \Bigr) \\ & = \sum_{k=0}^{n-1} a_{n,k} (1 - p_{n,k}) f(\tfrac{k}{n-1}) + \sum_{k=1}^n a_{n,k} p_{n,k} f(\tfrac{k-1}{n-1}) \\ & = \sum_{k=0}^{n-1} \bigl(a_{n,k} (1 - p_{n,k}) + a_{n,k+1} p_{n,k+1} \bigr) f(\tfrac{k}{n-1}) . \end{aligned} $$ Now an elementary calculation reduces the right-hand side to $p_{n-1}(x)$.

---

(I make this answer CW, since I expect this is exactly the solution Paata had in mind.)

I would also be happy to know the converse implication, that you quoted in the last remark of your notes

Let $f \in C([0,1])$. Then $p_{n+1}(f,x) \geq p_{n}(f,x)$ for all $n \in \mathbb{N}$ and all $x \in [0,1]$ if and only if $f$ is concave. Yuval gave a nice proof of one implication. To show the converse, assume contrary that $f$ is not concave. By adding a linear function if necessary, and scaling the result by a positive constant we can assume that there exists $x \in [a',b'] \subseteq [0,1]$ such that $f(a')=f(b')>1$, and

$0=\min_{[a',b']}f = f(x) < \frac{x-a'}{b'-a'}f(b')+\frac{b'-x}{b'-a'}f(a')$. By continuity we can further find $a<b$ such that $0\leq a' <a <x<b <b' \leq 1$ so that $\min\limits _{[a'b']\setminus [a,b]} f \geq 1$. Then, I claim that for $n$ large enough we must have $p_{n}(f,x)>0$. Indeed,

$$ p_{n}(f,x) = \sum_{0\leq k \leq n} f\left(\frac{k}{n}\right)\binom{n}{k}x^{k}(1-x)^{n-k} \geq -\|f\|_{C}\, n \max\limits_{0\leq k \leq [a'n]}\binom{n}{k}x^{k}(1-x)^{n-k}+\binom{n}{[an]}x^{[an]}(1-x)^{n-[an]}+ \binom{n}{[bn]}x^{[bn]}(1-x)^{n-[bn]} -\|f\|_{C}\, n\max\limits_{[b'n]\leq k \leq n}\binom{n}{k}x^{k}(1-x)^{n-k} $$ Let us show that the sum of the first two terms in the right hand side of the inequality is positive (for $n$ large enough), similarly the sum of the last two terms will be positive. Indeed, to verify

$$ \binom{n}{[an]}x^{[an]}(1-x)^{n-[an]} >\|f\|_{C}\, n \max\limits_{0\leq k \leq [a'n]}\binom{n}{k}x^{k}(1-x)^{n-k} $$ Take $1/n$ power and let $n \to \infty$. Since $\binom{n}{sn}^{1/n} \to s^{-s}(1-s)^{s-1}$ as $n \to \infty$ it suffices to verify that

$$ \max_{0\leq s \leq a'}s^{-s}(1-s)^{s-1}x^{s} (1-x)^{1-s} < a^{-a}(1-a)^{a-1}x^{a}(1-x)^{1-a} $$ Notice that $\varphi(s) := s^{-s}(1-s)^{s-1}x^{s} (1-x)^{1-s}$ is increasing on $[0,a]$. Indeed,

$$ (\ln \varphi (s) )' = \ln \left(\frac{1-s}{s} \cdot \frac{x}{1-x}\right) >0, $$ where the last inequality follows because $x>a\geq s$.

Thus for $n$ large enough $p_{n}(f,x)>0$. On the other hand, as Yuval pointed out, $p_{n}(f,x) = \mathbb{E}f(\frac{\xi_{1}+...+\xi_{n}}{n}) \to \mathbb{E}f(\mathbb{E} \xi_{1})=f(x)=0$ by the strong law of large numbers. Since $n \mapsto p_{n}(f,x)$ increasing we have $p_{n}(f,x) \leq 0$ which is in contradiction with $p_{n}(f,x)>0$ for $n$ large enough.