# Exponents and power series

I'm a CS major, and I'm learning about trees and time complexity. I want to know if it always holds that b (the branching factor of a tree) to the power of d (the depth of the tree) is the sum of all prior levels plus 1.

More formally: b^d = 1 + b^0 + b^1 . . . b^d-1

And whence comes the "1+" at the beginning? Isn't that what b^0 is for*? I can see a sort of pattern here, but the 1 throws me off. Would calculus help me be a better programmer? I loved my discrete mathematics curriculum -- is analysis related as well?

*i.e., is this why raising to the zeroth power = 1?

-
if $d$ is the depth of the tree, what is $n$? –  Alex Oct 9 '12 at 4:15
Fixed, thanks. I should probably just have stuck with x^n. –  Alex Nye Oct 9 '12 at 4:18

No, it is not true. You are right that the starting 1 should not be there. Then the sum of the geometric series $b^0+b^1+\ldots +b^{n-1}=\frac {b^n-1}{b-1}.$ To see this, think of $b(b^0+b^1+\ldots +b^{n-1})=b^1+b^2+\ldots +b^{n}$, so $(b-1)(b^0+b^1+\ldots +b^{n-1})=b^n-1$
@bismuth: try it with some small numbers: $1+3+9+27=40=\frac {3^4-1}{3-1}$ or $1+5+25+125+625=781=\frac{5^5-1}{5-1}$ –  Ross Millikan Oct 9 '12 at 4:45
@bismuth: I think the reason CS people run afoul of this is that they count by $2$'s so much. Then the denomimator becomes $2-1=1$ and you can ignore it. –  Ross Millikan Oct 9 '12 at 12:58
If $b$ is a constant, then you can prove this using perturbation method as in Graham, Knuth, Patachnik 'Concrete Mathematics'. Denote $S_n=\sum_{k=0}^{n}b^k$. Then, $$S_{n+1}=S_{n} +b^{n+1} = \sum_{k=0}^{n}b^k+b^{n+1}=b\sum_{k=0}^{n}b^k +1=bS_n+1$$ From this it is easy to find that $$S_n=\frac{1-b^{n+1}}{1-b}$$ A special case of this when $|b|<1, n \to \infty$, then $$S=\lim_{n \to \infty}S_n=\frac{1}{1-b}$$