# Tree with branching factor 1

Something that has been bothering me for a while is the formula for the maximum amount of nodes of a tree with height d and branching factor of b.

$$(b^{d+1}-1)/(b-1)$$

This holds true for all positive integer values of b, including 0, with the exception of b=1.

If b = 1, we would be dividing by 0. Which, well, we all know is not a "legal mathematical move". However, if b = 1, the number of nodes would be equal to the height of the tree + 1.

I'm not sure exactly what my question is. I just feel like it's weird that a tree with branching factor 0 would have 0 nodes, a tree with branching factor 2 would have $$(b^{d+1}-1)/(b-1)$$ nodes , but calculating the number of nodes of a tree with branching factor 1 would be impossible using the same formula.

I don't know what I'm missing. Why isn't there a formula that calculates all nodes in a tree that includes branching factor 1 (or rather, why doesn't this formula include b = 1?)? Or does a tree need a branching factor that is anything else than 1 (but larger than -1?) to qualify as a tree? I'm a bit confused. Help is greatly appreciated.

(Not sure if I got all the facts right here. Please forgive me if I didn't)

The formula you state follows from summing a geometric series: $$1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}.$$ When $b=1$, the series sums to $d+1$, which is also the limit of the expression above as $b\to1$.
As you mention, the formula is only meaningful when $b \neq 1$, though the correct value can still be recovered by taking a limit. This is perhaps the simplest example of a curious phenomenon in combinatorics, that of the "field with one element". Consider the following two quantities:
1. The number of subsets of size $k$ of a set of size $n$. These are counted by binomial coefficients $\binom{n}{k}$.
2. The number of $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field with $q$ elements. These are counted by Gaussian binomial coefficients $\binom{n}{k}_q$, which are rational functions (ratios of two polynomials) in $q$.
The curious thing is that if we substitute $q=1$ in the expression for $\binom{n}{k}_q$, we get back $\binom{n}{k}$ in the limit. (Just as in your case, when $q=1$ the denominator vanishes.) So a set is similar to a vector space over "the field with one element".
More generally, there are other formulas involving "$q$-analogs" (sets replaced with vector spaces over the field with $q$ elements) which degenerate to the correct values when taking the limit $q\to1$. There are some explanations for this phenomenon but it is still somewhat mysterious.