Inducción

Principio de inducción

La garantía de que el proceso visto se hace correctamente y que el algoritmo anterior produce la potencia de a para cualquier valor de n, viene de la mano del principio de inducción, que es la herramienta teórica en la que nos apoyaremos para dar sustento al planteamiento recursivo.

El principio de inducción se establece sobre el conjunto de los números naturales (ℕ) en tres fases o etapas, a las que denominaremos Base, Recurrencia y Conclusión.

Nos permite demostrar que una propiedad P es cierta para cualquier natural. Por ejemplo, demostrar que $\forall n \in IN, a^{n}$ se puede calcular como

$a^{n-1}*a$

1ª forma de demostración por recurrencia

Demostrar que la propiedad P se cumple para todos los naturales mayores o iguales que b

Base de la recurrencia

Demostrar que P es cierta para un número natural b

Recurrencia o paso inductivo: demostrar que la propiedad es hereditaria

Hipótesis: Se supone que P es cierta para un natural cualquiera n, siendo n $\geq$ b

Demostración: Se demuestra entonces que P se cumple también para el natural n+1

Conclusión

El resultado satisfactorio en cada una de las dos etapas anteriores, permite entonces establecer que P es cierta para todos los naturales mayores o iguales que b.

Ejemplo

Demostrar la siguiente propiedad: “Todo número de la forma 10n - 1 es divisible por 9, $\forall$ n $\in$ ℕ”

Base: demostremos la propiedad para n = 0

$10^{0}-1=0=0*9$

Recurrencia o paso inductivo

Hipótesis: supongamos que $10^{n}-1$ es divisible por 9. Existe entonces un natural a tal que

$10^{0}-1=a*9$

Demostración: tenemos que demostrar entonces que $10^{n+1}-1$ es también divisible por 9.

Para poder utilizar la hipótesis de recurrencia, intentemos expresar $10^{n+1}-1$ a partir de $10^{n}-1$

$10^{n+1}-1 = 10\cdot10^{n}-1=10\cdot(10^{n}-1)+10-1=10\cdot1(0^{n}-1)+9=$

utilizando la hipótesis de recurrencia podemos escribir

$10\cdot(a\cdot9)+9=9\cdot(10\cdot a+1)$ lo que establece que 10n+1 – 1 es un múltiplo de 9.

Conclusión

El principio de recurrencia/inducción nos permite concluir que 10n - 1 es divisible por 9, $\forall$ n $\in$ ℕ

2ª forma de demostración por recurrencia

Esta forma difiere de la anterior en la manera de definir la hipótesis de recurrencia

Base de la recurrencia

Demostrar que P es cierta para un número natural b

Recurrencia o paso inductivo: demostrar la herencia

Hipótesis: Se supone que P es cierta para todo natural comprendido entre b y n (límites incluidos) con n≥b

Demostración: Se demuestra entonces que la propiedad es cierta n+1

Conclusión:

El resultado satisfactorio en cada una de las dos etapas anteriores, permite entonces establecer que P es cierta para todos los naturales mayores o iguales que b

Ejemplo

Demostrar que

“Todo entero superior a 1 puede ser descompuesto en forma de un producto de factores primos”

Base: el número considerado es primo por lo que la propiedad es cierta

Recurrencia o paso inductivo

Hipótesis: La propiedad es cierta para todos los naturales del intervalo [2,n] con n ≥ 2 Demostración: Para demostrarlo, basta tener en cuenta que n+1 debe cumplir una de las dos condiciones siguientes

n+1 es primo: entonces la tesis está demostrada.
n+1 no es primo: decir que n+1 no es primo permite afirmar que existen dos enteros a y b tales que
n+1 = a * b y 1 < a < n+1 y 1 < b < n+1

Por hipótesis de inducción a y b satisfacen la propiedad. Se deduce entonces la propiedad para n+1

Conclusión

La propiedad se cumple para todos los naturales mayores o iguales que 2

Aplicación de la recurrencia sobre los naturales

Pueden utilizarse directamente los métodos de demostración que acabamos de recordar para establecer propiedades sobre conjuntos distintos del de los números naturales.

Una técnica frecuentemente utilizada consiste en asociar un natural a cada elemento del conjunto considerado y examinar la validez de la propiedad de los elementos en el orden de los naturales que le son asociados. Esta técnica es una generalización del principio de inducción sobre los naturales, que recibe el nombre de inducción noetheriana.

El siguiente ejemplo clásico ilustra esta técnica:

“Todo conjunto de cardinal n contiene $2^{n}$ partes”

