---
tag: 0Y1MG9R5VN
kind: statement
role: theorem
name: Catalan recurrence
msc: [05A15]
uses: [092DRBFKMG]
sources:
  - url: https://en.wikipedia.org/wiki/Catalan_number
    locator: Properties
---

## Statement

Let $n$ be a natural number, and let $C_m$ be the [[Catalan numbers|092DRBFKMG]].
Then
$$C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}.$$

## Remarks

With the definition of the node [[Catalan numbers|092DRBFKMG]], the statement holds by definition. Its content is in the combinatorial families that satisfy it.
Example: $C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 5 + 2 + 2 + 5 = 14$.
For [[Dyck words|0R9JR0465V]], the recurrence splits a word at the first return to level $0$.

## Explanations

### L1 human

A structure of size $n + 1$ often splits into a left part of size $i$ and a right part of size $n - i$.
Add over all $i$ the number of ways to build the two parts, and you get the next Catalan number.