Autor |
Mensaje |
Dul
Nivel 3
Edad: 31
Registrado: 03 Jul 2012
Mensajes: 20
Ubicación: Vicente López
|
|
Hola,
No entiendo cómo resolver el ejercicio 2 de este parcial http://wiki.foros-fiuba.com.ar/materias:61:07:parcial_00_20111029_1 :
Demostrar, utilizando el principio de inducción, que en un conjunto de n elementos hay (n(n-1))/2 subconjuntos de exactamente dos elementos, si n es mayor o igual a 2. Exprese claramente cual es la proposición que debe probar.
No sé cómo llegar a la proposición, justamente.
Alguien me puede ayudar?
Gracias
|
|
|
|
|
|
|
|
|
Nik
Nivel 4
Edad: 33
Registrado: 09 Ago 2011
Mensajes: 77
Carrera: Electrónica
|
|
Primero verificas para n=2. Por ejemplo {a,b} -> se cumple la fórmula porque sólo hay un subconjunto de 2 elementos.
Ahora para el paso inductivo:
Hip) En un conjunto de n elementos hay n(n-1)/2 subconjuntos. Formalmente: sea An="Cantidad de subconjuntos de exactamente 2 elementos que hay en un conjunto de n elementos". Es decir:
Hip) An = n(n-1)/2
Ahora, la Tesis a probar, la proposición a probar, debe ser la fórmula aplicada para n+1 elementos. Es decir:
Tesis) An+1 = (n+1)(n+1-1)/2 = (n+1)(n)/2
Demostración)
Si tengo n elementos en un conjunto y agrego uno, con éste último elemento agregado puedo formar nuevos subconjuntos de 2 elementos "uniéndolo" con cada uno de los n elementos que ya estaban en el conjunto. Es decir, la idea es:
Tenía n elementos:{x1,x2,x3,...,xn} , agrego uno (y) -> puedo formar n nuevos subconjuntos de 2: {x1,y},{x2,y},.....,{xn,y}.
Entonces, en total, con n+1 elementos tengo:
An+1 = n + n(n-1)/2 = (los nuevos n subconjuntos más los An subconjuntos que ya tenía )
Finalmente operando con esa expresión se llega a la que había que llegar según la tesis:
An+1 = (n+1)(n)/2
Cualquier cosa si no se entendió volvé a preguntar
|
|
|
|
|
|
|
|
|
|
|
Ver tema siguiente
Ver tema anterior
Podés publicar nuevos temas en este foro No podés responder a temas en este foro No podés editar tus mensajes en este foro No podés borrar tus mensajes en este foro No podés votar en encuestas en este foro No Podéspostear archivos en este foro No Podés bajar archivos de este foro
|
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker365 Attacks blocked.
|
|
[ Tiempo: 0.4511s ][ Pedidos: 22 (0.3836s) ] |