Apologies for this is a really trivial question, but I cannot figure out what to do after understanding the pattern of the function.
Say I have this:
$\begin{align} T(n) & = T(n-1) + 1/n \\ & = T(n-2) + 1/(n-1) + 1/n \\ & = T(n-3) + 1/(n-2) + 1/(n-1) + 1/n \\ \end{align}$
So after back-substituting a few times, at the $k$th step, I get this:
$T(n) = T(n-k) + \sum_{i=0}^{k-1} 1/(n-i)$
Now what do I do? How would I arrive at a $\theta$ answer from that equation?
$$T(k)-T(k-1)=\frac{1}{k} \implies \sum^{n}_{k=1}(T(k)-T(k-1))=\sum^{n}_{k=1}\frac{1}{k}$$ so this is a telescoping sum , solving it we get $$T(n)-T(0)=\sum^{n}_{k=1}\frac{1}{k}$$ thus $$T(n)=T(0)+\sum^{n}_{k=1}\frac{1}{k}$$