Inducción estructural y definiciones recursivas

La recursión es definir objetos en términos de ellos mismos, podemos utilizar la recursión para definir sucesiones, funciones y conjuntos. Cuando definimos conjuntos recursivamente, especificamos algunos elementos iniciales en un paso base y proporcionamos, en el paso recursivo, una regla para construir nuevos elementos a partir de los que ya tenemos. Para demostrar resultados sobre conjuntos definidos recursivamente empleamos un método llamado inducción estructural. ​

Funciones definidas recursivamente

Las definiciones recursivas de conjuntos, poseen un paso base y un paso recursivo. Se usan dos pasos para definir una función donde su dominio es el conjunto de enteros no negativos:

• Paso base: Se especifica el valor de la función en cero.
• Paso recursivo: Se da una regla que sirva para obtener su valor en un entero a partir de sus valores en enteros menores.

Esta definición se llama definición inductiva o recursiva.

Definición

"El conjunto Σ* de cadenas sobre el alfabeto Σ se puede definir recursivamente por: Paso base: λ ∈ Σ*, donde λ es la cadena vacía, aquella que no contiene símbolos. Paso recursivo: Si w ∈ Σ* y x ∈ Σ*, entonces wx ∈ Σ*."

Ejemplos

• Ejemplo 1

Supongamos que f se define recursivamente como:

       f(0) = 3.
       f(n+1) = 2*f(n)+3.

Entonces para obtener f(1), f(2), f(3), f(4)... tendremos que aplicar la definición recursiva por lo tanto:

       f(0) = 3. Por definición
       f(1) = 2*f(0)+3 = 2*3+3 = 9.
       f(2) = 2*f(1)+3 = 2*9+3 = 21.
       f(3) = 2*f(2)+3 = 2*21+3 = 45.
       f(4) = 2*f(3)+3 = 2*45+3 = 93.

• Ejemplo 2

Dar una definición recursiva de la función factorial F(n) = n!

Se puede definir la función factorial especificando el valor inicial de la función, F(0) = 1, después se da una regla para hallar F(n+1) a partir de F(n). Como sabemos por la definición de factorial (n+1)! se calcula multiplicando n!*(n+1), por lo tanto la regla que nos queda sería tal que: F(n+1) = (n+1)*F(n)

• Ejemplo 3

Obtener los números de Fibonacci $f_{2}\,$,$f_{3}\,$,$f_{4}\,$,$f_{5}\,$ y $f_{6}\,$

Por definición de números de Fibonacci se sabe que $f_{0}\,$=0 y $f_{1}\,$=1, por lo tanto:

       $f_{2}\,$ = $f_{1}\,$+$f_{0}\,$ = 1+0 = 1
       $f_{3}\,$ = $f_{2}\,$+$f_{1}\,$ = 1+1 = 2
       $f_{4}\,$ = $f_{3}\,$+$f_{2}\,$ = 2+1 = 3
       $f_{5}\,$ = $f_{4}\,$+$f_{3}\,$ = 3+2 = 5
       $f_{6}\,$ = $f_{5}\,$+$f_{4}\,$ = 5+3 = 8

Teorema de Lamé

Este teorema dice que siendo a y b dos números enteros positivos con a ≥ b. Entonces, el número de divisiones realizadas por el algoritmo de Euclides para calcular mcd(a,b) es menor o igual que cinco veces el número de cifras decimales de b.

Para n>=1, dejemos que u y v sean enteros con u>v>0 de manera que el algoritmo euclídeo aplicado a u y v requiera exactamente n pasos de división y de manera que u sea lo más pequeño posible satisfaciendo estas condiciones. Entonces u=F(n+2) y v=F(n+1), donde F_k es un número de Fibonacci.

Además, el número de pasos en el algoritmo euclidiano nunca excede 5 veces el número de dígitos del número más pequeño. De hecho, el 5 puede reducirse aún más a ln(10)/ln(phi) aproximadamente 4,785, donde phi es la proporción de oro.

Ejemplo

• Cuando se aplica el algoritmo de Euclides para encontrar el mcd(a,b) para a ≥ b, la secuencia de igualdades que se obtiene es (para a=r₀ y b=r₁):

       r0 = r1c1 + r2         0 ≤ r2 < r1
       r1 = r2c2 + r3         0 ≤ r3 < r2
       .
       .
       .
       rn-2 = rn-1cn-1 + rn    0 ≤ rn < rn-1
       rn-1 = rncn + rn

Hemos hecho n divisiones para encontrar r_n = mcd(a,b). Observa que los cocientes c₁, c₂, ..., c_n-1 son al menos 1. Además, c_n ≥ 2, puesto que r_n < r_n-1. Esto implica que

     rn ≥ 1 = f2,
     rn-1 ≥ 2rn = 2f2 = f3,
     .
     .
     .
     r2 ≥ r3+r4 ≥ fn-1+fn-2 = fn,
     b = r1 ≥ r2+r3 ≥ fn+fn-1 = fn+1.

