I am reading the textbook Algorithm Design by Kleignberg and Tardos and I am having trouble on page 216.
$$T(n) \le \sum_{j=0}^{log_2n - 1} \left ( \frac{q}{2}\right )^j cn = cn \sum_{j=0}^{log_2n - 1} \left ( \frac{q}{2}\right )^j where \,\,\, q > 2$$
Let $r = q/2$, and since the above is a geometric series where $r > 1$ we get the formula below:
$$T(n) \le cn \left (\frac{r^{log_2n} -1}{r - 1} \right) \le cn \left( \frac{r^{log_2n}}{r - 1}\right)$$
I simply do not understand how they got the formula using the geometric series formula. In wikipedia, all the formulas for geoemtric sums have $ 1 - r$ in the denominator but this formula has $r - 1$
After a brief search here I came across this formula for finite geometric series where $r > 1$
$$\sum_{i=0}^{n} r^i = \frac{r^{n+1} -1}{r -1}$$
What is the name of the above formula and how come it is so hard to find it online...?
I know it as "geometric series", but if you can't find it next time, just derive it.
$$ \begin{align} \sum\limits_{i=0}^n x^i &= \frac{1}{1 - x} \sum\limits_{i=0}^n (x^i - x^{i+1}) \\ &= \frac{1}{1-x} (1 - x + x - x^2 + x^2 - x^3 + x^3 - \cdots -x^n + x^n - x^{n+1}) \\ &= \frac{1 - x^{n+1}}{1 - x} = \frac{x^{n+1} - 1}{x-1} \end{align} $$