Sommatorie di binomiali

[Sisifo]

Allora.. visto che mi è stato chiesto posto la dimostrazione di queste due identità che, credo, facciano parte della teoria di base

1-
$ \displaystyle \sum ^n _{k=0} {n \choose k} = 2^n $


Dal teorema del binomio di Newton
$ \displaystyle 2^n = (1+1)^n = \sum ^n _{k=0} {n \choose k} 1^k 1^{n-k} $

2-
$ \displaystyle \sum ^n _{k=0} {n \choose k}^2 = { 2 n \choose n} $
Sempre dal teorema del binomio di Newton, il coefficiente di grado n in (x+y)^2n è $ 2n \choose n $, ma, per la regola dei prodotti di polinomi è anche la somma dei prodotti dei coefficienti di grado k e n-k in (x+y)^n e (x+y)^n per k che va da 0 a n. Da qui l'identità.

[mitchan88]

La seconda mi era sconosciuta!

Nello sviluppo del binomio di Newton, ponendo x=1 e y=-1, si ottiene un'altra identità carina!

[Oblomov]

Ti ringrazio Sisifo per avere postato la dimostrazione della prima,l'ho cercata sui testi in mio possesso ma non sono riuscito a trovarla.
Non ho capito bene la dimostrazione della seconda ma non importa molto.
Conosco però un'altra sommatoria interessante di cui ignoro la dimostrazione:
$ \displaystyle \sum ^n _{k=0} (-1)^k{n \choose k}=0 $.
Se la sai potresti scriverla?
P.S. Anche se probabilmente non servono per il glossario,ecco altre sommatorie "carine":
$ \displaystyle \sum ^n _{k=0} k{n \choose k}=n2^{n-1} $
$ \displaystyle \sum ^n _{k=0} {(-1)^k}k{n \choose k} =0 $
$ {n \choose 0}+{n \choose 2}+{n \choose 4}+{n \choose 6}...=2^{n-1} $
$ {n \choose 1}+{n \choose 3}+{n \choose 5}+{n \choose 7}...=2^{n-1} $
Spero che possano interessare.Anche qui se qualcuno conosce la dimostrazione é invitato a postarla al più presto.
Saluti,
Oblomov

[EvaristeG]

Oblomov, la dimostrazione di questa sommatoria è gemella della prima, come aveva velatamente fatto notare mitchan88 :

$ 0=(1-1)^n=\displaystyle{\sum_{k=0}^n(1)^{n-k}(-1)^k{n\choose k}} $

[Marco]

La prima delle sommatorie carine si risolve con in-and.out formula: tiri dentro k, fai uscire n, lo raccogli a fattor comune e ti riduci al caso precedente.
La seconda te l'ha spiegata Mithan88 e E.G., le ultime due seguono dalla 1- [primissima del post] e dalla "prima carina": sommi in un caso, sottrai nell'altro.

[HiTLeuLeR]

...oppure con le derivate formali: per ogni $ n \in \mathbb{N} $, vale $ \displaystyle (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k $, e perciò identicamente $ \displaystyle n\cdot (1+x)^{n-1} = \sum_{k=1}^n k \binom{n}{k} x^{k-1} $. Da qui la tesi, assumendo $ x = \pm 1 $.

[Oblomov]

La prima delle sommatorie carine si risolve con in-and.out formula: tiri dentro k, fai uscire n, lo raccogli a fattor comune e ti riduci al caso precedente.

Grazie Marco,ho fatto due conti e mi viene.

sommi in un caso, sottrai nell'altro

Qui mi viene un po' meno...ho notato che la somma delle utime due "carine"(non é un bel termine,va bene) dà $ 2^n $,come é giusto,ma non so come dimostrarle.Puoi aiutarmi?
Scusate il linguaggio un po' da Cellularese ma a quest'ora non connetto più.
Yawnn...'notte gente
Ob

[Marco]

Ah, sì. Ho capito la tua perplessità: nella fretta ho confuso la "seconda carina" con l'"altra sommatoria interessante". La seconda carina si fa come la prima.

Chiamo (i) la formula:

$ \displaystyle \sum ^n _{k=0} {n \choose k} = 2^n $

Chiamo (ii) la

$ \displaystyle \sum ^n _{k=0} (-1)^k{n \choose k}=0 $

Se fai la media aritmetica [(i) + (ii)]/2, i termini con k dispari si cancellano, mentre quelli pari restano.
Se invece fai la semidifferenza [(i) - (ii)]/2, scompiaiono i pari e restano i dipari.

[Marco]

Dato che siamo in vena di sommatorie di binomiali, ne manca una utilissima:
$ $ \sum_{i=k}^n \binom i k = \binom{n+1}{k+1} $.

[Oblomov]

Se fai la media aritmetica [(i) + (ii)]/2, i termini con k dispari si cancellano, mentre quelli pari restano.
Se invece fai la semidifferenza [(i) - (ii)]/2, scompiaiono i pari e restano i dipari.

Sagace!
Marco,ti ringrazio per l'aiuto.Per quanto riguarda la nuova,"utililissima" sommatoria che hai scritto ti chiedo come si dimostra e poi non ti scoccio più.
Saluti e salumi come al solito,
Ob&Ob

[Marco]

Fissi k e induci su n.