Reproduzco aquí la prueba que está sacada del libro "Learning from Data"
$B(N, k)$ es el número máximo de dicotomías en $N$ puntos tales que ningún subconjunto de tamaño $k$ de la $N$ puntos pueden ser destrozados por estas dicotomías.
El lema de Sauer: $B(N,k) \leq \sum_{i=0}^{k-1}{N\choose i}$
Prueba: La afirmación es verdadera siempre que $k = 1$ o $N = 1$ por la inspección. La prueba es por inducción sobre $N$ . Supongamos que la afirmación es cierta para todos los $N \leq N_o$ y para todos $k$ . Dado que la afirmación ya es verdadera cuando $k = 1$ (para todos los valores de $N$ ) por la condición inicial, sólo tenemos que preocuparnos de $k \geq 2$ . Por (probado en el libro), $B(N_0 + 1, k) \leq B(N_0, k) + B(N_0, k-1)$ y aplicando la hipótesis de inducción sobre cada término del lado derecho, obtenemos el resultado.
Mi preocupación Por lo que veo esta prueba sólo demuestra que si $B(N, k)$ implica $B(N+1, k)$ . No puedo ver cómo se muestra $B(N, k)$ implica $B(N, k+1)$ . Este problema surge porque el $k$ en $B(N_0 + 1, k)$ y $B(N_0, k)$ son los mismos, así que creo que tengo que probar la otra inducción también. ¿Por qué el autor es capaz de demostrarlo de esta manera?
