OliForum Matematico

se l'insieme A ha n elementi, allora si dimostri che il suo insieme delle parti abbia 2^n elementi..

claudiothe2nd ha scritto:se l'insieme A ha n elementi, allora si dimostri che il suo insieme delle parti abbia 2^n elementi..

Semplicissimo...
per ogni elemento abbiamo due scelte: includerlo o non includerlo nel sottoinsieme.
Trotale: 2^n

In maniera alternativa si contano i sottoinsiemi di 0, 1, ..., n elementi con l'identità algebrica$ \sum_{i=0}^n {n\choose i}=2^n $

EDIT: sorry, aveva già risposto qualcuno...

Propongo una dimostrazione per induzione del fatto che $ \displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n $, che poi è la richiesta di claudio, nota l'interpretazione "combinatorica" dei coefficienti binomiali...

Per n=0 funziona.
Suppongo sia $ \displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^n $.

Considero ora un $ (n+1) $-esimo elemento dell'insieme di partenza. Quanti sottoinsiemi in più posso creare, tenendo conto della sua presenza?
Beh, $ \displaystyle\binom{n}{0} $ sottoinsieme da 1 elemento (l'(n+1)-esimo deve esserci per definizione), $ \displaystyle\binom{n}{1} $ da 2 elementi (tutti i modi di abbinare all'(n+1)-esimo elemento gli altri n elementi)... e così via, fino ai $ \displaystyle\binom{n}{n-1} $nuovi sottoinsiemi da n elementi e agli $ \displaystyle\binom{n}{n} $ (che poi, ovviamente, è un sottoinsieme solo!) da n+1 elementi.
Totale, $ \displaystyle\sum_{k=0}^{n}\binom{n}{k}+\sum_{k=0}^{n}\binom{n}{k}=2^n+2^n=2\cdot 2^n=2^{n+1} $, ossia la tesi...

EDIT: Piccolo refuso... corretto per pignoleria!...

Quest'esercizio mi perseguita...
Ultimamente me lo ritrovo ovunque!
Io l'avevo dimostrato, sempre per induzione, sfruttando il fatto che

$ \displaystyle\binom{n}{k} $ = $ \displaystyle\binom{n-1}{k} $ + $ \displaystyle\binom{n-1}{k-1} $

oppure provare a sviluppare (1+1)^n