If one has recurrence function -
$$T(k) = 2T(k-1)+ \frac 1k$$
how can one determine the upper and lower bounds?
For upper bound, I try use 'substitution method' and drew out recurrence tree, illustrated below the first four levels (i=0-3)-
$$i=0: \quad \frac 1k$$ $$i=1: \quad 2(k-1)$$ $$i=2: \quad 4(k-2)$$ $$i=3: \quad 8(k-3)$$
I know height of tree is $log_2(k)$ and total cost per level is $\frac {2^i}{k-i}$. But how can I use this information to make a guess, to then be verified by substitution method?
Additionally, what sort of method could be used to find lower bound? Can I use this same recurrence tree to make a guess for that?
Thank you.