Antes, vamos a definir partes de un conjunto.

Def.- Dado un conjunto U, se llama conjunto de las partes de U y lo representamos por P(U) al conjunto cuyos elementos son los subconjuntos de U, es decir, P(U) = { A : A ⊂ U }

Ejemplo: si U = { a, b } entonces P(U) = {Ø, {a}, {b}, {a,b}}

Ejemplo

“Todo conjunto de cardinal n contiene 2n partes”

Esta propiedad se demuestra por recurrencia de la siguiente forma: decimos que efectuamos una recurrencia sobre el cardinal del conjunto.

Base: el conjunto de cardinal 0 es el conjunto vacío. Sólo hay una parte, él mismo. como $2^{0}$ = 1, la propiedad queda demostrada.

Recurrencia:

Hipótesis: Todo conjunto de cardinal n tiene $2^{n}$ partes.

Demostración:

Sea E un conjunto de cardinal n + 1

Sea a un elemento cualquiera de E y sea F el subconjunto de E que contiene el resto de sus elementos

E = {a} $\cup$ F y F tiene n elementos.

Toda parte de E puede ser caracterizada por la presencia o ausencia del elemento a.

El conjunto de las partes de E que no contienen al elemento a es el conjunto de las partes de F. Por la hipótesis de recurrencia, hay entonces $2^{n}$ partes de E que no contienen al elemento a.
Por otro lado, el conjunto de las partes de E que sí contienen al elemento a se puede construir simplemente añadiendo a cada parte de F, el elemento a. Por lo tanto, hay también $2^{n}$ partes de E que contienen el elemento a.

En conclusión, E tiene $2^{n}+2^{n}$ partes, es decir, $2^{n+1}$ partes

Conclusión:

Todo conjunto de cardinal n contiene 2n partes.

Veámoslo con un ejemplo concreto:

E = { a, b, c } F = { b, c }

E = {a} $\cup$ F

Conjunto de las partes de E.-

el conjunto de las partes de E que no contienen al elemento a son las partes de F, es decir,

P(F) = { Ø, {b}, {c}, {b,c} }

el conjunto de las partes de E que sí contienen al elemento a , se construyen añadiendo el elemento a cada parte de F, esto es,

{{a}, {a,b}, {a,c}, {a,b,c}}

En conclusión P(E) = { Ø, {b}, {c}, {b,c}, {a}, {a,b}, {a,c}, {a,b,c} }

Definición recurrente de un conjunto

Un conjunto puede ser definido según dos técnicas:

definición explícita por enumeración de los elementos del conjunto (definición en extensión) Ejemplos:
- el conjunto de cifras impares es { 1, 3, 5, 7, 9 }
- el conjunto de vocales es { A, E, I, O, U }
definición implícita por el enunciado de una propiedad que caracteriza los elementos del conjunto (definición en comprensión). El lenguaje para formalizar la propiedad puede ser el lenguaje natural, o notaciones matemáticas, o un intermedio.

Ejemplos:

los enteros pares descritos con ayuda de dos cifras de base 10
{ x : x $\in$ ℕ y 10 ≤ x < 100 y $\exist$ y : y $\in$ ℕ y x = 2y }
{10, 12, 14, …, 98}

Es evidente que se definirá un conjunto en extensión cuando el número de elementos sea reducido. En caso contrario, es preferible recurrir a una definición en comprensión.

Una definición recurrente tiene, además, la particularidad de enfocar el problema desde una perspectiva constructiva.

La idea es que la construcción de todo elemento del conjunto se fundamenta en ciertos elementos (elementos base) y en reglas precisas de construcción.

Partiendo de los elementos base y mostrando cómo crear un nuevo elemento a partir de elementos que se supone se saben crear. Se concluye que se saben crear todos los elementos.

Enunciamos ahora el principio de definición recurrente de un conjunto:

Base: se describen (en extensión o comprensión) los elementos del conjunto que servirán para crear todos los otros con las reglas enunciadas en la etapa de recurrencia.

Recurrencia: se trata de la formulación recurrente de las reglas que permiten crear un elemento del conjunto a partir de elementos ya creados.

Recurrencia en un conjunto definido de forma recurrente

Ya hemos indicado que la recurrencia en los naturales permite establecer propiedades de conjuntos distintos de ℕ, cuando el conjunto considerado puede ser definido por recurrencia puede razonarse directamente de la siguiente manera y que recibe el nombre de inducción estructural:

