Cum demonstrez ca numarul de submultimi ale unei multimi este 2^n.Cum as putea demonstra? [DAU FUNDA]MULTUMESC

Question

aladinbeci · Accepted Answer

Maya, analizez doar ultima parte a demonstratiei. Prima parte (cea cu etapa de verificare) banuiesc ca stii cum se face.
Asadar, ar trebui sa demonstram ca daca o multime alcatuita din k elemente are (2 la puterea k) submultimi, atunci o multime alcatuita din (k + 1) elemente va avea un numar de submultimi egal cu 2 la puterea (k + 1).
Pentru aceasta sa consideram o multime A alcatuita din (k + 1) elemente, adica:
A = {a1, a2, a3,...,ak, a(k + 1)}.
Aici 1,   2,  3,..., k, (k + 1) sunt indici, deci se vor scrie mai jos decat elementele a.
Consderam acum o submultime A' a multimii A.
A' = {a1, a2, a3,...,ak}.
Deoarece am presupus ca P(k) este adevarata, avem imediat ca numarul submultimilor lui A' este (2 la puterea k).
Este evident ca din fiecare submultime a lui A', daca adaugam elementul a(k + 1) (citeste " a indice (k + 1) "), se va obtine o noua submultime a lui A. Asadar, se vor obtine inca (2 la puterea k) submultimi ale multimii A.
Numarul total de submultimi ale multimii A va fi atunci:
(2 la puterea k) (cate am presupus initial considerand P(k) adevarat) + (2 la puterea k) (cate s-au obtinut prin adaugarea elementului a indice (k + 1)) = 2*(2 la puterea k) = 2 la puterea (k + 1).
Cu semnul "*" am simbolizat inmultirea.
Asadar, s-au obtinut 2 la puterea (k + 1) submultimi ale multimii A, deci P(k + 1) este adevarata, deci, conform metodei inductiei matematice rezulta ca P(n) este adevarata.
Ma bucur daca te-am putut ajuta. Verifica si tu demonstratia.

Mickey2002 · Answer

Analizez doar ultima parte a demonstratiei. Prima parte (cea cu etapa de verificare) banuiesc ca stii cum se face.
Asadar, ar trebui sa demonstram ca daca o multime alcatuita din k elemente are (2 la puterea k) submultimi, atunci o multime alcatuita din (k + 1) elemente va avea un numar de submultimi egal cu 2 la puterea (k + 1).
Pentru aceasta sa consideram o multime A alcatuita din (k + 1) elemente, adica:
A = {a1, a2, a3,...,ak, a(k + 1)}.
Aici 1,     2,    3, ..., k, (k + 1) sunt indici, deci se vor scrie mai jos decat elementele a.
Consderam acum o submultime A' a multimii A.
A' = {a1, a2, a3,...,ak}.
Deoarece am presupus ca P(k) este adevarata, avem imediat ca numarul submultimilor lui A' este (2 la puterea k).
Este evident ca din fiecare submultime a lui A', daca adaugam elementul a(k + 1) (citeste " a indice (k + 1) "), se va obtine o noua submultime a lui A. Asadar, se vor obtine inca (2 la puterea k) submultimi ale multimii A.
Numarul total de submultimi ale multimii A va fi atunci:
(2 la puterea k) (cate am presupus initial considerand P(k) adevarat) + (2 la puterea k) (cate s-au obtinut prin adaugarea elementului a indice (k + 1)) = 2*(2 la puterea k) = 2 la puterea (k + 1).
Cu semnul "*" am simbolizat inmultirea.
Asadar, s-au obtinut 2 la puterea (k + 1) submultimi ale multimii A, deci P(k + 1) este adevarata, deci, conform metodei inductiei matematice rezulta ca P(n) este adevarata.