Hallar la suma de $\log(n-1)$ serie

Question

Intento averiguar el tiempo de ejecución de los algoritmos de recursión. El problema es: $$T(n) = 2T(n-1) + \log{n}$$ y estoy utilizando el método del árbol de recurrencia, que me lleva a $$\log(n) + 2\log(n-1) + 4\log(n-2) + 8\log(n-3)+ \cdots + \cdots$$

que es

$$\sum_{i=0}^{n-1} 2^i\log(n-i)$$

Pregunta : ¿Cuál será el valor de esta suma?

Answer 1

Existe un resultado formal $$S_n=\sum_{i=0}^{n-1} 2^i\,\log(n-i)=2^n\, \text{LerchPhi}^{(0,1,0)}(2,0,0)-\text{LerchPhi}^{(0,1,0)}(2,0,-n)$$ donde aparece la derivada de la función trascendente de Lerch respecto a su segundo argumento.

Dicho esto, no es muy útil pero $$S_n \sim 2^{n-1}$$ parece ser una aproximación decente. Cálculo de los logaritmos

$$\left( \begin{array}{ccc} n & \text{approximation} & \text{exact} \\ 10^1 & 6.24909 & 6.23832 \\ 10^2 & 68.6371 & 68.6216 \\ 10^3 & 692.470 & 692.454 \\ 10^4 & 6930.79 & 6930.78 \end{array} \right)$$