Base: demostrar que P es cierta para todos los elementos que aparecen en la base de la definición recurrente del conjunto.

Recurrencia o paso inductivo

Hipótesis: La hipótesis de recurrencia consiste en suponer que los elementos que sirven para la creación de un elemento e del conjunto verifican la propiedad P.

Demostración: consiste en demostrar que e también verifica P

Conclusión: se concluye que la propiedad es cierta para todos los elementos del conjunto

Ejemplo

Sea X = { X1, X2, ..., Xi, Xi+1, ...} = { 1, 3, 5, …, 15, 17, …} la sucesión de números impares. Queremos demostrar que sobre X se cumple la siguiente propiedad:

$x_i=2i-1 \forall i\ge1$

De acuerdo con el proceso que debemos seguir en la inducción estructural, nos apoyaremos en una definición recurrente de X. En este caso, es la siguiente:

Base de la definición del dominio: 1 $\in$ X

Recurrencia de la definición del dominio: si y $\in$ X entonces y + 2 $\in$ X

Base: el primer número impar es 1, por lo que verifica la propiedad puesto que

$X_1 = 2i-1 = 2\cdot1-1=1$

Recurrencia:

Hipótesis: Suponemos que la propiedad es cierta para Xi, o sea, Xi = 2i - 1 Demostración: entonces hay que demostrar Xi+1 = 2(i+1) – 1 se puede escribir

Xi+1 = Xi + 2 = (2i - 1) + 2 = 2(i +1) – 1

lo que establece la herencia de la propiedad

Conclusión: Xi = 2i - 1 $\forall$ i $\geq$ 1

Last updated 1 year ago

Inducción

Principio de inducción

El principio de inducción se establece sobre el conjunto de los números naturales (ℕ) en tres fases o etapas, a las que denominaremos Base, Recurrencia y Conclusión.

Nos permite demostrar que una propiedad P es cierta para cualquier natural. Por ejemplo, demostrar que $\forall n \in IN, a^{n}$ se puede calcular como

$a^{n-1}*a$

1ª forma de demostración por recurrencia

Demostrar que la propiedad P se cumple para todos los naturales mayores o iguales que b

Base de la recurrencia

Demostrar que P es cierta para un número natural b

Recurrencia o paso inductivo: demostrar que la propiedad es hereditaria

Hipótesis: Se supone que P es cierta para un natural cualquiera n, siendo n $\geq$ b

Demostración: Se demuestra entonces que P se cumple también para el natural n+1

Conclusión

El resultado satisfactorio en cada una de las dos etapas anteriores, permite entonces establecer que P es cierta para todos los naturales mayores o iguales que b.

Ejemplo

Demostrar la siguiente propiedad: “Todo número de la forma 10n - 1 es divisible por 9, $\forall$ n $\in$ ℕ”

Base: demostremos la propiedad para n = 0

$10^{0}-1=0=0*9$

Recurrencia o paso inductivo

Hipótesis: supongamos que $10^{n}-1$ es divisible por 9. Existe entonces un natural a tal que

$10^{0}-1=a*9$

Demostración: tenemos que demostrar entonces que $10^{n+1}-1$ es también divisible por 9.

Para poder utilizar la hipótesis de recurrencia, intentemos expresar $10^{n+1}-1$ a partir de $10^{n}-1$

$10^{n+1}-1 = 10\cdot10^{n}-1=10\cdot(10^{n}-1)+10-1=10\cdot1(0^{n}-1)+9=$

utilizando la hipótesis de recurrencia podemos escribir

$10\cdot(a\cdot9)+9=9\cdot(10\cdot a+1)$ lo que establece que 10n+1 – 1 es un múltiplo de 9.

Conclusión

El principio de recurrencia/inducción nos permite concluir que 10n - 1 es divisible por 9, $\forall$ n $\in$ ℕ

2ª forma de demostración por recurrencia

Esta forma difiere de la anterior en la manera de definir la hipótesis de recurrencia

Base de la recurrencia

Demostrar que P es cierta para un número natural b

Recurrencia o paso inductivo: demostrar la herencia

Hipótesis: Se supone que P es cierta para todo natural comprendido entre b y n (límites incluidos) con n≥b

Demostración: Se demuestra entonces que la propiedad es cierta n+1

Conclusión:

El resultado satisfactorio en cada una de las dos etapas anteriores, permite entonces establecer que P es cierta para todos los naturales mayores o iguales que b

Ejemplo

Demostrar que

“Todo entero superior a 1 puede ser descompuesto en forma de un producto de factores primos”

