Maximum Nodes in a Binary Tree of Bounded Depth

Count the maximum number of nodes possible at each depth level from 0 to d.

Level $i$ can hold at most $2^i$ nodes; sum a geometric series.

1. 1. Count nodes level by level

   A binary tree can have at most $2^i$ nodes at depth $i$, for $i=0,\dots ,d$.

2. 2. Sum the geometric series

   Summing over all levels gives a geometric series that telescopes to a closed form.

   $$\sum _{i=0}^d{2}^i=2^{d+1}-1$$

Answer: 2^(d+1)-1