Lo que se busca aquí se conoce como inducción estructural . Se empieza con las cadenas mencionadas en el caso básico de la definición recursiva y se comprueba que tienen la propiedad en cuestión. Aquí sólo hay una, ba y lo hace: tiene el mismo número de a y b 's, y termina en a .
A continuación, demuestra que las construcciones permitidas por la definición recursiva preservan la propiedad en cuestión.
-
Si s tiene el mismo número de a y b y termina en a ¿es esto también cierto para ab-s ? Sí: si s tiene, digamos, $n$ a y $n$ b 's, entonces ab-s tiene $n+1$ de cada letra, y la última letra de ab-s es evidentemente la última letra de s que por hipótesis es a .
-
Si s y t ambos tienen el mismo número de a y b y terminan en a ¿es esto también cierto para s-t ? De nuevo, es fácil demostrar que la respuesta es sí .
Ahora tienes derecho a concluir que toda cadena de balbuceos tiene el mismo número de a y b y termina en a . Si necesita un poco más de convencimiento, suponga que existiera una cadena de balbuceos que no tuviera esa propiedad. Entonces habría una más corta sin la propiedad; llámala u . Claramente u no es la cadena de balbuceo inicial ba Así que, o bien u es ab-s para una cadena de balbuceos s o u es s-t para algunas cuerdas de balbuceo s y t . Pero ambos casos son imposibles. Por ejemplo, si u fueron ab-s entonces s sería una cadena de balbuceos más corta que u por lo que tendría la propiedad, y el argumento del primer punto anterior mostraría que u debe tener la propiedad también. El segundo punto se ocupa de la otra posibilidad.
En este problema también se podría utilizar la inducción ordinaria sobre la longitud de la cadena de balbuceos, pero es una buena idea familiarizarse con la técnica más general.
