I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09). Although you guys don't have to go and look at the video, I feel that the summation he does is wrong so I will attach the screenshot of the slide.
Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?
algorithms;data structures;algorithm analysis;mathematical analysis;discrete mathematics
If you have a series of numbers that are consecutive power of 2s, like $1+2+4+8+16+\cdots+2^k$ you get as sum $2^{k+1}-1$. You can either see this by looking at the formula for the geometric series or you can prove this by induction.Then the statement of the lectures follows, since here $k=\lfloor \log (n-1) \rfloor$. Therefore the sum is less than $2n$.