Combinazioni con ripetizione, dimostrazione

[Lavinia Volpe]

Th: C'n,k= ((n+k-1)(k))

Dimostrazione (per induzione):
1) k=1 C'n,1=((n)(1))=n ; ((n)(1))=n

2) C'n,k+1 = ((n+k)(k+1))
Possiamo ripartire le C'n,k+1 in n categorie, che otteniamo così:
1° categoria: le combinazioni (da quel che ho capito di ordine k+1) che contengono almeno una volta il 1° elemento
2* categoria: le combinazioni che contengono il 2° elemento e non il 1°
così via fino alla categoria che contiene solo l'ennesimo elemento

Le C'n,k+1 saranno uguali alla somma di queste categorie


Da qui comincia la parte che non capisco:
Quindi per costruire la prima categoria aggreghiamo all'elemento 1 tutte le C'n,k, avremo ((n+k-1)(k))
Per la seconda categoria aggreghiamo all'elemento 2 una qualsiasi C'n-1,k, avremo ((n+k-2)(k))
e così via fino all'ultima categoria ((k)(k))

Qui finisce la parte che non capisco

La somma delle n categorie è per ipotesi induttiva è uguale a ((n+k)(k+1))

Ci ricordiamo a questo punto una proprietà del fattoriale: ((n+1)(k+1)) = ((n)(k))+((n-1)(k))+.....+((k+1)(k))+((k)(k))

[fisicarlo]

Mi dispiace, ma sono allergico alle dimostrazioni per induzione, non le ho mai tollerate...