Dimostrazione per induzione del coefficente binomiale.

[Neptune2]

Non mi è molto chiara questa dimostrazione per induzione:

Un insieme di cardinalità N ha $((n),(k))$ sottoinsiemi di cardinalità k $AA 0<=k<=n$

Dimostrazione per induzione su n:

Passo base: $n= 0$ |insieme vuoto| = 0 $((0), (0)) = 1$ vera

Passo induttivo: supponiamo vera p(n) (e qual'è p(n) ? sarà la proposizione iniziale che vogliamo dimostrare)
$Prendiamo |x| = n+1$

Voglio verificare se i sottoinsiemi di X di cardinalità K sono $((n+1),(k))$

Se $X = {a1....an,an+1} = {a1..an} U {an+1}$

Poniamo $x' = {a1..an}$ con cardinalità pari ad n

Sia $k$ t.c $0 <= k <= n+1$

Se $k = 0$ allora $1= ((n+1),(0))
se $k = n+1$ allora $1 = ((n+1),(n+1))

Quindi p(n+1) è vera per $k = 0$ e $k =n+1$

*****Da qui inizio a perdermi..

Sia k t.c $1<=k <= n$
sia $A sube X$ con $|A| = k$ e $1 <=k<= n$
Se $an+1 notin A$ allora $A sube X'$ perchè la cardinalità è uguale a k e $|x| = n$

E quindi per ipotesi induttiva posso dire che i sottoinsiemi di a di x di cadinalità k che non contengono an+1 ce ne sono $((n),(k))$


Se invece $an+1 in A$ allora A è del tipo $S U {an+1}$ con $S sube X$

$|A| = k$ quindi $|S| = k -1$ ma per ipotesi $|X'| = n$ e per ipotesi induttiva i sottoinsiemi di cardinalità k-1 di x' sono $((n),(k-1))$

Quindi gli insiemi S sono $((n),(k-1))$ e gli A = $((n),(k-1))$

In totale i sottoinsiemi $A sube X$ ($|x|= n+1$) tali che $|a| = k$ sono $((n),(k)) + ((n),(k-1)) = ((n+1),(k)) $ come volevasi dimostrare

****

Praticamente so che tutto questo vuole dimostrare come il coefficente binomiale vale per qualsiasi N e qualsiasi k.
Parte dimostrandolo per induzione su N e trova che è vero per $K = 0$ e $K =1$ a qiesto punto però fa un'altra dimostrazione per dimostrare che questo vale anche per qualsiasi valore di k?

In questo secondo pezzo mi sono un pò perso, forse anche per erorri vari di nomenclature (o meglio, mi sembra che molte cose non vengano dichiarate bene).

Qualcuno potrebbe commentarmi un pò i passaggi e dirmi se nel caso c'è qualche erorre?

Vi ringrazio in anticipo,
Neptune.

[Nidhogg]

Per il passo induttivo, io farei così:

Supponiamo $n>=1$, quindi $|A|!=O/$. In questo caso l'asserto è verso se $k=0$ o se $k=n$. Per $k=0$ si ha un unico sottoinsieme di $A$ di cardinalità $0$ (insieme vuoto) e $((n), (0)) = 1$; $k=n$ si ha un unico sottoinsieme di $A$ di cardinalità $n$ (insieme stesso) e $((n), (n)) = 1$. Supponiamo quindi $1<=k<=n-1$. Per l'Hp induttiva abbiamo che un insieme di cardinalità $n-1$ ha esattamente $((n-1), (i))$ sottoinsiemi di cardinalità $i AA 0<=i<=n-1$. Prendiamo un elemento $a_0$ nell'insieme $A$. Un sottoinsieme di $A$ con $k$ elementi può contenere $a_0$ oppure no. I sottoinsiemi che non contengono $a_0$ sono proprio i sottoinsiemi di $A\\{a_0}$ aventi $k$ elementi. Questo insieme ha cardinalità $n-1$ e i suoi sottoinsiemi, per Hp induttiva, sono $((n-1), (k))$. I sottoinsiemi di $A$ con $k$ elementi che contengono l'elemento $a_0$ sono quelli del tipo $S uu {a_0}$, dove $S$ è un sottoinsieme avete $k-1$ elementi di $A\\{a_0}$. Per Hp induttiva tali sottoinsiemi sono $((n-1), (k-1))$. I sottoinsiemi di $A$ con $k$ elementi sono in tutto $((n-1), (k)) + ((n-1), (k-1))$. Avendo supposto che $1<=k<=n-1$, vale l'uguaglianza $((n-1), (k))+((n-1), (k-1))=((n), (k))$ e quindi vi sono esattamente $((n), (k))$ sottoinsiemi di cardinalità $k$ di $A$.

P.S.: La proposizione dimostrata vale sse $n>=k$.


Saluti,
Ermanno.