Induction arising in proof of Berry Esseen theorem

Question

I've been studying the paper An estimate of the remainder in a combinatorial central limit theorem by Bolthausen, which proves the Berry Essen theorem using Stein's method:

Let $\gamma$ be the absolute third moment of a random variable $X$, and let $X_{i}$ be iid with the same law as $X$. Let $S_{n}=\sum_{i}^{n}X_{i}$, and suppose $E(X)=0$, $E(X^{2})=1$.

The goal is to find some universal constant $C$ such that $|P(S_{n} \leq x) - P(Y\leq x)| \leq C\frac{\gamma}{\sqrt{n}}$.

Let $\delta(n,\gamma) = \sup_{x}|P(S_{n} \leq x) - P(Y\leq x)|$. We would like to bound $\sup_{n}\frac{\sqrt{n}}{\gamma}\delta(n, \gamma)$.

In the proof the following bound is derived:

$\delta(n,\gamma) \leq c\frac{\gamma}{\sqrt{n}}+\frac{1}{2}\delta(n-1,\gamma)$ where $c$ is a universal constant. Noting that $\delta(1,\gamma) \leq 1$, the author claims that the result is implied. However when I try to use induction to get the result the constant $C$ increases without bound $n$ grows. If anyone has studied this paper before, I would love to hear from you.

Answer 1

Let $a_n = \frac{\sqrt{n}}{\gamma} \delta \left( n, y \right)$. The bound you have stated implies that $$a_n \leq c + \frac{2}{3} a_{n - 1}$$ where I replaced $\frac{\sqrt{n}}{\sqrt{n - 1}}$ with $\frac{4}{3}$ which is certainly true for $n > 2$. Therefore, $$a_n \leq c + \frac{2}{3} a_{n - 1} \leq c \left( 1 + \frac{2}{3} \right) + \left( \frac{2}{3} \right)^2 a_{n - 2} \leq \cdots \leq c \frac{1}{1 - \frac{2}{3}} + a_2$$ which is bounded as required.

Answer 2

A slight modification of the answer by Random:

Given that $a_n\le c+\frac23\,a_{n-1}$ for $n\ge3$, take any real $b\ge\max(3c,a_2)$. Then $a_n\le b$ for all $n\ge2$, by induction on $n$.