OliForum Matematico

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

Molto bello questo problema!

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.

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...

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....

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

bella

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

bella anche questa