Como no está claro dónde radica su problema, comenzaré desde el principio.
La inducción matemática funciona como el juego de los susurros chinos (en el caso ideal, es decir, toda comunicación es sin pérdida) o dominó (perfectamente configurado) : comienzas en algún lugar y demuestras que tu próximo paso no rompe nada, suponiendo que nada se haya roto hasta luego.
Más formalmente, cada prueba de inducción consta de tres elementos básicos:
- Ancla de inducción , también caso base : muestra para casos pequeños¹ que el reclamo es válido.
- Hipótesis de inducción : supone que la reclamación se cumple para un determinado subconjunto del conjunto sobre el que desea probar algo.
- Paso inductivo : Usando la hipótesis, demuestras que el reclamo es válido para más elementos.
Por supuesto, el paso debe ajustarse de modo que cubra todo el conjunto base (en el límite).
Nota importante: las personas que confían en sus habilidades de inducción a menudo pasan por alto el ancla y dejan la hipótesis implícita. Si bien esto está bien cuando presenta su trabajo a una audiencia experta (por ejemplo, un documento), esto no se recomienda al hacer pruebas usted mismo, especialmente como principiante. Escribe todo.
Considere un ejemplo simple sobre ; queremos mostrar que ∑ n i = 0 i = n ( n + 1 )( N , ≤ ) vale para todos losn∈N.∑nortei = 0i = n ( n + 1 )2n ∈ N
- Ancla : Para , ∑ n i = 0 i = 0 = n ( n + 1 )n = 0 claramente se sostiene.∑nortei = 0i = 0 = n ( n + 1 )2
- Hipótesis : suponga que es válido para un arbitraria, pero fixed²n∈N.∑ki = 0i = k ( k + 1 )2n ∈ N
Paso : para , calcule la suma:n + 1
∑i = 0n + 1i = ( n + 1 ) + ∑i = 0nortei =IHn+1+n(n+1)2=(n+2)(n+1)2
Entonces la identidad es válida para . (Observamos que solo necesitábamos una pequeña parte de la hipótesis, a saber, para k = n . Eso sucede a menudo).n + 1k = n
El principio inductivo ahora nos asegura que la afirmación es válida: lo hemos mostrado directamente para . El paso dice que si se mantiene para 0 , también se mantiene para 1 ; si es válido para 1 , también es válido para 2 ; y así.0 00 0112
Echemos un vistazo a otro ejemplo, esta vez en . La afirmación que queremos probar es: para cada subconjunto finito A de N , el tamaño del conjunto de potencia 2 A de A es 2 | A | ³. Llevamos a cabo nuestra inducción sobre ( N , ≤ ) , de nuevo, es decir, sobre el tamaño de los subconjuntos A .( 2norte, ⊆ )UNAnorte2UNAUNA2El | A |( N , ≤ )UNA
- Ancla: Considere el (solo) conjunto de tamaño , el conjunto vacío. Claramente, 2 ∅ = { ∅ } y por lo tanto | 2 ∅ | = 1 = 2 0 como se reivindica.0 02∅= { ∅ }El | 2∅El | =1= 20 0
- Hipótesis: suponga que para todos los conjuntos con | A | ≤ n con algo arbitrario, pero fijo n ∈ N , tenemos | 2 A | = 2 | A | .A ⊆ NEl | A | ≤nn ∈ NEl | 2UNAEl | = 2El | A |
Paso: Sea arbitrario⁴ de tamaño n + 1 , y sea b ∈ B arbitrario (tal b existe como n + 1 > 0 ). Ahora la hipótesis se aplica a B ∖ { b } y por lo tanto | 2 B ∖ { b } | = 2 n . Ya queB ⊆ Nn + 1b ∈ Bsin + 1 > 0B ∖ { b }El | 2B ∖ { b }El | = 2norte
,2si= 2B ∖ { b }∪ { A ∪ { b } ∣ A ∈ 2B ∖ { b }}
de hecho tenemos que como se reivindica.El | 2siEl | =2⋅ | 2B ∖ { b }El | =2⋅ 2norte= 2n + 1
Una vez más, por inducción se demuestra el reclamo.
Ahora, para su problema puede usar un truco común: fortalecer la declaración . Si formula su reclamo como "el autómata acepta todas las palabras con un número impar de unos", obtendrá una hipótesis de inducción como "entre todas las palabras de longitud , el autómata acepta exactamente las que tienen un número impar". Esto no lo llevará a ningún lado ya que no sabemos nada acerca de cuántos están contenidos en qué parte de una palabra dada (aceptada); La hipótesis no se aplica a lo que haya cortado de su palabra seleccionada arbitrariamente.norte
Por lo tanto, desea formular una afirmación más fuerte: "El autómata está en estado si y solo si la parte consumida de la entrada contiene un número impar de unos", y muestre este. Tenga en cuenta que implica el reclamo anterior.si
- Ancla : Después de procesar la única cadena de longitud cero, , el autómata está claramente en el estado A como se reivindica.εUNA
- Hipótesis : suponga que la reclamación se cumple para fragmentos de entrada de longitud hasta que se elige de forma arbitraria, pero fija.norte
- Paso : considere una palabra arbitraria . Hay dos casos.
w ∈ { 0 , 1 }n + 1
- contiene un número par de unos. Hay dos casos para el último símbolo.
w
- : en este caso, w ′ = w 1 ... w n - 1 contiene un número par de unos. Por hipótesis de inducción, el autómata se encuentra en el estado A después de consumir w ' . El consumo de w n = 0 hace que el autómata permanezca en el estado A , como se afirma.wnorte= 0w′= w1... wn - 1UNAw′wnorte= 0UNA
- wnorte= 1w′= w1... wn - 1siw′wnorte= 1UNA
- w
El principio de inducción implica que la afirmación es válida.
- Realizas la inducción a lo largo de un orden parcial; el ancla necesita cubrir todos los elementos mínimos y, a veces, más (dependiendo de la declaración).
- norte
- 2UNAUNA0 , 1
- siUNA