Base: el número considerado es primo por lo que la propiedad es cierta

Recurrencia o paso inductivo

n+1 es primo: entonces la tesis está demostrada.
n+1 no es primo: decir que n+1 no es primo permite afirmar que existen dos enteros a y b tales que
n+1 = a * b y 1 < a < n+1 y 1 < b < n+1

Por hipótesis de inducción a y b satisfacen la propiedad. Se deduce entonces la propiedad para n+1

Conclusión

La propiedad se cumple para todos los naturales mayores o iguales que 2

Aplicación de la recurrencia sobre los naturales

Pueden utilizarse directamente los métodos de demostración que acabamos de recordar para establecer propiedades sobre conjuntos distintos del de los números naturales.

El siguiente ejemplo clásico ilustra esta técnica:

“Todo conjunto de cardinal n contiene $2^{n}$ partes”

Antes, vamos a definir partes de un conjunto.

Def.- Dado un conjunto U, se llama conjunto de las partes de U y lo representamos por P(U) al conjunto cuyos elementos son los subconjuntos de U, es decir, P(U) = { A : A ⊂ U }

Ejemplo: si U = { a, b } entonces P(U) = {Ø, {a}, {b}, {a,b}}

Ejemplo

“Todo conjunto de cardinal n contiene 2n partes”

Esta propiedad se demuestra por recurrencia de la siguiente forma: decimos que efectuamos una recurrencia sobre el cardinal del conjunto.

Base: el conjunto de cardinal 0 es el conjunto vacío. Sólo hay una parte, él mismo. como $2^{0}$ = 1, la propiedad queda demostrada.

Recurrencia:

Hipótesis: Todo conjunto de cardinal n tiene $2^{n}$ partes.

Demostración:

Sea E un conjunto de cardinal n + 1

Sea a un elemento cualquiera de E y sea F el subconjunto de E que contiene el resto de sus elementos

E = {a} $\cup$ F y F tiene n elementos.

Toda parte de E puede ser caracterizada por la presencia o ausencia del elemento a.

El conjunto de las partes de E que no contienen al elemento a es el conjunto de las partes de F. Por la hipótesis de recurrencia, hay entonces $2^{n}$ partes de E que no contienen al elemento a.
Por otro lado, el conjunto de las partes de E que sí contienen al elemento a se puede construir simplemente añadiendo a cada parte de F, el elemento a. Por lo tanto, hay también $2^{n}$ partes de E que contienen el elemento a.

En conclusión, E tiene $2^{n}+2^{n}$ partes, es decir, $2^{n+1}$ partes

Conclusión:

Todo conjunto de cardinal n contiene 2n partes.

Veámoslo con un ejemplo concreto:

E = { a, b, c } F = { b, c }

E = {a} $\cup$ F

Conjunto de las partes de E.-

el conjunto de las partes de E que no contienen al elemento a son las partes de F, es decir,

P(F) = { Ø, {b}, {c}, {b,c} }

el conjunto de las partes de E que sí contienen al elemento a , se construyen añadiendo el elemento a cada parte de F, esto es,

{{a}, {a,b}, {a,c}, {a,b,c}}

En conclusión P(E) = { Ø, {b}, {c}, {b,c}, {a}, {a,b}, {a,c}, {a,b,c} }

Definición recurrente de un conjunto

Un conjunto puede ser definido según dos técnicas:

definición explícita por enumeración de los elementos del conjunto (definición en extensión) Ejemplos:
- el conjunto de cifras impares es { 1, 3, 5, 7, 9 }
- el conjunto de vocales es { A, E, I, O, U }
definición implícita por el enunciado de una propiedad que caracteriza los elementos del conjunto (definición en comprensión). El lenguaje para formalizar la propiedad puede ser el lenguaje natural, o notaciones matemáticas, o un intermedio.

Ejemplos:

los enteros pares descritos con ayuda de dos cifras de base 10
{ x : x $\in$ ℕ y 10 ≤ x < 100 y $\exist$ y : y $\in$ ℕ y x = 2y }
{10, 12, 14, …, 98}

Es evidente que se definirá un conjunto en extensión cuando el número de elementos sea reducido. En caso contrario, es preferible recurrir a una definición en comprensión.

Una definición recurrente tiene, además, la particularidad de enfocar el problema desde una perspectiva constructiva.

La idea es que la construcción de todo elemento del conjunto se fundamenta en ciertos elementos (elementos base) y en reglas precisas de construcción.

