OBM 2024 Problem 2

Uma partição de um conjunto $A$ é uma família de subconjuntos não vazios de $A$, de modo que quaisquer dois subconjuntos distintos da família são disjuntos e a união de todos os subconjuntos é igual a $A$. Dizemos que uma partição de um conjunto de inteiros $B$ é afastada se cada subconjunto que compõe a partição não contém inteiros consecutivos. Prove que, para todo inteiro positivo $n$, a quantidade de partições do conjunto $\{1, 2, \ldots, n\}$ é igual a quantidade de partições afastadas do conjunto $\{1, 2, \ldots, n, n+1\}$.

Por exemplo, $\big\{\{1,3\},\{2\}\big\}$ é uma partição afastada do conjunto $\{1,2,3\}$. Por outro lado, $\big\{\{1,2\},\{3\}\big\}$ é uma partição do mesmo conjunto, mas que não é afastada pois $\{1,2\}$ contém inteiros consecutivos.