Given recursive function:
$$T(x)=2T(\frac{x}{2})+\frac{2}{\log (x)}$$
reach an explicit form:
We already solved it in class. However I can't seem to remember, how was it...
I Wrote it in these stages, but now I am stumped and can't figure it out:
$2(2T(\frac{x}{4})+\frac{2}{\log \frac{x}{2}})+\frac{2}{\log x}$
$2^2T(\frac{x}{2^2})+\frac{2^2}{\log \frac{x}{2^1}}+\frac{2}{\log \frac{x}{2^0}}$
$...=2^kT\frac{x}{2^k}+\sum ...$
I recognized some pattern, but wasn't able to express it using Sigma...
is this progression look valid? like I said the teacher solved it in class, however I am not able to restore it...
$$T(x)=2T(\frac{x}{2})+\frac{2}{\log (x)}$$ $$T(2x)=2T(x)+\frac{2}{\log (2x)}$$ $T(x)=\frac12T(2x)-\frac{1}{\log (2x)}$
$\frac12T(2x)=\frac{1}{2^2}T(2^2x)-\frac{1}{2\log (2^2x)}$
$\frac{1}{2^2}T(2^2x)=\frac{1}{2^3}T(2^3x)-\frac{1}{2^2\log (2^3x)}$
Etc.
$\frac{1}{2^n}T(2^n x)=\frac{1}{2^{n+1}}T(2^{n+1}x)-\frac{1}{2^n\log(2^{n+1}x)}$
Adding the above equations leads to :
$$T(x)=\frac{1}{2^{n+1}}T(2^{n+1}x)-\sum_{k=0}^n \frac{1}{2^k\log(2^{k+1}x)}$$
$$T(x)=\frac{1}{2^{n+1}}T(2^{n+1}x)-\sum_{k=0}^n \frac{1}{2^k\log(x)+2^k(k+1)\log(2)}$$ For $n\to\infty$ we suppose that $\frac{1}{2^{n+1}}T(2^{n+1}x)\to 0$. This will be checked latter. $$T(x)=-\sum_{k=0}^\infty \frac{1}{2^k\log(x)+2^k(k+1)\log(2)}$$ $$T(x)=-\frac{1}{\ln(2)}\sum_{k=0}^\infty \frac{\left(\frac12\right)^k}{\left(\frac{\log(2x)}{\ln(2)}+k\right)}$$
Lerch function $\Phi(z,s,a)$ , with $z=\frac12\quad;\quad s=1 \quad;\quad a=\frac{\ln(2x)}{\ln(2)}\quad$ , Eq.$(1)$ in http://mathworld.wolfram.com/LerchTranscendent.html $$T(x)=-\frac{1}{\ln(2)}\:\Phi\left(\frac12 \:,\: 1 \:,\: \frac{\ln(2x)}{\ln(2)}\right)$$
IN ADDITION :
Limit of $\frac{1}{2^{n+1}}T(2^{n+1}x)$ for $n\to\infty$ :
$T(2^n x)=-\frac{1}{\ln(2)}\:\Phi\left(\frac12 \:,\: 1 \:,\: a)\right)$ with $a=\frac{\ln(2^{n+1}x)}{\ln(2)}=n+1+\frac{\ln(x)}{\ln(2)}$
For $n\to\infty\quad;\quad a\sim n\to\infty\quad;\quad \Phi\left(\frac12 \:,\: 1 \:,\: a)\right)\sim \frac{2}{a}\sim \frac{2}{n}\to 0 \quad ;$
Thus $\frac{1}{2^{n+1}}T(2^{n+1}x)\sim -\frac{2}{\ln(2)2^{n+1}n}\to 0$ as it was supposed.
DIRECT PROVE :
From the definition of the Lerch function $\Phi(z,s,a)=\sum_{k=0}^\infty \frac{z^k}{(k+a)^s}$
$$T(x)=-\frac{1}{\ln(2)}\:\Phi\left(\frac12 \:,\: 1 \:,\: \frac{\ln(2x)}{\ln(2)}\right)=-\frac{1}{\ln(2)}\sum_{k=0}^\infty \frac{(\frac12)^k}{(k+\frac{\ln(2x)}{\ln(2)})}$$
$$T(x)=-\sum_{k=0}^\infty \frac{1}{2^k(k\ln(2)+\ln(2x))}$$ $$T(x/2)=-\sum_{k=0}^\infty \frac{1}{2^k(k\ln(2)+\ln(x))}$$ $$2T(x/2)+\frac{2}{\ln(x)}=-\sum_{k=0}^\infty \frac{1}{2^{k-1}(k\ln(2)+\ln(x))}+\frac{2}{\ln(x)}$$
$$2T(x/2)+\frac{2}{\ln(x)}=-\sum_{k=1}^\infty \frac{1}{2^{k-1}(k\ln(2)+\ln(x))}$$ $$2T(x/2)+\frac{2}{\ln(x)}=-\sum_{k=1}^\infty \frac{1}{2^{k-1}((k-1)\ln(2)+\ln(2x))}$$ Changing the index $(k-1)$ to $k$ : $$2T(x/2)+\frac{2}{\ln(x)}=-\sum_{k=0}^\infty \frac{1}{2^{k}(k\ln(2)+\ln(2x))}=T(x)$$