Usando il principio di induzione, dimostra (senza fare ricorso alla formula del binomio di Newton), che la sommatoria per k che varia da 0 a n di C(n,k) = 2^n
Usando il principio di induzione, dimostra (senza fare ricorso alla formula del binomio di Newton), che la sommatoria per k che varia da 0 a n di C(n,k) = 2^n
74
punti
Livello 1
Per n = 1 é vero,
S_k:0->1 C(1,k) = C(1,0) + C(1,1) = 1 + 1 = 2
Sia vero per n generico
S_k:0->n C(n,k) = 2^n
S_k:0->(n+1) C(n+1, k) = C(n+1,0) + C(n+1, n+1) + S_k:1->n C(n+1, k) =
= 1 + 1 + S_k:1->n [ C(n,k) + C(n, k-1) ] =
= 2 + S_k:1->n C(n,k) + S_k:1->n C(n, k-1) =
= 2 + ( S_k:0->n C(n,k) - C(n,0) ) + S_h:0->n C(n, h) - 1=
= 2 + 2^n - 1 + 2^n - 1 = 2*2^n + 2 - 2 = 2^(n+1)
nella seconda somma ho fatto un cambio di indice h = k-1
h va da 0 a n-1, resta isolato l'ultimo addendo C(n.n) = 1
Ho usato l'identità, che abbiamo già incontrato e utilizzato,
C(n+1,k) = C(n,k) + C(n,k-1)
49487
punti
Livello 7
@eidosm perfetto grazie
Posso riscrivere questa dimostrazione in cartaceo e farne un contenuto di Creator.