Hola.
A mi también me resulta confusa porque en el apunte define
[texx]\sum_{}^{n} := \left\{ xp \mid x \in \sum_{}, p \in \sum_{}^{n-1} \right\}[/texx]
donde xp es la yuxtaposición del carácter x con la cadena p.
Veamos, a traves del siguiente ejemplo que [texx]\sum_{}^{n}[/texx] está constituido por todas las cadenas sobre [texx]\sum_{}[/texx] con n caracteres.
Luego muestra un ejemplo donde define un alfabeto [texx]\sum_{} = \left\{ a,b \right\}[/texx]
Y define [texx]\sum_{}^{2} \sum_{}^{3} ... [/texx]
Para mi con la definición: [texx]\sum_{}^{n} := \left\{ xp \mid x \in \sum_{}, p \in \sum_{}^{n-1} \right\}[/texx] es obvio que tienen n carácteres.
No sé, no lo entiendo muy bien, un compañero lo hizo así:
[texx]P(n): \sum_{}^{n} = \left\{ a_1,...,a_n \mid a_i \in \sum_{}, \forall i=1,...,n \right\}
\\
P(1): \sum_{}^{1}= \left\{a_1 \mid a_1 \in \sum_{} \right\} = \sum_{}[/texx]
Supongo que es cierta para [texx]P(n)[/texx] pruebo para [texx]P(n+1)[/texx]
Tesis: [texx]P(n+1): \sum_{}^{n+1} = \left\{a_1,a_2,...,a_n,a_{n+1} \mid a_i \in \sum_{}, \forall i = 1,...,n+1 \right\}[/texx]
Prueba:
[texx]\sum_{}^{n+1} \stackrel{Def.}{=} \left\{ xp \mid x \in \sum_{} , p \in \sum_{}^{n} \right\} \stackrel{HIP.}{=} [/texx]
[texx]
p \in \sum_{}^{n} = \left\{ a_1, ..., a_n \right\}[/texx]
donde [texx]p = a_1,...,a_n[/texx], [texx]a_i \in \sum_{}[/texx]
[texx]
= \left\{ xp \mid x \in \sum_{} , p = a_1, ..., a_n ; a_i \in \sum_{} \forall i = 1,..., n \right\} = \\
= \left\{ x a_1 a_2 ... a_n \mid x,a_i \in \sum_{} \forall i = 1,...,n \right\}
\\[/texx]
[texx]
\therefore P(n+1)[/texx] es verdadero.
[texx]
\therefore P(n)[/texx] es verdadero [texx]\forall n \in \mathbb{N}[/texx]
Pero esta demostración no me cerraba bien, ahora la voy a volver a pensar porque estaba haciendo otros ejercicios y te comento lo que pienso.
Saludos.