Inducción completa

El principio del buen orden: todo conjunto
no vacío de enteros positivos posee un
mínimo.
Principio del buen orden






El principio del buen orden: todo conjunto
no vacío de enteros positivos posee un
mínimo.
Ejemplo: A={n: 2n-(-1)n no es múltiplo 3 }
Si no fuera vacío, tendría un mínimo m.
1) m>1 pues 21-(-1)1= 3
2) como 2m-(-1)m no es múltiplo de 3 
2m-1-(-1)m-1 es múltiplo de 3 (¿porqué?)
Principio del buen orden




Pero si 2m-1-(-1)m-1 es múltiplo de 3 
(clase pasada) 2m-(-1)m es múltiplo de 3
¡Contradicción!  A es vacío.
Equivalencia del principio de buen orden y
el de inducción completa: ejercicio o leer
Grimaldi Teorema 4.1
Inducción completa fuerte

Principio de inducción fuerte: Sea A(n)
una proposición acerca del entero n.
Si sabemos que:



A(n0) , A(n0+1), …, A(n1) es verdadera y
Si k  n1 ,siempre que A(n0) , A(n0+1), …,
A(k) sea verdadera se cumple que A(k+1)
también lo es,
Entonces A(n) vale para todo nn0.
Inducción completa fuerte



Ejemplo: Todo natural mayor que 7 se
puede expresar como suma de 3s y 5s
Principio de inducción fuerte a A(n) = “n
es suma de 3s y 5s”. Y n0 = 8.
Demostraremos que


A(8) , A(9), A(10) son verdaderas y
Si k  10 , A(8) , A(9), …, A(k) verdaderas 
A(k+1) verdadera
Inducción completa fuerte







A(8) , A(9), A(10) , A(11) :
8 = 3+5, 9 = 3+3+3, 10=5+5
k  10 y A(8) , A(9), …, A(k) verdaderas 
A(k+1) verdadera:
k  10  k > k+1-3  8  A(k+1-3) verdadera
 k+1-3 =
3+..+3+5+..+5 
k+1 = 3+ 3+..+3+5+..+5 
A(k+1) verdadera:
Inducción como forma de conteo




Esquema:
1) cuento a “mano” algunos casos para
diferentes n
2) Conjeturo una fórmula
3) La demuestro por inducción
Inducción como forma de conteo





Ejemplo: Cantidad de subconjuntos de un conjunto con
10 elementos.
0) Considero el problema general para n elementos y an
dicha cantidad
1) si n = 1 tengo P({1}) = {{}, {1}}
 a1 = 2
n=2
P({1,2}) = {{}, {1}, {2},{1, 2}}
 a2 = 4
n = 3 P({1,2,3}) = {{},{1}, {2},{3},{1, 2},{1,3},{2,3}
,{1,2,3}}
 a2 = 8
Inducción como forma de conteo





Ejemplo: Cantidad de subconjuntos de un conjunto con
10 elementos.
0) Considero el problema general para n elementos y an
dicha cantidad
1) si n = 1 tengo P({1}) = {{}, {1}}
 a1 = 2 = 21
n=2
P({1,2}) = {{}, {1}, {2},{1, 2}}
 a2 = 4 = 22
n = 3 P({1,2,3}) = {{},{1}, {2},{3},{1, 2},{1,3},{2,3}
,{1,2,3}}
 a2 = 8 = 23
Inducción como forma de conteo











2) Conjeturo que an = 2n
3) Demostración por inducción:
Base: n = 1 ya lo cheque
Paso inductivo Si vale para k vale para k+1:
Sea S  Ak+1 = {1,…,k+1} entonces
o bien k+1  S o bien k+1  S. 
P(Ak+1) = {S sin k+1}  {S con k+1}
Pero {S sin k+1} = P(Ak)
Y {S con k+1} = {S  {k+1}: S sin k+1} 
|{S con k+1}| = |{S sin k+1}| = ak
 ak+1 = ak + ak = 2k + 2k = 2k+1.
Definiciones recursivas







Ejemplo 1: n! = n (n-1)!
Y
0! = 1
Ejemplo 2: Cmn = Cm-1n + Cm-1n-1 y
Cmm = 1
Ventajas:
Cálculo
Demostración por inducción
Desventajas: Propiedades
Triángulo de Pascal
Ejemplo de demostración usando la
definición recursiva
Considere la sucesión definida por
an = an-1 + an-2 si n  2,
y a0 = a 1 = 1
Entonces a2 = a1 + a0 = 1 +1 = 2
a3 = a2 + a1 = 2 +1 = 3
Etc

