Proof by induction that given the recurrence $b_{n+1} = b_n-\frac{b_n^2}{2}$, $\frac{1}{n+1}\leq b_n\leq\frac{2}{n+2}$

Question

I need to prove by induction that, given the recurrence $b_{n+1} = b_n-\frac{1}{2} b_n^2$,

$$\frac{1}{n+1} \leq b_n \leq \frac{2}{n+2}.$$

This recurrence comes from another probability problem (in the image attached). I'm completely lost how to prove this inequality. Tried many different approaches, but nothing works, the bounds are not too tight. But if you compute $b_n$ for various values of $n,$ both inequalities always hold. $b_0=1$, $b_1=\frac{1}{2}.$

Would really appreciate your help on this!

Answer 1

We are going to work on sequence ($c_n$) defined by

$$c_n:=1-\beta_n.\tag{0}$$

($c_n$) verifies recurrence relationship $$c_{n+1}=\tfrac12(c_n^2+1) \ \ \text{with} \ \ c_0=0$$

(easy to check ; see graphical representation below).

Remarks :

• The technical interest of using $c_n$ instead of $\beta_n$ is that $c_n$ occurs only once in the RHS of the recurrence relationship (think to the canonical expression for the quadratic of this RHS).

• Recurrence relationship shows that $\forall n, \ c_n\geq 0$ and, by an immediate recurrence, that $c_n \in [0,1]$.

• $c_n$ has a natural interpretation as the probability of the complementary event.

Inequalities to be proved :

$$\forall n, \ \dfrac{1}{n+1} \ \leq \ \beta_n \ \leq \ \dfrac{2}{n+2}$$

become the following ones :

$$\forall n, \ \ 1-\dfrac{2}{n+2}\leq c_n \leq 1-\dfrac{1}{n+1}$$

(observe the reversal of the inequality symbols). Said otherwise :

$$\text{To be established :} \ \ \forall n, \ \ \underbrace{ \ \ \dfrac{n}{n+2}\leq c_n \leq \dfrac{n}{n+1}}_{\text{Property} \ (P_n)}\tag{1}$$

Let us prove (1) by recurrence.

• property $(P_0)$ is true.

• General step : $\forall n, \ (P_n) \implies (P_{n+1})$, i.e.,

$$(2a) \ \ \dfrac{n}{n+2}\leq c_n \leq \dfrac{n}{n+1}\ \ \implies \ \ (2b) \ \ \dfrac{n+1}{n+3}\leq c_{n+1} \leq \dfrac{n+1}{n+2}\tag{2}$$

Let us square the three members of (2a) (legal because all of them are positive) ; then add $1$ and divide by $2$ all of them, giving :

$$\dfrac{(n+2)^2+n^2}{2(n+2)^2} \leq c_{n+1} \leq \dfrac{(n+1)^2+n^2}{2(n+1)^2}.$$

It is now easy to see that (2b) will be established if we are able to show that, for all $n$ :

$$\dfrac{(n+2)^2+n^2}{2(n+2)^2} \geq \dfrac{n+1}{n+3} \ \ \text{and} \ \ \dfrac{(n+1)^2+n^2}{2(n+1)^2} \leq \dfrac{n+1}{n+2}.$$

Indeed, the first inequality is reducible to $4 \geq 0$ and the second one to $n \geq 0$, both true...

Fig. 1 : Graphical representation of the convergence of sequence $(c_n)$. The points on the curve have coordinates $(c_k,c_{k+1})$.

Last remarks :

• Sequence $(c_n)$ can be found on OEIS site as https://oeis.org/A167424 and http://oeis.org/A076628 giving interesting connections. (reference found in the following answer https://math.stackexchange.com/q/12493)

• Experimental computations show that the lower bound $1/(n+1)$ for $\beta_n$ is not tight at all.

Answer 2

If you do not necessarily need induction to prove that, here is a quick solution: For the inequality to be true, we must have $b_0 = 1$, which will be assumed hereafter. Then it is easy to check that $0 \leq b_n \leq 1$ for all $n \geq 0$. Moreover, since

$$ \frac{1}{b_{n+1}} = \frac{1}{b_n} + \frac{1}{2-b_n}, $$

it follows that

$$ \frac{1}{b_n} = 1 + \sum_{k=0}^{n-1} \frac{1}{2 - b_k}. $$

Together with the bounds of $b_n$, this proves

$$ 1 + \frac{n}{2} \leq \frac{1}{b_n} \leq 1 + n, $$

which then translates to the desired inequality.

---

Addendum. It is also easy to check that $b_n \to 0$ as $n\to\infty$. Then by Cesaro-Stolz theorem, we have

$$ \lim_{n\to\infty} \frac{1/b_n}{n} = \lim_{n\to\infty} \left(\frac{1}{b_{n+1}} - \frac{1}{b_n}\right) = \lim_{n\to\infty} \frac{1}{2-b_n} = \frac{1}{2}, $$

and so, $b_n \sim \frac{2}{n}$ as $n\to\infty$. Better asymptotic forms can also be extracted by refining this argument.