I'm studying a book about Markov Chains (Markov Chains and Mixing Times by Yuval Peres), but my question is regarding calculus. The author presents an upper bound to a certain value and then simplifies that bound.
$t\le2(n-1)\,k\,(1+\frac12+...\frac1n)=\left(2+o(1)\right)\log(2)\,nk^2$
Note that $n=2^{k+1}-1.$ Although I believe that the asymptotic expansion of the harmonic number $\log(n)+\gamma+\mathcal{O}\left(\frac1n\right)$ is being used here, I don't understand how exactly they employ it. I'm thinking that it can't be a very complicated simplification, since it's not explained in the text.
Thanks for any help!
Let $H_n = 1 + 1/2 + \dots + 1/n$. Informally, we have $\log n \approx k\log 2$ for $n$ very large, in the sense that $$\lim_{k\rightarrow\infty} \frac{\log (2^{k+1}-1)}{ k \log 2}=\text{constant},$$ which is what I take big-$O$ notation to mean, as opposed to little-$o$ notation which additionally specifies the constant $= 0$. Then \begin{align*} 2(n-1)k H_n &\approx 2(n-1) k (\log n + \gamma + O(1/n)) \\ &\approx 2(n-1) k(k \log 2 + \gamma + O(1/n))\\ &\approx O(1/n)+O(k^2)+2\log2 \;nk^2. \end{align*} I don't know what your $o(1)$ means, but presumably it could mean $O(1)$ and that the first two $O$-terms in the above expansion are neglected and you are left with the result in the book.