Self-doubt sum series and logaritms.

Question

These are what i ended up with while solving a couple of recurrance relation can anyone help to solve further.

 

 

1. $(n^2) log(n/2^{k-1}) + 2(n^2) log(n/2^{k-2}) + 3(n^2) log(n/2^{k-3}) + ...+ (n^2) log(n)$

 

       $2. lg n + lg (n / 2) + lg (n / 4) + ... + lg (n / 2^{lg n})$

 

Note: Assume base 2 for log terms.

Comments

I think this got resolved now, didn’t it?

:)

---

yes sir but however as i was solving second one i found that…

$lgn + lg(n/2) + lg(n/2^2) +...+ lg(n/2^{logn})$

 

evalutes to

 

$lgn + lgn - 1 + (lgn -2) +...+ lgn- lgn$

above was easily understandable but then it was suggested to write in reverse and the last step was like

 

$0 + 1 + 2 +.. + lgn$                                                           

  which is what i didn’t understood.

 

after reaching 1 we’ll use the guassian sum formula or Ramanujan formula and

 $lgn (lgn + 1)/2$

---

$logn+log(\frac{n}{2})+log(\frac{n}{2^2})+...+log(\frac{n}{2^{logn}})$

$logn + logn – 1 + logn – 2 + … logn – logn$

Separate the logn from the negative terms

$(logn + logn + … logn) – (1 + 2 + … +logn)$

$(logn\times(logn + 1)) – \frac{logn(logn + 1)}{2}$ (You can see we have logn + 1 total terms because they go from $\frac{n}{2^0}$ to $\frac{n}{2^{logn}}$)

$=\frac{logn(logn + 1)}{2}$