+1 vote
24 views

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.

| 24 views
+1
I think this got resolved now, didn’t it?

:)
+1
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$
+1
$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}$