Inequality for the expected value of the sum of Bernoulli random variables

Question

I'm stuck with this seemingly simple inequality.

Suppose that $X_1,X_2,\ldots$ are Bernoulli random variables and denote $S_n=X_1+\ldots+X_n$. Let $n_k=\inf\{n:\operatorname ES_n\ge k^2\}$ for $k\ge1$. Show that the inequality $$ k^2\le\operatorname ES_{n_k}\le k^2+1 $$ is valid for $k\ge1$.

The first inequality follows from the definition of $n_k$, but how can we make sure that the second inequality is valid? We have that $$ \operatorname ES_{n_k}=\operatorname EX_1+\ldots+\operatorname EX_{n_k}\le n_k $$ since $\operatorname EX_m\le 1$ for $m\ge1$, but we only know that $n_k\ge k^2$.

Any help is much appreciated!

Answer 1

By the definition of $n_k$ we find $$\mathbb ES_{n_k}\geq k^2$$ and also $$\mathbb ES_{n_k-1}<k^2$$

Here $$ES_{n_k}=\mathbb E[S_{n_k-1}+X_{n_k}]=\mathbb ES_{n_k-1}+p$$ where $p$ denotes the parameter of $X_{n_k}$ so the last equality leads to $$\mathbb ES_{n_k}=\mathbb ES_{n_k-1}+p<k^2+1$$

Answer 2

As you say, the left inequality follows from the definition of $n_k$. Suppose the right inequality were false. That is, suppose $$E[S_{n_k}]>k^2+1$$

Then, since $E[X_{n_k}]≤1$ we must have $E[S_{n_k-1}]>k^2$ whence we have found an integer smaller than $n_k$ which satisfies the defining inequality for $n_k$, a contradiction.