Risultato MOOLTO interessante

[mattilgale]

posto questa identità moolto interessante che ho scoperto spulciando su mathlinks,

$ \displaystyle \sum_{i=0}^n(-1)^iP(i){n\choose i}=0 $ con $ n>p\geq 0 $ dove p è il grado del polinomio P(x)

per la dimostrazione vi rimando a

http://www.mathlinks.ro/Forum/viewtopic.php?t=90529

perché è veramente dura, non tanto per il metodo(tipicamente olimpico) ma per gli strummenti utilizzati (non propriamente tali)...

invito comunque i BIG a cimentarsi con questo interessante quesito

[ficus2002]

Molto bello questo problema!

[Nonno Bassotto]

Non ho visto bene la dimostrazione di cui posti il link, ma da alcune parole che ho letto (scusate ma sono con un modem e ci metto un sacco a caricarla tutta) credo di averne una più semplice, che posto qua in bianco.

Basta verificare l'identità per P(x)=x^k, dove n>k. Il polinomio (x-1)^n si annulla di ordine n in 1, quindi la sua k-esima derivata è nulla in 1. D'altra parte

(x-1)^n=somma di (-1)^i x^i c(n,i)

dove c(n.i) sono le combinazioni di i elementi scelti fra n. Derivando k volte e scegliendo x=1 si trova una cosa che è praticamente la tesi, cioè

0=somma di (-1)^i i (i-1)...(i-k+1) c(n,i)

Questo è il polinomio che compare la tesi, più un pezzo di grado più basso, e si può andare per induzione su k.

[Catraga]

Anch'io penso che sia sufficiente dimostrarla per gli elementi della base di R[x] (lo spazio vettoriale dei polinomi a coefficienti reali), poi per estensione lineare vale per tutto lo spazio...

[Catraga]

Sparo col cannone...

Si vede che la somma
$ $$ \sum_{n=0}^\infty\sum_{i=0}^n (-1)^ii^k{n \choose i}x^n $$ $
e' la convoluzione esponenziale delle funzioni:
$ e^{-x} \qquad \left(x\frac{d}{dx}\right)^ke^x=e^xq(x) $
con q(x) polinomio di grado k.
Ovvero e' la moltiplicazione di
$ \sum_{n=0}\frac{(-1)^i}{n!}x^n \qquad \sum_{n=0}\frac{n^k}{n!}x^n $
quindi:
$ e^{-x}e^xq(x)=q(x) $
Essndo deg(q)<n si ha che la somma e' nulla poiche'
$ [[x^n]]q(x)=0 $
Ok, molto poco olimpico....

[Simo_the_wolf]

Induzione sul grado di $ P(x) $. Il caso in cui il polinomio è una costante è banale in quanto sappiamo che $ \sum \binom nk = (1-1)^n =0 $.

Passo induttivo: diciamo che $ P(x)= x Q(x) + a_0 $ dove $ a_0 $ è il termine noto di $ P(x) $. Chiamiamo poi $ P'(x)= Q(x+1) $.Abbiamo:


$ \displaystyle \sum_{i=0}^n (-1)^i P(i) \binom ni = $
$ \displaystyle \sum_{i=0}^n (-1)^i Q(i) i \binom ni + a_0 \sum_{i=0}^n (-1)^i \binom ni = $
$ \displaystyle = -n \sum_{i=1}^n (-1)^{i-1} Q(i) \binom {n-1}{i-1} + a_0 (1-1)^n = $
$ \displaystyle = -n \sum_{k=0}^{n-1} (-1)^{k} P'(k) \binom {n-1}{k} $


Abbiamo sfruttato il fatto che $ \binom ni = \frac ni \binom {n-1}{i-1} $.
Ma quest'ultima quantità è 0 per ipotesi induttiva in quanto $ deg(P')=deg(P)-1 $. Fine

[mattilgale]

bella

[frengo]

io ho invece una dimostrazione un pò più..."combinatoria":

allora:

innanzitutto visto che

$ \sum\limits_{i=0}^n(-1)^iP(i)\binom{n}{i}=0 $,$ \sum\limits_{i=0}^n(-1)^iQ(i)\binom{n}{i}=0\longrightarrow\sum\limits_{i=0}^n(-1)^i[P(i)+Q(i)]\binom{n}{i}=0 $
e
$ \sum\limits_{i=0}^n(-1)^iP(i)\binom{n}{i}=0\longrightarrow\sum\limits_{i=0}^n(-1)^iaP(i)\binom{n}{i}=0 $ per ogni $ a\in\mathbb{R} $

basta dimostrare "solamente" che

$ \sum\limits_{i=0}^n(-1)^ii^k\binom{n}{i}=0 $ per ogni $ 0\leq k<n $

consideriamo l'espressione $ i^k\binom{n}{i} $: essa rappresenta,dato un insieme di n persone,i modi di scegliere un sottoinsieme di i persone,e affidare a queste persone k incarichi DISTINGUIBILI(anche più per una persona).

sia ora $ S_{k;j} $ il numero di modi di affidare i k incarichi a j persone diverse appartenenti a tutto l'insieme di n persone.


lemma 1:
$ i^k\binom{n}{i}=\sum\limits_{j=0}^i\binom{n-j}{i-j}S_{k;j} $

dimostrazione:

troviamo quante volte $ S_{k;j} $ è contato in $ i^k\binom{n}{i} $; ogni configurazione di $ S_{k;j} $ è contata un numero di volte pari al numero di insiemi di i elementi che contengano i j già scelti, quindi $ \binom{n-j}{i-j} $.QED


usando il lemma 1, trasformiamo la tesi:

$ \sum\limits_{i=0}^n(-1)^ii^k\binom{n}{i}=0 $

$ \sum\limits_{i=0}^n(-1)^i\sum\limits_{j=0}^i\binom{n-j}{i-j}S_{k;j}=0 $

$ \sum\limits_{i=0}^n\sum\limits_{j=0}^i(-1)^i\binom{n-j}{i-j}S_{k;j}=0 $

$ \sum\limits_{j=0}^n\sum\limits_{i=j}^n(-1)^i\binom{n-j}{i-j}S_{k;j}=0 $

ora, $ \sum\limits_{i=j}^n(-1)^i\binom{n-j}{i-j}=(-1)^j\sum\limits_{i=j}^n(-1)^{i-j}\binom{n-j}{i-j}=(-1)^j(1+(-1))^{i-j}=0 $

e quindi tutta la somma è uguale a 0.

ciao ciao

[mattilgale]

bella anche questa