Suggestion to solve the equation

Question

Suggestion to solve the equation: $$T(n)=2T(n-1)+\frac{1}{n}+1?$$

Answer 1

$$T(n) = 2. T(n-1) + \dfrac{1}{n}$$

$$T(n) - 2. T(n-1) = \dfrac{1}{n}$$.

Divide both sides by $2^{n-1}$, we get,

$$\dfrac{T(n)}{2^{n-1}}-\dfrac{T(n-1)}{2^{n-2}} = \dfrac{1}{n.2^{n-1}}$$

Let $g(n) =\dfrac{T(n)}{2^{n-1}}$. Then, the above equation can be rewritten of the form,

$$g(n) - g(n-1) = \dfrac{1}{n.2^{n-1}}.$$ Summing this from $n=2$ to $n=k$, we get,

$$g(k) - g(1) = \sum_{n=2}^{k} \dfrac{1}{n.2^{n-1}}.$$ So,

$$g(k) = g(1) + \sum_{n=2}^{k} \dfrac{1}{n.2^{n-1}}. $$ $g(1)$ can be found using $T(1)$. Hence,you can obtain the equation for $T(k)$.

NOTE: $\sum_{n=2}^{\infty} \dfrac{1}{n.2^{n-1}}$ converges.

Consider $\sum \dfrac{x^n}{n}$. Then, $$\dfrac{d(\sum\dfrac{x^n}{n})}{dx} = \sum_{n \geq 1}x^{n-1}.$$ We know $\sum x^n = \dfrac{1}{1-x}$ for $|x|<1$. So, $\sum \dfrac{x^n}{n} = - log(1-x)$. In your case, just plug in $x=1/2$.

Answer 2

I'd rather rewrite it as

$$T(n)=2^{n-1}+2^n\sum_{k=2}^n\frac1{k2^k}$$

where $j=n-k$. Now notice that we have

$$\sum_{k=2}^n\frac1{k2^k}\le\sum_{k=2}^\infty\frac1{2^k}=\frac12$$

and hence

$$T(n)\le2^n\implies T(n)\in\mathcal O(2^n)$$

As far as closed form goes, you can rewrite this in terms of the Lerch transcendent:

$$T(n)=2^n\ln(2)-\frac12\Phi\left(\frac12,1,n+1\right)$$