Node counts in recombining and exploding trees

Question

A binomial tree has $N$ time steps. How many nodes does it have in total if it recombines (up-then-down equals down-then-up), and how many if it does not?

Short answer

Recombining: $\frac{(N+1)(N+2)}{2}$ ; non-recombining: $2^{N+1} - 1$ . In the recombining tree step $k$ has $k+1$ nodes, giving $1 + 2 + \dots + (N+1)$ . Without recombination the nodes double each step, giving $1 + 2 + \dots + 2^N$ . That quadratic-versus-exponential growth is why recombining trees are used in practice.

Adapted from Crack, Heard on the Street, Q2.57, p.32; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

The Binomial Model
Counting and Combinatorics
The One-Period Binomial Model: Replication, Delta Hedging, and Risk-Neutral Pricing

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free