Numero di sottoinsiemi di 3 elementi per induzione

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Numero di sottoinsiemi di 3 elementi per induzione #58436

avt
Jetser
Punto
Ciao a tutti! Sto cercando di fare questa dimostrazione per induzione, riguarda il numero di sottoinsiemi di 3 elementi di un insieme di n elementi. Arrivato a un certo punto non so come andare avanti.

Dimostrare per induzione che per ogni n>=0 un insieme di n elementi ha \frac{n(n-1)(n-2)}{6} sottoinsiemi con 3 elementi.

Allora faccio il caso base ponendo n=3 e la formula restituisce 1, che è corretto, quindi la formula è verificata per n=3. adesso il passo induttivo, pongo n+1 al posto di n e la formula diventa

\frac{n(n-1)(n+1)}{6}

faccio i calcoli e ottengo questa, chiamiamola (a)

\frac{n^{3} - n}{6}

adesso prendo la formula nel caso n (non n+1) e la espando, e ottengo questa, chiamiamola (b)

\frac{n^{3} -3n^{2} +2n}{6}

a questo punto cerco di trovare la formula (b) nella formula (a), quindi alla formula (a) aggiungo e tolgo 3n^2 e 3n, così ottengo

\frac{n^{3} -n -3n^{2} +3n^{2} +3n -3n}{6}

da qui separo la formula in due pezzi

\frac{n^{3} -3n{^2} +2n}{6} + \frac{3n{^2} -3n}{6}

Così la prima parte è uguale alla formula (b), ma non so cosa fare della seconda parte. Chiedo scusa se ho esposto il problema in modo confusionario.

Grazie per l'attenzione emt
 
 

Numero di sottoinsiemi di 3 elementi per induzione #58461

avt
Galois
Amministratore
Ciao Jetser emt

Da quel che leggo hai le idee un po' confuse su come si utilizza il Principio di induzione, ragion per cui ti invito, innanzitutto, a leggere con molta calma ed attenzione la lezione di cui al link emt

Fatto ciò, dobbiamo dimostrare, per induzione su n, che un insieme di n elementi, con n \in \mathbb{N} ha esattamente:

(*) \ \frac{n(n-1)(n-2)}{6}

sottoinsiemi di 3 elementi.

(1) Base di induzione

Dobbiamo verificare che la proprietà è verificata per n=0 (che è il nostro valore iniziale) e non n=3 come hai fatto tu.

n=0 vuol dire che siamo di fronte ad un insieme avente zero elementi, il quale ha, ovviamente, 0 sottoinsiemi di 3 elementi. In effetti sostituendo n=0 in (*) otteniamo proprio zero e quindi la base di induzione è verificata!

(2) Passo induttivo.

Supponiamo la tesi vera per n, ovvero supponiamo che un insieme di n elementi abbia esattamente

\frac{n(n-1)(n-2)}{6}

sottoinsiemi di 3 elementi e proviamo la nostra proprietà per n+1, cioè dobbiamo dimostrare, utilizzando la supposizione fatta che chiameremo ipotesi induttiva, che un insieme di n+1 elementi ha:

(*) \ \frac{(n+1)(n+1-1)(n+1-2)}{6}=\frac{(n+1)(n)(n-1)}{6}

sottoinsiemi di 3 elementi.

Posto, per comodità, che il nostro insieme di n+1 elementi sia

A'=\{x_1, \ x_2, \ ..., \ x_n, \ x_{n+1} \}

I sottoinsiemi di A' (di 3 elementi) si possono ripartire in due famiglie:

- quelli che non contengono x_{n+1}

- quelli che contengono x_{n+1}

I primi sono sottoinsiemi di \{x_1, \ x_2, \ ... \ x_n \} ovvero di un insieme di n elementi e come tali, per ipotesi induttiva sono (*).

Gli altri sono della forma

\{x_i, \ x_j, \ x_{n+1} \} con i,j \in \{1,2,..,n\}, \ i \neq j

Quanti sono?

Sono esattamente \frac{n(n-1)}{2}, infatti:

l'ultimo elemento è fissato. Gli altri possono variare. In quanti modi?

Fissiamo il primo, ovvero supponiamo, ad esempio, che i=1

Il secondo, x_j, può variare in n-1 modi.

Ri-fissiamo il primo, ovvero i=2.

Il secondo, x_j, può variare, ancora, in n-1 modi, ma, nota bene che, otteniamo due volta la stessa terna e, per la precisione:

(x_1, x_2, x_{n+1}) (dal primo ragionamento) che è uguale a (x_2, x_1, x_{n+1}) ottenuta dal secondo ragionamento.

Ripetendo lo stesso discorso per i \in \{3, \ 4, ... \ n\}

tali terne sono proprio \frac{n(n-1)}{2}

[Quel 2 a denominatore è dovuto alle terne che, di volta in volta, si ripetono]

Possiamo quindi concludere che il numero di sottoinsiemi di 3 elementi di un insieme che ne contiene n+1 è dato da:


\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2} = \ conti \ = \frac{(n+1)(n)(n-1)}{6}

che è quanto volevamo provare emt
Ringraziano: CarFaby, Jetser

Numero di sottoinsiemi di 3 elementi per induzione #58474

avt
Jetser
Punto
Ciao Galois, grazie al tuo intervento è tutto molto più chiaro, sia l'esercizio che il ragionamento alla base dell'induzione.
Grazie mille emt
Ringraziano: Galois
  • Pagina:
  • 1
Os