# Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$?

I have an exercise problem and don't know why its answer is like this. $$\sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n).$$

Regarding this equation, I think it would be, $$\sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(\lg n \cdot 2^{\lg n}) = \Theta(\lg n \cdot n),$$ with the proof, $$\sum_{i=1}^{g(n)}f(i) \le \sum_{i=1}^{g(n)}f(g(n)) = g(n)\cdot f(g(n)).$$

My thought with this question, $$f(n) = 2^{i-1}$$ and $$g(n)= \lg n$$. Then result would be $$\lg n \cdot 2^{\lg n - 1}$$.

Can anyone point out where I made a mistake? (I am not asking grading mine, but tell me where I mis-think)

• This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly. – dkaeae Feb 26 '19 at 16:56
• @dkaeae edited my question – jayko03 Feb 26 '19 at 17:19
• @jayko03 Unfortunately, changing the question to 'find my mistake' does not solve the problems that exist with questions requesting to 'check a solution'. You can improve your question by specifically explain where and why you think you have made a mistake. – Discrete lizard Feb 26 '19 at 18:36

Your argument shows that $$\sum_{i=1}^{\lg n} 2^{i-1} = O(n\lg n).$$ It doesn't show the matching lower bound, which is actually false.