Cn = Σ Ci·C(n-1-i).
La recurrencia de Catalan es la propiedad fundamental que define a los números de Catalan, una sucesión de números naturales que aparece muy seguido en la combinatoria. Aunque la expresión cerrada $C_n = \frac{1}{n+1}\binom{2n}{n}$ es útil para calcular, la relación de recurrencia $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ suele ser el método principal para identificar estructuras de Catalan en problemas de olimpiada. Esta relación describe un proceso de descomposición recursiva, donde una estructura de tamaño $n$ se divide en dos estructuras de Catalan más pequeñas e independientes de tamaños $i$ y $n-1-i$, generalmente separadas por un elemento "raíz" específico o una condición de "primer regreso".
Esta recurrencia es esencial porque representa la auto-similitud estructural que encuentras en muchos objetos geométricos y algebraicos. Por ejemplo, al contar de cuántas formas puedes triangular un polígono convexo de $n+2$ vértices, puedes fijar un lado base específico. Este lado debe pertenecer a exactamente un triángulo, cuyo tercer vértice divide al polígono restante en dos polígonos más pequeños. Si sumas sobre todas las posiciones posibles de este tercer vértice, obtienes la recurrencia de Catalan. De la misma forma, al contar árboles binarios, el nodo raíz divide al árbol en un subárbol izquierdo y uno derecho; si el número