Daau Sum

## The Problem

Show that:

(1)
\begin{align} db+(d-1)b^2 + \dots + b^d \in \mathrm{O}(b^d) \end{align}

### Solution 1

(2)
\begin{eqnarray} db+(d-1)b^2 + \dots + b^d &=& \underbrace{ b + b^2 + \dots + b^{d-1} + b^d }_{\dfrac{b(b^d - 1)}{b-1} } \\ &+& \underbrace{ b + b^2 + \dots + b^{d-1} }_{ \dfrac{b(b^{d-1} - 1)}{b-1} } \\ &\vdots& \\ &+& \underbrace{ b }_{ \dfrac{b(b^1 - 1)}{b-1} } \\ &=& \dfrac{b (b^d + b^{d-1} + \dots + b^1 - d)}{b - 1} \in \mathrm{O}(b^d + b^{d-1} + \dots + b^1 - d) \\ &=& \mathrm{O}( \dfrac{b(b^d - 1)}{b-1} - d) \\ &=& \mathrm{O}(b^d - d) \\ &=& \mathrm{O}(b^d) \end{eqnarray}

Assuming that b > 1.

### Solution 2

Factor the original formula by b^d and then you have something that looks like (1 + 2/b + … + d/b^(d-1)).
This is where we hаve to take b>1 too :) and it is bounded by the Taylor series (1-1/b)^-2 which makes the calculation collapse to O(b^d).
This is probably the shortest proof.

page revision: 3, last edited: 02 Sep 2010 19:53