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
2  
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
add comment

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
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
1  
@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
add comment

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
add comment

Your Answer

 
discard

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.