Conjuntos y estructuras definidas recursivamente

Las definiciones recursivas de conjuntos tienen dos partes, un paso base y un paso recursivo.

En el paso base se especifica una colección inicial de elementos.

En el paso recursivo se proporcionan reglas para la formación de nuevos elementos del conjunto a partir de los que ya se conocen.

"Regla de exclusión: El conjunto no contiene nada más que aquello especificado por la regla base o que se obtiene recursivamente por aplicación de la regla recursiva".

Las definiciones recursivas pueden incluir también una regla de exclusión que especifica que un conjunto definido recursivamente no contiene más elementos que aquellos especificados en el paso base o generados por la aplicación del paso recursivo.

Definiciones

1. El conjunto Σ* de cadenas sobre el alfabeto Σ se puede definir recursivamente por:
   1. Paso base: λ ∈ Σ*, donde λ es la cadena vacía, aquella que no contiene símbolos.
   2. Paso recursivo: Si w ∈ Σ* y x ∈ Σ*, entonces wx ∈ Σ*.

Ejemplos

• Considera el subconjunto S de los enteros definidos por

1. Paso base: 3 ∈ S.
2. Paso recursivo: Si x ∈ S e y ∈ S, entonces x + y ∈ S.

Los nuevos elementos de S se forman partiendo del paso base, 3, aplicando el paso recursivo una vez 3+3 = 6, dos veces 3+6 = 6+3 = 9 y 6+6 = 12 y así sucesivamente.

Podemos definir Σ*, el conjunto de cadenas en Σ, recursivamente, como se muestra en la definición 1.

Inducción estructural

"Una definición inductiva de un conjunto A consiste en una colección de esquemas de reglas.Cada esquema es de uno de los dos tipos:básico e inductivo.

• Los esquemas básicos son aquellos que establecen incondicionalmente que ciertos elementos pertenecen al conjunto.
• Los esquemas inductivos son aquellos que establecen que un elemento, llamado conclusión del esquema, está en el conjunto si otros elementos llamados hipótesis del esquema están en el conjunto.

Los elementos de A son aquellos para los cuales puede mostrarse que pueden construirse a partir de un número finito de aplicaciones de esquemas.

Principio de inducción estructural sea A un conjunto definido inductivamente y P una propiedad sobre los elementos de A. Supongamos que:

• 1. Para cada esquema básico en la definición de A, si x es introducido en A por la misma,

entonces P(x) es verdadera.

• 2. Para cada esquema inductivo en la definición de A, si P es verdadera para cada hipótesis del

esquema entonces P es verdadera para la conclusión del esquema. Entonces, P(x) es verdadera para todo x en A."

Se utiliza para demostrar resultados sobre conjuntos definidos recursivamente. El caso práctico lo podemos observar en los ejemplos:

Ejemplos

• Demuestra que en toda fórmula bien formulada, se abren el mismo número de paréntesis que se cierran.

1. Paso base: Las fórmulas V, F y p no contienen paréntesis, por lo que claramente se abren y se cierran el mismo número de paréntesis.
2. Paso recursivo: Suponemos que p y q son fórmulas bien construidas, cada una de ellas con los mismos paréntesis abiertos que cerrados. Esto es, si se abren ap y aq paréntesis en p y q, respectivamente, y se cierran cp y cq, entonces ap=cp y aq=cq. Para completar el paso de inducción, necesitamos mostrar que también tienen el mismo número de paréntesis abiertos y cerrados. En el primer caso se abren ap+1; en las demás fórmulas, ap+aq+1. De forma similar, en el primer caso se cierran cp+1 paréntesis, mientras que en las demás cp+cq+1. Como sabemos que ap=cp y aq=cq, se sigue que en estas cuatro expresiones se abren los mismos paréntesis que se cierran. Esto completa la demostración por inducción.

Véase también

Función matemática

Conjunto

Inducción matemática

Referencias

Bibliografía

Matemática discreta y sus aplicaciones, Kenneth H. Rosen

Grahan, R.L., Knutn, D.E., Patashnik, O. Concrete Mathematics

Enlaces externos

Epistemowikia Teorema de Lamé:http://mathworld.wolfram.com/LamesTheorem.html

Inducción:http://repem.exactas.unlpam.edu.ar/cdrepem10/memorias/comunicaciones/Reflexiones/CB%2022.pdf

https://www.u-cursos.cl/ingenieria/2011/1/CC3101/1/material_docente/bajar?id_material=348900

• Datos: Q30917633