Partiendo de los elementos base y mostrando cómo crear un nuevo elemento a partir de elementos que se supone se saben crear. Se concluye que se saben crear todos los elementos.

Enunciamos ahora el principio de definición recurrente de un conjunto:

Base: se describen (en extensión o comprensión) los elementos del conjunto que servirán para crear todos los otros con las reglas enunciadas en la etapa de recurrencia.

Recurrencia: se trata de la formulación recurrente de las reglas que permiten crear un elemento del conjunto a partir de elementos ya creados.

Recurrencia en un conjunto definido de forma recurrente

Base: demostrar que P es cierta para todos los elementos que aparecen en la base de la definición recurrente del conjunto.

Recurrencia o paso inductivo

Hipótesis: La hipótesis de recurrencia consiste en suponer que los elementos que sirven para la creación de un elemento e del conjunto verifican la propiedad P.

Demostración: consiste en demostrar que e también verifica P

Conclusión: se concluye que la propiedad es cierta para todos los elementos del conjunto

Ejemplo

Sea X = { X1, X2, ..., Xi, Xi+1, ...} = { 1, 3, 5, …, 15, 17, …} la sucesión de números impares. Queremos demostrar que sobre X se cumple la siguiente propiedad:

$x_i=2i-1 \forall i\ge1$

De acuerdo con el proceso que debemos seguir en la inducción estructural, nos apoyaremos en una definición recurrente de X. En este caso, es la siguiente:

Base de la definición del dominio: 1 $\in$ X

Recurrencia de la definición del dominio: si y $\in$ X entonces y + 2 $\in$ X

Base: el primer número impar es 1, por lo que verifica la propiedad puesto que

$X_1 = 2i-1 = 2\cdot1-1=1$

Recurrencia:

Hipótesis: Suponemos que la propiedad es cierta para Xi, o sea, Xi = 2i - 1 Demostración: entonces hay que demostrar Xi+1 = 2(i+1) – 1 se puede escribir

Xi+1 = Xi + 2 = (2i - 1) + 2 = 2(i +1) – 1

lo que establece la herencia de la propiedad

Conclusión: Xi = 2i - 1 $\forall$ i $\geq$ 1

Last updated 1 year ago

Principio de inducción

1ª forma de demostración por recurrencia

Base de la recurrencia

Conclusión

Ejemplo

Conclusión

2ª forma de demostración por recurrencia

Base de la recurrencia

Conclusión:

Ejemplo

Recurrencia o paso inductivo

Aplicación de la recurrencia sobre los naturales

“Todo conjunto de cardinal n contiene 2n2^{n}2n partes”

Ejemplo

“Todo conjunto de cardinal n contiene 2n partes”

Recurrencia:

Demostración:

Conclusión:

Veámoslo con un ejemplo concreto:

E = {a} ∪\cup∪ F

Definición recurrente de un conjunto

Recurrencia en un conjunto definido de forma recurrente

Recurrencia o paso inductivo

Ejemplo

Base de la definición del dominio: 1 ∈\in∈ X

X1=2i−1=2⋅1−1=1X_1 = 2i-1 = 2\cdot1-1=1X1​=2i−1=2⋅1−1=1

Principio de inducción

1ª forma de demostración por recurrencia

Base de la recurrencia

Conclusión

Ejemplo

Conclusión

2ª forma de demostración por recurrencia

Base de la recurrencia

Conclusión:

Ejemplo

Recurrencia o paso inductivo

Aplicación de la recurrencia sobre los naturales

“Todo conjunto de cardinal n contiene 2n2^{n}2n partes”

Ejemplo

“Todo conjunto de cardinal n contiene 2n partes”

Recurrencia:

Demostración:

Conclusión:

Veámoslo con un ejemplo concreto:

E = {a} ∪\cup∪ F

Definición recurrente de un conjunto

Recurrencia en un conjunto definido de forma recurrente

Recurrencia o paso inductivo

Ejemplo

Base de la definición del dominio: 1 ∈\in∈ X

X1=2i−1=2⋅1−1=1X_1 = 2i-1 = 2\cdot1-1=1X1​=2i−1=2⋅1−1=1

“Todo conjunto de cardinal n contiene $2^{n}$ partes”

E = {a} $\cup$ F

Base de la definición del dominio: 1 $\in$ X

$X_1 = 2i-1 = 2\cdot1-1=1$

“Todo conjunto de cardinal n contiene $2^{n}$ partes”

E = {a} $\cup$ F

Base de la definición del dominio: 1 $\in$ X

$X_1 = 2i-1 = 2\cdot1-1=1$