Finding an asymptotic bound on a sum This sum came up in the context of analyzing an algorithm: $\sum_{k = 0}^{\lg n} 2^k \lg(\lg(n) - k)$. I tried bounding it with $\sum_{k = 0}^{\lg n} 2^k \lg\left(\lg\left(\frac{n}{2^k}\right)\right)$, but I can't go any further than this. How to asymptotically bound this sum? Thanks!
Edit: I made some progress, and I found an upper bound but I don't think that it's a tight bound:
$$\sum_{k = 0}^{\lg n} 2^k \lg\left(\lg\left(\frac{n}{2^k}\right)\right) \leq \sum_{k = 0}^{\lg n} 2^{\lg n} \lg\left(\lg\left(\frac{n}{2^0}\right)\right) = \sum_{k = 0}^{\lg n} n \lg(\lg(n)) = \lg(n) n \lg(\lg(n)),$$ meaning that $$\sum_{k = 0}^{\lg n} 2^k \lg\left(\lg\left(\frac{n}{2^k}\right)\right) = O(n \cdot \lg(n) \cdot \lg(\lg(n))).$$
 A: If we redefine a bit the problem, we can find a reasonable asymptotic of the sum.
Let's call $N=\ln n$ and consider the sum
$$S(N)=\sum_{k = 0}^{N-1} 2^k \ln(N - k)$$
(as @Robert Israel mentioned, otherwise, at $k=N$ we get an infinite term).
Using the Frullani' integral $\displaystyle \ln (N-k)=\int_0^\infty\frac{e^{-t}-e^{-t(N-k)}}{t}dt$ , and our sum becomes
$$S(N)=\sum_{k=0}^{N-1}2^k\int_0^\infty\frac{e^{-t}-e^{-t(N-k)}}{t}dt=\int_0^\infty\frac{dt}{t}\left(e^{-t}\sum_{k=0}^{N-1}2^k-e^{-Nt}\sum_{k=0}^{N-1}2^ke^{tk}\right)$$
$$=\int_0^\infty\frac{dt}{t}\left(e^{-t}\frac{2^N-1}{2-1}-e^{-Nt}\frac{2^Ne^{tN}-1}{2e^t-1}\right)$$
$$=2^N\int_0^\infty\frac{e^{-t}}{t}\left(1-\frac{1}{2-e^{-t}}\right)dt-\int_0^\infty\left(\frac{e^{-t}}{t}-\frac{e^{-Nt}}{t(2e^t-1)}\right)dt=S_1-S_2$$
As $2e^t-1>1$ for $t\in[0;\infty)$, we can get the following estimation of the second term:
$$S_2=\int_0^\infty\left(\frac{e^{-t}}{t}-\frac{e^{-Nt}}{t(2e^t-1)}\right)dt<\int_0^\infty\left(\frac{e^{-t}}{t}-\frac{e^{-Nt}}{t}\right)dt=\ln N\tag{1}$$
But the first term is exponentially big at $N\to\infty\,:$
$$S_1=2^N\int_0^\infty\frac{e^{-t}}{t}\left(1-\frac{1}{2-e^{-t}}\right)dt=2^N\int_0^\infty\frac{1-e^{-t}}{t}\frac{dt}{2e^t-1}=2^N\cdot J\tag{2}$$
where $\displaystyle J=\int_0^\infty\frac{1-e^{-t}}{t}\frac{1}{2e^t-1}dt=0.507834...$
Therefore, $\displaystyle \boxed{\,\,S(N)=2^NJ-O(\ln N)<2^NJ\,\,}$ or, using your notation,
$$\sum_{k = 0}^{\ln n-1} 2^k \ln(\ln n - k)=2^{\ln n}J-O\big(\ln(\ln n)\big)\to 2^{\ln n}J-\ln\big(\ln n\big)\,\text{at}\,n\to\infty$$
An important observation by @Gary:
If your notation means $N=\log_2n\,$, then we get, using $\log_2(N-k)=\frac{\ln(N-k)}{\ln2}\,$ (and $N=\log_2n$)
$$\sum_{k = 0}^{\log_2n-1} 2^k \log_2(\log_2n - k)=n\frac {J}{\ln2}-O\big(\log_2(\log_2n)\big)\to n\,\frac{J}{\ln2}-\log_2(\log_2n)\,\text{at}\,n\to\infty$$

Numeric check with WolframAlpha
$$N=10\quad S(10)=517.534...\,;\quad \text{approx:} \, S_1(10)=2^{10}J=1024\cdot 0.50783...=520.022...$$
At $N\to\infty\,\,S_2(N)\to\ln N$ quickly (please, see below); therefore
$$S(10)=S_1(10)-S_2(10)\approx2^{10}J-\ln(10)=520.022-2.3025...=517.719...$$

Evaluation of the next asymptotic terms
$$S_2=\int_0^\infty\left(\frac{e^{-t}}{t}-\frac{e^{-Nt}}{t(2e^t-1)}\right)dt=\int_0^\infty\frac{e^{-t}-e^{-Nt}}{t}dt+2\int_0^\infty\frac{e^{-Nt}}{t}\frac{1-e^{-t}}{2-e^{-t}}dt$$
$$=\ln N+2\int_0^\infty\frac{e^{-x}}{x}\frac{1-e^{-x/N}}{2-e^{-x/N}}dx$$
Decomposing $e^{-x/N}$ into the series and integrating term by term,
$$S_2=\ln N+\frac2N\int_0^\infty e^{-x}\frac{1-\frac{x}{2N}+...}{1+\frac{x}{N}-...}dx=\ln N+\frac2N-\frac{3}{N^2}+O\Big(\frac{1}{N^3}\Big)$$
and, therefore,
$$\boxed{\,\,S(N)=S_1-S_2=2^NJ-\ln N-\frac2N+\frac{3}{N^2}+O\Big(\frac{1}{N^3}\Big)\,\,}$$
