1
$\begingroup$

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?

  • 0
    Fixed, thanks. I should probably just have stuck with x^n.2012-10-09

2 Answers 2

1

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$

  • 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.2012-10-09
1

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} $