0
$\begingroup$

I have the following question:

Show that $\displaystyle\sum_{k=1}^n a_k=na_n-\displaystyle\sum_{k=1}^{n-1} k(a_{k+1}-a_k)$

then evaluate $\displaystyle\sum_{k=1}^n \lfloor \log_2(k) \rfloor=(n+1)\lfloor \log_2(n) \rfloor -2^{\lfloor \log_2(n) \rfloor+1}+2$

I can show the first part pretty easily by induction but I have no idea where to go with the second part. I use the expansion and get:

$\displaystyle\sum_{k=1}^n \lfloor \log_2(k) \rfloor=n\lfloor \log_2(n) \rfloor-\displaystyle\sum_{k=1}^{n-1} k(\lfloor \log_2(k+1) \rfloor-\lfloor \log_2(k) \rfloor)$ but I have no idea where to go from here.

Thanks for any help.

3 Answers 3

3

You (now) have

$\sum_{k=1}^n\lfloor\lg n\rfloor=n\lfloor\lg k\rfloor-\sum_{k=1}^{n-1}k\Big(\lfloor\lg(k+1)\rfloor-\lfloor\lg k\rfloor\Big)\;,$

where I use $\lg$ for $\log_2$. Now notice that when $2^m\le k, $\lg k=\lg(k+1)$, and the corresponding term in the last summation is $0$. You get a non-zero term only when $k=2^m-1$ for some $m$, and in that case the term that you get is $k$. Thus,

$\sum_{k=1}^{n-1}k\Big(\lfloor\lg(k+1)\rfloor-\lfloor\lg k\rfloor\Big)=\sum_{1\le m\le\lg n}\left(2^m-1\right)=\sum_{m=1}^{\lfloor\lg n\rfloor}\left(2^m-1\right)\;.$

From here you should be able to finish it; it’s just a little algebra now.

1

If you explicitly write out the first several terms in your second summation $\sum_{k=1}^{n-1}k(\lfloor \log_2(k+1)\rfloor - \lfloor \log_2(k)\rfloor)$, you will find out all terms are zero except when $k=2^s-1$ where $s$ is an integer less than $\lfloor \log_2(n)\rfloor$. Then it becomes a geometrical series and it's easy to sum it up and get a nice result.

0

You are asked to show first

$ \displaystyle\sum_{k=1}^n a_k=na_n-\displaystyle\sum_{k=1}^{n-1} k(a_{k+1}-a_k) \,.$

To prove this you need to use summation by parts

$ \sum_{k=m}^n f_k(g_{k+1}-g_k) = \left[f_{n+1}g_{n+1} - f_m g_m\right] - \sum_{k=m}^n g_{k+1}(f_{k+1}- f_k)\,. $

In your case, let $f_k=a_k$ and $g_k=k \Rightarrow g_{k+1}-g_k=1$.

  • 0
    I'm pretty sure that I can just use induction to show this?2012-09-29