Finding $\sum_{i=0}^{log_2n}(\log n -i)$

Question

Find $\displaystyle\sum_{i=0}^{log_2n}(\log n -i)$

Just to make sure I got it using a change of variable:

$\displaystyle\sum_{i=0}^{log_2n}(\log n -i)= \sum_{k=0}^{\log n}k =\Theta (\log ^2 n)$

Change of variable: $k=\log n -i\ \Rightarrow 0 \le k \le \log n$, and $\log n-k=i$

But I saw another way to solve it:

$\displaystyle\sum_{i=0}^{log_2n}(\log n -i)= \sum_{k=0}^{\log n}\log n - \sum_{k=0}^{\log n} i =\log ^2 n - \log ^2 n =0 ?$ Why it doesn't work when splitting the sum?

Answer 1

Let $P=\lfloor \log_2 n \rfloor$. Then \begin{align*} \sum_{i=0}^{P}(\log n -i) & = \sum_{i=0}^{P}(\log n) -\sum_{i=0}^{P}i\\ & = (\log n)\sum_{i=0}^{P}1-\sum_{i=0}^{P}i\\ & = (\log n)(P+1)-\frac{1}{2}P(P+1)\\ & = (\lfloor \log_2 n \rfloor +1)\left(\log_2n-\frac{\lfloor \log_2 n \rfloor}{2}\right). \end{align*}