Combinatoria base

[giulylanza06]

Un insieme non vuoto A si dice n-buono se A ⊆ {1, 2, . . . , n} e |A| ≤ min A.
Sia $A_n$ il numero di insiemi n-buoni. Dimostrare che per ogni n ≥ 1 vale la formula $a_{n+2}=a_{n+1}+a_n+1$

[Pachisi]

Ho una dimostrazione, ma non e` molto bella.

Se l'insieme $A$ ha un solo elemento, $|A| \le min(A)$. Quindi, abbiamo $n+2$ scelte. Se $|A|=2$, allora $A$ non puo` contenere 1. Allora, abbiamo \( \displaystyle \binom{n+1}{2} \) scelte. Usando lo stesso ragionamento,
\(\displaystyle A_{n+2}= \binom{n+2}{1} +\binom{n+1}{2}+...+\binom{n-i}{j} \). Abbiamo due casi: $n-i=j$ o $n-i-1=j$. Nel primo caso, \(\displaystyle A_{n+1}= \binom{n+1}{1} +\binom{n}{2}+...+\binom{n-i}{j-1} \) e \(\displaystyle A_n= \binom{n}{1} +\binom{n-1}{2}+...+\binom{n-i-1}{j-1} \). Usando l'identita` di Pascal con il fatto che \(\displaystyle \binom{n-i}{j}=\binom{n-i-1}{j-1} \frac{n-i}{j} = \binom{n-i-1}{j}\), abbiamo la tesi.
Nel secondo caso \(\displaystyle A_{n+1}= \binom{n+1}{1} +\binom{n}{2}+...+\binom{n-i-1}{j} \) e \(\displaystyle A_n= \binom{n}{1} +\binom{n-1}{2}+...+\binom{n-i-1}{j-1} \). Usando l'identita` di Pascal abbiamo la tesi.
Spero sia abbastanza chiaro (se servono i calcoli li posto)