Sommatoria di binomiali (own)

[staffo]

Discutendo io e Claudio. abbiamo pensato a questo problema:
dimostrare che $ \sum_{k=0}^{h} \binom{n + k -1}{k} = \binom{n+h}{h} $

[Mist]

Induzione

Testo nascosto:

Per $h=1$ la tesi diventa: $\binom{n-1}{0}+\binom{n}{1} = \binom{n+1}{1}$ ovvero $n+1=n+1$ che è vero

ora, suppongo che la tesi sia vero per $h$, ovvero che valga $\sum_{k=0}^{h}\binom{n+k-1}{k} = \binom{n+h}{h}$
ora, per $h+1$ si ha che
$\sum_{k=0}^{h+1}\binom{n+k-1}{k} = \binom{n+h+1}{h+1}$
$\sum_{k=0}^{h}\binom{n+k-1}{k} + \binom{n+h}{h+1} = \frac{(n+h+1)!}{(h+1)!n!}$
Applicando l'ipotesi induttiva si ha però che
$= \frac{(n+h+1)!}{(h+1)!n!} =\frac{(n+h)!}{(h+1)!n!} (n+h+1)$

Moltiplicando ambo i membri di $\frac{(n+h)!}{h!n!}+\frac{(n+h)!}{(h+1)!(n-1)!} =\frac{(n+h)!}{(h+1)!n!} (n+h+1)$ per $\frac{(n+h)!}{(h+1)!n!}$ si ottiene una tautologia, e quindi la tesi è dimostrata per induzione.

Sono sicuro che esista una dimostrazione combinatorica, magari ci penso domani

[Claudio.]

Dimostrazione combinaTORIA si c'è, e anche abbastanza semplice, se no non credo che avremmo mai trovato quella relazione

[Mist]

http://it.wikipedia.org/wiki/Combinatoria

Vedi:termini analoghi

Testo nascosto:

se il modo di esprimere un numero come somma di $h$ numeri distinti è $\binom{n+k-1}{k-1}$ allora........ centra qualcosa ?

[staffo]

forse potrebbe entrarci, però non ne sono certo. Di sicuro può essere risolto con ragionamenti elementari sulle palline e scatole, o caramelle e bambini =), o monete e cassetti (vedete voi cosa vi diverte di più)