n 0
an 1
1
1
2
2
3
3
4
5
5
8
6 7
13 21
Ejemplo de demostración usando la
definición recursiva






Conjeturamos que an  2 n  n  6
Por inducción fuerte con n0 = 6 y n1 = 7.
Paso base: sale de la tabla.
Paso inductivo: suponemos válida la proposición para n =
6, 7, …, k con k  7 y queremos demostrarla para k+1:
ak+1 = ak +ak-1
Para aplicar hipótesis inductiva a ak y ak-1 debemos
chequear que k y k-1 están entre 6 y k. Para k es obvio,
para k-1, sale de cómo k  7  k-1 
ak  2k + 2(k-1) = 4k-2 que es mayor o igual que 2(k+1)
para todo k  2, pero estabamos bajo la hipótesis de k 
6, así que se cumple.
Principio de inclusión-exclusión




¿Cuantos enteros del 1 al 100 no son
múltiplos de 2 ni de 3?
¿Cuántas soluciones enteras hay a la
ecuación
x+y+z+t = 18, con x, y, z, t <=7
¿Cuántas funciones sobreyectivas hay?
¿Cuantas permutaciones no dejan ninguno
símbolo en su lugar original?
Diagramas de Venn
Diagramas de Venn
Ventanal en el
comedor del
Gonville and Caius
College, Cambridge,
conmemorando la
estancia de Venn y su
principal
descubrimiento
Diagramas de Venn
Diagramas de Venn
Principio de inclusión-exclusión

|(A1c…Anc)| =
|U| - |(A1… An)c|=
|U| - |A1…An| =
|U| - |A1| - |A2| -…- |An| +
+ |A1A2| + |A1A3|+ …+|An-1An|+
|A1A2A3|+ … + |An-2An-1An|-…
(-1)n |A1A2…An|
Números de Stirling




Sob(m, n) = k=0m Cmk (-1)k (n-k)m
S(m, n) = Sob(m,n)/n!
Sob(m, n) = Cant. de formas de distribuir
m objetos distinguibles en n cajas
distinguibles sin que queden cajas vacías
S(m, n) = Cant. de formas de distribuir m
objetos distinguibles en n cajas
indistinguibles sin que queden cajas vacías
Resumen de técnicas de conteo




Básicas: combinaciones, etc
Inducción completa
Inclusión-exclusión
Principio del palomar
Relaciones de recurrencia

Ejemplo: ¿de cuántas formas se puede
baldosar un patio de 2x16 con baldosas de
1x2?
Relaciones de recurrencia

Ejemplo: ¿de cuántas formas se puede
baldosar un patio de 2x16 con baldosas de
1x2?
Relaciones de recurrencia

Ejemplo: ¿de cuántas formas se puede
baldosar un patio de 2x16 con baldosas de
1x2?
Relaciones de recurrencia

Ejemplo: ¿de cuántas formas se puede
baldosar un patio de 2x16 con baldosas de
1x2?
Relaciones de recurrencia

Ejemplo: ¿de cuántas formas se puede
baldosar un patio de 2x16 con baldosas de
1x2?
Relaciones de recurrencia


Si fuera chico sería más fácil de contar!
Empecemos por los más chicos: 2x1, 2x2,
2x3, etc:
Baldosado 2x3
Baldosado
2x2
2x3
2x4
Baldosado
2x2
2x3
2x4
Baldosado

En general si voy a construir cualquier
baldosado, tengo exactamente dos formas de
empezar:




con una baldosa vertical o
Con dos baldosas horizontales
En el primer caso el resto lo baldosamos como si
el patio fuera largo n-1 mientras que en el
segundo como si fuera de n-2
Así an = an-1 + an-2 mientras que a1 =1 y a2 = 2.
Baldosado



Así an = an-1 + an-2 mientras que a1 =1 y a2
= 2.
De aquí la sucesión es: 1
2
3
5
8
13 21 34 55 89 144 233
377 610 987 1597
De donde hay 1597 formas de baldosar un
patio de 2x16.
Baldosado

¿Asintóticas?
Descargar

Inducción completa