UNIVERSIDAD ABIERTA Y A
DISTANCIA DE MEXICO
LICENCIATURA EN MATEMÁTICAS
Análisis combinatorio
C.P. ANA MARIA JURADO CAZAREZ
AL11505074
FACILITADOR:
Carmen Regina Navarrete gonzalez
UNIDAD 1. ¿Qué es el análisis combinatorio?
Actividad 1. Inducción matemática
Resuelve los siguientes ejercicios usando inducción matemática.
1. Demuestra que n !=n( n−1)(n−2) …(3)(2)(1) . Parte de la definición recursiva
de factorial.
Probamos primero que la igualdad se cumple para n= 1.
Por definición, tenemos que n !=el producto de … … .
por lo tanto ,1 !=1
Ahora, supongamos que se cumple para k:
Tenemos que: k !=( k ) ( k −1 )( k−2 ) ( k −3 ) … . ( 3 )( 2 ) ( 1 )
Ahora, demostramos que también se cumple para
( k +1 ) !=( k +1 ) ( k +1−1 )( k + 1−2 ) ( k +1−3 ) … . ( 3 ) ( 2 )( 1 )= ( k +1 ) ( k ) ( k−1 ) …(3)(2)(1)
Es decir:
( 1 ) ( 2 )( 3 ) … ( k ) ( k +1 ) =(k+ 1) !
Correcto, para demostrar lo anterior considera la definición rescursiva de factorial:
Entonces
(k+1)!=(k+1-1)!(k+1)=(k+1)k!
Como k !=( k ) ( k −1 )( k−2 ) ( k −3 ) … . ( 3 )( 2 ) ( 1 )
Queda demostrado que
( 1 ) ( 2 )( 3 ) … ( k ) ( k +1 ) =(k+ 1) !
Por lo tanto, como la relación n !=n( n−1)(n−2) …(3)(2)(1) se cumple para n=1 y
si se cumple para n=k también se cumple para n=k+1, se demuestra que es
verdadera.
2. Para cualquier conjunto A , su conjunto potencia, P A , se define como el
conjunto formado por todos sus subconjuntos. Demuestra que si A tiene n
elementos, entonces ¿ P A ∨¿ 2n .
Supongamos que A={ a1 , a2 , a3 , … , an } es un conjunto finito
Verificamos para n= 1, es decir, que el conjunto tenga solo un elemento.
A={ a } , los subconjuntos serian: ∅ , { a }
Entonces, A tiene 2 subconjuntos, que es igual a 2=21 subconjuntos.
Supongamos ahora que la propiedad se cumple para
n=k , es decir , que tendria 2k subconjuntos
Consideremos ahora un conjunto con k +1 elementos .
A={ a1 , a2 , a3 , … , ak , ak+1 }
Si B es un subconjunto de A, puede ocurrir que a k+1 este o no este en el subconjunto B.
Caso 1. a k+1 no este en el subconjunto B. a k+1 ∉ B
Entonces, B es un subconjunto de A, donde B= { a1 , a2 , a 3 , … , a k , }
Y tendremos 2k subconjuntos porque tenemos k elementos y decimos que la proposición
se cumple para k elementos del conjunto.
Caso 2. a k+1 este en el subconjunto B. a k+1 ∈ B
Entonces, B= { ak+ 1 } ∪C , donde C ⊂ A
{a k+1 }
siempre esta fijo y solo habría que contar cuantos subconjuntos habría en C, pero
como ya sabemos que son 2k subconjuntos de este tipo.
En consecuencia, en total tengo: 2k +2k =21 ( 2k ) =2k+1
Correcto, al aumentar un elemento se duplica el número de subconjuntos que se pueden
formar.
n
1 n
3. ∑ i ( i+1 =
) ( n+1 )
i=1
En esta ocasión, es i quien cambia de valor, entonces:
Verificamos que se cumple para i= 1 (hacemos también n= 1)
1 1 1 1
= =
1 ( 1+1 ) ( 1+1 ) 2 2
Suponemos ahora que es verdadero para i= n.
1 n
=
n ( n+1 ) ( n+1 )
No se cómo hacer que se cumpla la igualdad.
Has comprobado que la igualdad se cumple para n=1
Ahora establecemos la hipótesis de inducción, es decir, suponemos que la igualdad se
cumple para un valor cualquiera de n, digamos k:
k
1 k
∑ i ( i+1 =
) ( k +1 )
…(1)
i=1
Lo que queremos demostrar es que se cumple para el siguiente valor, es decir, para
n=k+1
k +1
1 k +1
∑ i ( i+1 =
) ( k +2 )
…(2)
i=1
(Observa que donde había k, pusimos k+1)
Voy a comenzar la demostración
Por propiedades de la suma (la descomponemos)
k +1 k k+1
1 1 1
∑ i ( i+1 )
=¿ ∑ +∑ ¿ (observa los índices)
i=1 i=1 i ( i+1 ) i=k +1 i ( i+1 )
Lo que está en color azul es la hipótesis de inducción (ecuación (1)), lo que está en color
1
verde es
(k + 1)(k +2)
Así que
k +1 k k+1
∑ i ( i1+1 ) =¿ ∑ i ( i+1
1
+∑
1
=
k
+
1
) i=k +1 i ( i+1 ) ( k +1 ) (k +1)(k + 2)
¿
i=1 i=1
Falta resolver para demostrar (2) y concluir.
(∑ )
n 2 2 n 2
n ( n+1 )
4. ∑ i =
3
= i
i=1 4 i=1
Esta fórmula es para obtener la suma de los primeros n cubos.
Los primeros n cubos son: (son k cubos)
3 3 3 3
1 +2 +3 +…+ k
Verificamos primero que se cumple cuando n= 1
3 12 ( 1+1 )2 1 ( 2 )2 4
1= = = =1
4 4 4
Suponemos ahora que se cumple para n= k
Verificamos que se cumple para n= k+1
3 3 3 3 3
1 +2 +3 +…+ k + ( k +1 )
Donde:
2 2
3 3 3 k ( k +1 )
3
1 +2 +3 +…+ k = (correcto, esta es la hipótesis inductiva)
4
k ( k +1 ) + 4 ( k +1 ) ( k + 1 ) ( k + 4 k + 4 )
2 2 2 2 3 2 2
k ( k +1 ) 3
Entonces: + ( k +1 ) = =
4 4 4
Y como k 2+ 4 k + 4=( k +2 )2
( k +1 )2 ( k +2 )2
entonces :
4
Muy bien, si deseas probar que (es opcional)
( )
n 2 2 2
n ( n+ 1 )
∑i = 4
i=1
Observa que
( ) [ ][ ]( )
k +1 2 k k+1 2 k 2 k 2 k
∑i = ∑ i+ ∑ i = ∑ i+(k +1) = ∑ i +2 ( k +1 ) ∑ i+( k +1 ) 2
i=1 i=1 i=k+ 1 i=1 i=1 i=1
Y recuerda que
k 2 2
k (k + 1)
∑ i= 4
i=1
Es la hipótesis de inducción, así que solo falta sustituir, simplificar y concluir.
5. Un polígono es una figura geométrica plana formada por una sucesión finita
de segmentos rectilíneos, unidos consecutivamente hasta encerrar una
región. Los segmentos rectilíneos que lo forman son sus lados, y los puntos
en que se unen son los vértices. Lo llamamos convexo si sus ángulos
interiores —los que forman los lados dentro del polígono— son menores a
180°.
(a) (b) (c) (d) (e) (f) (g)
En la figura se muestra diversos polígonos, (b), (d), (e) y (g) son convexos. La diagonal de
un polígono es un segmento de recta que une dos vértices que no son consecutivos.
En esta figura se muestran en rojo algunas diagonales de los polígonos convexos de la
figura anterior. ¿Qué ocurre con el triángulo? ¿Tiene diagonales?
Usando el principio de inducción matemática, demuestra que un polígono de n lados tiene
n(n−3)
exactamente diagonales.
2
En el caso del triángulo, como las diagonales se trazan de un vértice a otro no
consecutivos, y en esta figura no hay vértices consecutivos, no hay diagonales.
Correcto
La siguiente figura en la que se pueden trazar diagonales es el cuadrilátero, en el que
pueden trazarse 2 diagonales sin repetirlas.
Entonces, empezamos la demostración verificando cuando n= 4 (vértices de la figura)
4( 4−3) 4
D= D= D=2
2 2
Suponemos ahora que es válida para n= k vértices.
k ( k−3 )
Tendríamos que:
2
Verificamos ahora que se cumpla para (k+1) vértices:
k ( k−1) k ( k −3 ) +2 ( k −1 ) k 2−3 k +2 k −2 k 2−k −2 (k +1)(k −2)
+k −1= = = =
2 2 2 2 2
Muy bien, al agregar un vértice el número de diagonales resulta (k-2)+1=k-1
6. Uso de identidades
a) Una ruleta tiene los enteros de 1 a 25 colocados en forma aleatoria.
Demuestra que, independientemente de su posición en la ruleta, existen tres
de ellos adyacentes cuya suma es al menos 39.
Este es un problema de existencia, proporciona tres números cualesquiera que cumplan
lo pedido.
2n n
b) Determina el entero positivo n para el cual ∑ i=∑ i
2
i=1 i=1
La suma de los primeros n números naturales es:
n(n+1)
2
Correcto, pero nos piden la suma de los primeros 2n números naturales
La suma de los primeros n cuadrados es:
n(n+1)(2 n+1)
6
Buscamos un número que cumpla con las dos condiciones, entonces:
n(n+1) n(n+1)(2 n+1)
=
2 6
Procedemos a resolver la ecuación:
6 [ n(n+1) ] =2 [ n (n+1)(2n+ 1) ] 6 n ( n+1 )=2 n(n+1)(2 n+1)
6 n(n+1)
=2 n ( 2n+ 1 ) 6 n=2 n ( 2n+1 ) 6 n=4 n2 +2 n
(n+1)
4 n −4 n=0 4 ( n −n )=0
2 2
Resolvemos la ecuación y los valores que obtuve son: x= 1 y x= 0
Trabajamos con números naturales, el 0 no es un número natural, aunque algunas
personas consideran que sí.
Veamos si se cumple
2n n
∑ i=∑ i2
i=1 i=1
Para n=1
Si n=1
∑ i=1+ 2
i=1
∑ i2=1
i=1
Por lo que para n=1
2n n
∑ i ≠ ∑ i2
i=1 i=1
Como mencioné al principio, la suma es para los primeros 2n números naturales:
2n n 2n
n(n+1)
∑ i=∑ i+ ∑ i=
2
+ n+1+n+2+…+ 2n=1+2+…+ n+ n
2
i=1 i=1 i =n +1
2n
n (n+1) n(n+ 1) 2
∑ i= 2
+
2
+ n =n ( n+ 1 )+ n2
i=1
2n
∑ i=n ( 2n+1 )
i=1
Ahora ya puedes proceder como al principio y resolver para hallar el valor para el cual se
cumple la igualdad.
c) Considera las cuatro ecuaciones siguientes:
(1 1 = 1
)
(2 2 + 3 + 4 = 1 + 8
)
(3 5 + 6 + 7 + 8 + 9 = 8 + 27
)
(4 10 + 11 + 12 + 13 + 14 + 15 + 16 = 27 + 64
)
Conjetura la fórmula general sugerida por estas ecuaciones y demuéstrala.
Al analizar las ecuaciones encontré lo siguiente:
Las cantidades del lado izquierdo de la igualdad son los números naturales y
aumentan en la siguiente proporción: 1, 3, 5, 7, 9…. N.
En el lado derecho de la igualdad, tenemos los cubos de estos dígitos,
empezando por el cubo de 1 en la primera ecuación. En la segunda ecuación,
tenemos otra vez el cubo de 1 y el cubo de 2, el siguiente digito.
En la parte izquierda, podemos utilizar la fórmula para obtener la suma de los
primeros n dígitos, pero, tenemos que restar aquellos que no se consideran.
Luego, me di cuenta que la primera ecuación tiene un digito, empieza con el 1, la
segunda ecuación termina con el 5, la tercera con el 9, la cuarta con el 16.
Mi problema era como determinar cuál sería el último dígito en cada ecuación,
pero es fácil determinarlo, porque cada a ecuación sumamos el siguiente número
impar y tenemos el ultimo digito y ese mismo número es la cantidad de dígitos que
sumaremos.
Entonces, el problema es que no sé cómo representar el miembro izquierdo de la
igualdad.
Creo que en el lado izquierdo, iría la suma de los n primos para determinar el
número de dígitos que llevara cada ecuación respecto a la anterior.
Para este ejercicio, nos enfocamos en estas cuatro ecuaciones.
Por ejemplo, para la ecuación (2)
3 3 3 3
S2=2+3+ 4=1+8=1 + 2 =( 2−1 ) +2
¿Puedes determinar Sn?