Prove that $\left( \sum_{j=0}^{\left[n/2\right]} {n \choose j} \left(1+p\right)^j \right)^{1/n}$ is increasing in $n$

binomial-coefficientssummation

I need to prove that ($p>0$ and $[x]$ is the greatest integer $\leq x$):

$$L(n) = \left( \sum\limits_{j=0}^{\left[\frac{n}{2}\right]} {n \choose j} \left(1+p\right)^j \right)^{\frac{1}{n}}$$

is an increasing function of $n$. It is quite apparent numerically but is surprisingly hard to prove. I thought of taking logarithm on both sides:

$$\log(L(n)) = \frac{\log\left( \sum\limits_{j=0}^{\left[\frac{n}{2}\right]} {n \choose j} \left(1+p\right)^j \right)}{{n}}$$

But this doesn't seem to lead anywhere.

One idea I had that provides a vague outline: let $p=0$. Then we get:

$$L(n) = \left( \sum\limits_{j=0}^{\left[\frac{n}{2}\right]} {n \choose j} \right)^{\frac{1}{n}}$$

For odd $n$ this becomes:

$$L(n) = \left( \frac{2^n}{2}\right)^{\frac{1}{n}} = \frac{2}{2^{\frac{1}{n}}}$$

and this is an increasing function. So, adding $p>0$ shouldn't make this decreasing.

EDIT: Here is some python code that demonstrates that the function is increasing.

import numpy as np
import matplotlib.pyplot as plt
from scipy.special import comb

def binom_partial_sum(n,p=.5):
    b_sum=0
    for j in range(int(n/2)+1):
       b_sum+=comb(n,j)*(1+p)**j
     return b_sum**(1/n)
sums = np.array([binom_partial_sum(i,p=0.1) for i in range(11,301,1)])
plt.plot(np.arange(11,301,1),sums,label="partial sum")

EDIT: turns out the premise of this question is wrong. The expression increases over the long range, but nothing can be easily said over short increments. For example, see plot below of the partial sum with $n$ ($p=3.0$):
enter image description here

Best Answer

I'm writing this here in case getting an idea of the dominant behavior of the function suffices for your purposes.

Focusing on just the even terms of the sequence for concreteness, let $X_n$ be a random variable distributed as $\text{Binom(2n, 1/2)}.$ Also let $\alpha = 1+p.$ We have

$$ \frac{L(2n)}{2} = \left( \sum_{k=0}^n \mathbb{P}(X_n = k) \alpha^k\right)^{\frac{1}{2n}}$$

Letting $Y_n = X_n - n$ and shifting the index, we have

$$L(2n) = 2 \sqrt{\alpha} \left( \sum_{k= -n}^0 \mathbb{P}(Y_n = k) \alpha^k \right)^{\frac{1}{2n}}$$

By the normal approximation to the Binomial, the term inside the brackets is approximately $$ \int^{1/2}_{-n-1/2} \frac{1}{\sqrt{n\pi}} \exp \left(-\frac{y^2}{n} \right) \ \alpha^y \ dy \\ = \frac{1}{2} \exp\left(\frac{n\log^2 \alpha}{4}\right) \left( \text{erf}\left( \frac{n \log \alpha + 2n+1}{2\sqrt{n}} \right)-\text{erf}\left( \frac{n\log \alpha - 1}{2\sqrt{n}} \right) \right).$$

This should match your plot fairly closely. We could use the asymptotic expansion of the error function to give an expansion of this function (although I would recommend using a computer algebra software such as Mathematica).

Related Question