A simple Master Theorem for Discrete Divide and Conquer Recurrences - Garet, Olivier (North-Western European Journal of Mathematics, 2023)
The aim of this note is to provide a Master Theorem for some discrete divide and conquer recurrences:\[X_{n}=a_n+\sum_{j=1}^m b_j X_{\lfloor\frac{n}{m_j}\rfloor},\]where the \(m_i\)'s are integers with \(m_i\ge 2\). The main novelty of this work is there is no assumption of regularity or monotonicity for \((a_n)\). Then, this result can be applied to various sequences of random variables \((a_n)_{n\ge 0}\), for example such that \(\sup_{n\ge 1}\mathbb{E}(|a_n|) < \infty \).