Ciao.
Dimostrare che, per $ n $ intero e positivo,
$ $ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k^n = n! $.
Binomiali, potenze e fattoriali
Binomiali, potenze e fattoriali
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Beh, una soluzione carina ce l'ho (ma probabilmente e' lo stesso "conteggio notevole" cui accenna Teppic nell'altro filo). In pratica si tratta di calcolare il volume di un cubo unitario in modo ... strano ...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Beh, visto che ho già fatto casino nell'altra discussione, ecco una soluzione possibile:
Siano $ c_1,\dots c_n $ n colori
prendiamo n palline distinte, chiamando $ C_i $ l'insieme delle colorazioni di queste palline in cui nessuna è del colore $ c_i $
Quanto elementi ha l'insieme $ \bigcup_{i=1}^n C_i $ ??? Beh, sono tutte le colorazioni in cui almeno un colore non c'è mai, per cui tutte meno quelle in cui ci sono tutti gli n colori, cioè $ n^n-n! $
Per il principio di inclusioneesclusione ne ha $ \displaystyle\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}(n-k)^n $
Segue che $ \displaystyle\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}(n-k)^n=n^n-n! $ ovvero $ \displaystyle\sum_{k=0}^n (-1)^{k}\binom{n}{k}(n-k)^n=n! $ che è la tesi.
Siano $ c_1,\dots c_n $ n colori
prendiamo n palline distinte, chiamando $ C_i $ l'insieme delle colorazioni di queste palline in cui nessuna è del colore $ c_i $
Quanto elementi ha l'insieme $ \bigcup_{i=1}^n C_i $ ??? Beh, sono tutte le colorazioni in cui almeno un colore non c'è mai, per cui tutte meno quelle in cui ci sono tutti gli n colori, cioè $ n^n-n! $
Per il principio di inclusioneesclusione ne ha $ \displaystyle\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}(n-k)^n $
Segue che $ \displaystyle\sum_{k=1}^n (-1)^{k+1}\binom{n}{k}(n-k)^n=n^n-n! $ ovvero $ \displaystyle\sum_{k=0}^n (-1)^{k}\binom{n}{k}(n-k)^n=n! $ che è la tesi.
Fondatore dell'associazione "Non uno di meno", per lo sterminio massiccio dei nani e affini.
Premessa: questo metodo è molto più apprezzabile su somme un po' più complicate, ma visto che funziona...
Osserviamo che $ (x-1)^n=\displaystyle{\sum_{k=0}^n(-1)^{n-k}x^k{n\choose k}} $.
Sia $ f(x)=(x-1)^n $.
Osserviamo che $ \displaystyle{x\frac{\textrm{d}f(x)}{\textrm{d}x}=\sum_{k=0}^n(-1)^{n-k}kx^k{n\choose k}} $.
E dunque (con n derivate e n-1 moltiplicazioni per x)
$ \displaystyle{g(x)=\frac{\textrm{d}}{\textrm{d}x}\left(x\frac{\textrm{d}}{\textrm{d}x}\left(x\cdots \left(x\frac{\textrm{d}}{\textrm{d}x}f(x)\right)\cdots\right)\right)} $$ =\displaystyle{\sum_{k=0}^n(-1)^{n-k}k^nx^k{n\choose k}} $.
Dunque $ g(1) $ è la nostra somma.
Ora, $ xf'(x)=nx(x-1)^{n-1} $; proseguendo a derivare e moltiplicare per x, compariranno sempre termini della forma $ ax^{\alpha}(x-1)^{\beta} $, fino a che non si deriva l'$ n- $sima volta in cui compare anche un termine con $ \beta=0 $, che è quello ottenuto derivando sempre il fattore $ (x-1) $. Perciò
$ g(x)=(x-1)p(x)+n(n-1)(n-2)\cdots2\cdot1x^{n-1} $
quindi
$ g(1)=n! $.
Epilogo: non l'ho postato perché è una bella soluzione, ma perché è un metodo molto efficace e generalizzabile.
Osserviamo che $ (x-1)^n=\displaystyle{\sum_{k=0}^n(-1)^{n-k}x^k{n\choose k}} $.
Sia $ f(x)=(x-1)^n $.
Osserviamo che $ \displaystyle{x\frac{\textrm{d}f(x)}{\textrm{d}x}=\sum_{k=0}^n(-1)^{n-k}kx^k{n\choose k}} $.
E dunque (con n derivate e n-1 moltiplicazioni per x)
$ \displaystyle{g(x)=\frac{\textrm{d}}{\textrm{d}x}\left(x\frac{\textrm{d}}{\textrm{d}x}\left(x\cdots \left(x\frac{\textrm{d}}{\textrm{d}x}f(x)\right)\cdots\right)\right)} $$ =\displaystyle{\sum_{k=0}^n(-1)^{n-k}k^nx^k{n\choose k}} $.
Dunque $ g(1) $ è la nostra somma.
Ora, $ xf'(x)=nx(x-1)^{n-1} $; proseguendo a derivare e moltiplicare per x, compariranno sempre termini della forma $ ax^{\alpha}(x-1)^{\beta} $, fino a che non si deriva l'$ n- $sima volta in cui compare anche un termine con $ \beta=0 $, che è quello ottenuto derivando sempre il fattore $ (x-1) $. Perciò
$ g(x)=(x-1)p(x)+n(n-1)(n-2)\cdots2\cdot1x^{n-1} $
quindi
$ g(1)=n! $.
Epilogo: non l'ho postato perché è una bella soluzione, ma perché è un metodo molto efficace e generalizzabile.
Ok. Vi scrivo la mia.
Voglio calcolare il volume del ipercubo unitario in dimensione $ n $, ossia l'insieme $ C = [0,1]^n $. Lo faccio montando dei simplessi con il principio di inclusione-esclusione.
Inizio contando tutti i punti
(a) a coordinate positive,
(b) la cui somma delle coordinate non supera $ n $.
Questo insieme è un simplesso di spigolo $ n $, e quindi ha volume
$ n^n / n! $.
Ora, sicuramente ho contato tutti i punti del cubo $ C $, però ho contato troppa roba, perché ad esempio ho contato tutti i punti che hanno una coordinata maggiore di 1 e che soddisfano le altre condizioni (a) e (b).
Ad esempio, fissando la prima coordinata. L'insieme dei punti che soddisfano (a), (b) e
(c_1) la prima coordinata è maggiore di 1
è un simplesso di spigolo $ n-1 $, ed ha volume $ (n-1)^n / n! $. Ripeto la stessa cosa per ogni possibile scelta di coordinata, e quindi per $ \binom{n}{1} $ scelte.
Dal mio contgeggio del volume, voglio percio' togliere tutti questi simplessi piu' piccoli. Se faccio cosi', conto correttamente una volta i punti di $ C $, conto zero volte i punti che soddisfano esattamente una condizione di tipo (c), ma ho sottratto troppe volte i punti che soddisfano due o piu' condizioni di tipo (c).
Allora riaggiungo i simplessi di lato $ n-2 $ che soddisfano (a), (b) e due condizioni di tipo (c). Tali simplessi sono $ \binom{n}{2} $.
Ecc....
Alla fine, il volume totale di $ C $ risulterà essere
$ $ \binom{n}{0} \frac{n^n}{n!} - \binom{n}{1} \frac{(n-1)^n}{n!} + \binom{n}{2} \frac{(n-2)^n}{n!} \cdots \pm \binom {n}{n} \frac{0^n}{n!} $
Ma sappiamo che il volume del cubo unitario è 1. []
Notare che, se si usa la stessa identica dimostrazione sostituendo la condizione (b) con
(b') la somma delle coordinate non supera $ x $, con $ x \geqslant n $,
si dimostra l'identità:
$ $ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} (x-k)^n = n! $
Del resto, questa identità eguaglia due polinomi, quindi (principio di identità dei polinomi) deve valere per ogni $ x $, e non solo per $ x \geqslant n $.
Voglio calcolare il volume del ipercubo unitario in dimensione $ n $, ossia l'insieme $ C = [0,1]^n $. Lo faccio montando dei simplessi con il principio di inclusione-esclusione.
Inizio contando tutti i punti
(a) a coordinate positive,
(b) la cui somma delle coordinate non supera $ n $.
Questo insieme è un simplesso di spigolo $ n $, e quindi ha volume
$ n^n / n! $.
Ora, sicuramente ho contato tutti i punti del cubo $ C $, però ho contato troppa roba, perché ad esempio ho contato tutti i punti che hanno una coordinata maggiore di 1 e che soddisfano le altre condizioni (a) e (b).
Ad esempio, fissando la prima coordinata. L'insieme dei punti che soddisfano (a), (b) e
(c_1) la prima coordinata è maggiore di 1
è un simplesso di spigolo $ n-1 $, ed ha volume $ (n-1)^n / n! $. Ripeto la stessa cosa per ogni possibile scelta di coordinata, e quindi per $ \binom{n}{1} $ scelte.
Dal mio contgeggio del volume, voglio percio' togliere tutti questi simplessi piu' piccoli. Se faccio cosi', conto correttamente una volta i punti di $ C $, conto zero volte i punti che soddisfano esattamente una condizione di tipo (c), ma ho sottratto troppe volte i punti che soddisfano due o piu' condizioni di tipo (c).
Allora riaggiungo i simplessi di lato $ n-2 $ che soddisfano (a), (b) e due condizioni di tipo (c). Tali simplessi sono $ \binom{n}{2} $.
Ecc....
Alla fine, il volume totale di $ C $ risulterà essere
$ $ \binom{n}{0} \frac{n^n}{n!} - \binom{n}{1} \frac{(n-1)^n}{n!} + \binom{n}{2} \frac{(n-2)^n}{n!} \cdots \pm \binom {n}{n} \frac{0^n}{n!} $
Ma sappiamo che il volume del cubo unitario è 1. []
Notare che, se si usa la stessa identica dimostrazione sostituendo la condizione (b) con
(b') la somma delle coordinate non supera $ x $, con $ x \geqslant n $,
si dimostra l'identità:
$ $ \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} (x-k)^n = n! $
Del resto, questa identità eguaglia due polinomi, quindi (principio di identità dei polinomi) deve valere per ogni $ x $, e non solo per $ x \geqslant n $.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
click! ma fermandosi un passetto prima se si dimostra con la "derivata discreta" (quella usata nel primo post del link del primo post... 
) che vi consiglio di provare a fare, cioè definire ricorsivamente $ p_{k+1} (x) = p_k(x) - p_k(x-1) $ e esprimere $ p_n(x) $ in funzione di $ p_0(x) $ e notando cosa succede passo per passo (il grado e il coeff. di grado massimo).
In questo modo si dimostra quello che voleva edriv dove al posto di $ k^n $ c'è un qualsiasi polinomio $ p(k) $ monico di n-esimo grado
) che vi consiglio di provare a fare, cioè definire ricorsivamente $ p_{k+1} (x) = p_k(x) - p_k(x-1) $ e esprimere $ p_n(x) $ in funzione di $ p_0(x) $ e notando cosa succede passo per passo (il grado e il coeff. di grado massimo).In questo modo si dimostra quello che voleva edriv dove al posto di $ k^n $ c'è un qualsiasi polinomio $ p(k) $ monico di n-esimo grado