Can someone please help me follow the explanation of this answer
Apologize in advance if this is not the right place for it.
my questions are:
why "N = 1 + 2 + 2^2 + 2^3 + ... + 2^h = (2^{h+1} - 1) / (2 - 1) = 2^{h+1} - 1"? I am able to visualize where 1, 2, 2^2 comes from as explain, but can't manipulate it into (2^{h+1} - 1) / (2 - 1)
As explained, L = 2^h, "Therefore, by substitution, we get "N = 2*L - 1". Maybe I can't understand the first step, I got stuck here as well. L has no place to go to in the equations we have so far ?
Thank you in advance.
The sum $1+2+2^2+2^3+.....+2^h$ can be expressed as $\Sigma_{i=0}^{h}m^{i}$ ,where $m$ is the $m$-ary of the tree , and $i$ is the $power(height)$.
$\Sigma_{i=0}^{h}m^{i}$=$\frac{m^{h+1}-1}{m-1}$
$Proof:$
$\Sigma_{i=0}^{h}m^{i} = m^0+m^1+m^2+m^3+.....+m^h$
Multiply the sum by -m :
$-m\Sigma_{i=0}^{h}m^{i}=-m-m^2-m^3-m^4-.....-m^{h+1}$
Add these two u get
$\Sigma_{i=0}^{h}m^{i} - m\Sigma_{i=0}^{h}m^{i}$ = $m^0-m^{h+1}$ ,which evaluates to :
$(1-m)\Sigma_{i=0}^{h}m^{i} = 1 - m^{h+1} $
$\Sigma_{i=0}^{h}m^{i} = \frac{1 - m^{h+1}}{1-m} *\frac{-1}{-1} = \frac{m^{h+1}-1}{m-1}$ as desired.
This is geometric series formula with parameters for this sum:
$a=1, r=m, k=h$.