Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

up vote 1 down vote accepted

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$

share|improve this answer
lol, okay, I'll think about it till I grok just what it means. Thank you. –  Alex Nye Oct 9 '12 at 4:18
Wow yeah, that's interesting. I can see that applies better and is more 'honest'. Still don't know intuitively precisely why it holds, but thanks. –  Alex Nye Oct 9 '12 at 4:33
@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} $$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.