Using series to produce guess for algorithm analysis I need to find the upper asymptotic bound for the recursion:
$$
T(k) = 2T(k-1)+\frac{1}{k}
$$
I was able to determine: 


*

*The height of this tree is $k-1$.

*The cost of each level is $\displaystyle{\frac{2^i}{k-i}}$.
So then I am using the following formula to get an upper bound estimate:
$$
T(n) = 2^h*T(1) + \sum \frac{2^i}{k-i},
$$
where the sum term is from $i=0$ to $h-1$. By plugging in the fact that the height, $h = k-1$, this formula can be expanded to
$$
T(n) = 2^{k-1}*T(1) + \sum\frac{2^i}{k-i},
$$
where the sum term is from $i=0$ to $k-2$. However, I am stuck at reducing the summation term to produce an estimated Big(O) of just the first time, or $O(2^k)$.
Thanks.

I tried to solve this from scratch:
$$
\\
T(n) = 2T(n - 1) + \frac{1}{n}
\\
T(n) = 2(2T(n - 2) + \frac{1}{n - 1}) + \frac{1}{n}
\\
T(n) = 2(2(2T(n - 3) + \frac{1}{n - 2}) + \frac{1}{n - 1}) + \frac{1}{n} = 2^3T(n - 3) +\frac{2^2}{n - 2}+\frac{2^1}{n - 1} + \frac{2^0}{n}
\\
T(n) = 2^kT(n - k) + \sum_{i = 0}^{k - 1} \frac{2^i}{n - i}
\\
\text{When } n - k = 0 \text{(instead of n - k = 1, to simplify)} \Rightarrow  k = n
\\
T(n) = 2^nT(0) + \sum_{i = 0}^{n - 1} \frac{2^i}{n - i}
\\
T(n) = 2^n -\frac{\frac{1}{2}^{n + 1}\ { }_2F_1(1, n + 1;n+2; \frac{1}{2})}{n + 1} - \frac{1}{2}  - \log(-\frac{1}{2})
$$
With a helpful answer here and here.
Intuitively, however, I think that (proof here): $$ { }_2F_1(1, n + 1;n+2; \frac{1}{2})\ \in\ O(2^n).$$
