Awesome q2a theme
+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.

in Mathematical Logic by (29 points) | 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}$

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,106 questions
3,157 answers
14,595 comments
95,958 users