Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 2 / d / Solution

Absorb the finitely many exceptional initial terms in the Big O notation assumption into a constant $C>0$, so that $|a_n|\le Cn$ for every $n\ge 1$. This is possible because each initial term is finite and each index is positive. We prove the stronger bound $|{}^k{b}_n|\le Cn$ for every $k,n\ge 1$.

The case $k=1$ is the chosen bound. If it holds at $k-1$, the triangle inequality givesMathematical induction completes the proof. Thus ${}^k{b}_n=O(n)$ for every fixed $k$; in fact the same constant works for all the iterated Cesàro means. This is the linear-growth bound for iterated Cesàro means.