the question goes as follows: In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)?
My idea:
Minimal: The root is 1, it has a minimum of 2 children, therefore we have 1 + 2, and then for any level below each node will have the minimum nodes allowed which is d. We get $1 + 2 + 2d + 2d^2 + ... + 2d^{h-1}$ including the leaves, therefore making $1 + \sum_{i=1}^{h-2} 2d^i$ (note that the final index is $h-2$ since we dont count the leaves).
Maximal: Pretty similiar but each level will have $2d$ children, thus making $ 1 + 2d + (2d)^2 + .... + (2d)^{h}$ including the leaves, therefore making $ \sum_{i=0}^{h-1} (2d)^i$.
However, the answer sheet goes $1 + \sum_{i=1}^{h} (2d)^i$ for maximal and $1 + \sum_{i=1}^{h} 2d^{i-1}$ for minimal.
I'll note that the height is defined as the numbers of edges from top-to-bottom, and for example; a tree of root only is of height 0. Tree of root + one set of children is of height 1.
Am I missing something or is there a mistake in our answer-sheet?
Thanks!
