Quidditch wrote: Let $a_1, a_2, a_3, \dots$ be a sequence of positive integers such that $\text{(i)}$ $a_1=0$ $\text{(ii)}$ for all $i\geq 1$, $a_{i+1}=a_i+1$ or $-a_i-1$. Prove that $\frac{a_1+a_2+\cdots+a_n}{n}\geq-\frac{1}{2}$ for all $n\geq 1$. huh? positive integers, but $a_1 = 0$? Also, if it's positive integer \[ LHS > 0 > -\frac{1}{2} \]

Note that $a_{i+1}^2=(a_i+1)^2=a_i^2+2a_i+1\implies a_{i+1}^2-a_i^2=2a_i+1$. We can compute the telescopic sum: $$(a_{n+1}^2-a_n^2)+(a_n^2-a_{n-1}^2)+\cdots+(a_2^2-a_1^2)=2(a_1+a_2+\cdots+a_n)+n.$$$2(a_1+a_2+\cdots+a_n)+n=a_{n+1}^2-a_1^2=a_{n+1}^2\geq 0\implies \frac{a_1+a_2+\cdots+a_n}{n}\geq -\frac{1}{2}$