Sommatoria di binomiali nulla (OWN)

Polinomi, disuguaglianze, numeri complessi, ...
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Sommatoria di binomiali nulla (OWN)

Messaggio da dario2994 » 19 feb 2010, 18:34

Dato $ $n\in\mathbb{N} $ dimostrare che
$ $\sum_{i=0}^n{2i\choose i}{2(n-i)\choose n-i}\frac{1}{2i-1}=0 $
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 19 feb 2010, 19:38

Mi sa che manca qualche segno nella sommatoria.
Sono il cuoco della nazionale!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 19 feb 2010, 21:50

Mi pare sia vera così... potrebbe essere che ho sbagliato qualche calcolo, nel qual caso trovate un controesempio :)
p.s. ho controllato via pc, è giusta così, mi erano venuti dei dubbi xD Non vi rimane che dimostrarla :twisted:
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 20 feb 2010, 17:13

Ehm, effettivamente ho parlato prima di accorgermi che il primo termine della somma era negativo! Comunque n=0 è un controesempio. Supponiamo ora n>0.

$ $\sum_{i=0}^n \frac{1}{2i-1}\binom{2i}{i}\binom{2(n-i)}{n-i}=0 $
Portiamo dall'altra parte l'unico termine negativo
$ $\sum_{i=1}^n \frac{1}{2i-1}\binom{2i}{i}\binom{2(n-i)}{n-i}=\binom{2n}{n} $
Sciogliamo il primo bionomiale e semplifichiamo il semplificabile
$ $\sum_{i=1}^n \frac{1}{2i-1}\frac{2i(2i-1)}{i^2}\binom{2(i-1)}{i-1}\binom{2(n-i)}{n-i}=\binom{2n}{n} $
$ $\sum_{i=1}^n 2\frac{1}{i}\binom{2(i-1)}{i-1}\binom{2(n-i)}{n-i}=\binom{2n}{n} $
Ora dividiamo a metà ogni termine e sommiamo metà del primo con metà dell'ultimo, poi metà del secondo con metà del penultimo, e così via fino a sommare metà dell'ultimo con metà del primo
$ $\sum_{i=0}^{n-1}\left(\frac{1}{i+1}+\frac{1}{n-i}\right)\binom{2i}{i}\binom{2(n-1-i)}{n-1-i}=\binom{2n}{n} $
Sommiamo normalmente le frazioni tra parentesi, ottenendo sempre n+1 come numeratore
$ $\sum_{i=0}^{n-1}\frac{n+1}{(i+1)(n-i)}\binom{2i}{i}\binom{2(n-1-i)}{n-1-i}=\binom{2n}{n} $
Dividiamo per n+1, permutiamo un po' i fattori
$ $\sum_{i=0}^{n-1}\frac{1}{i+1}\binom{2i}{i}\frac{1}{n-i}\binom{2(n-1-i)}{n-1-i}=\frac{1}{n+1}\binom{2n}{n} $
Ed eccoci arrivati a una famosa identità sui numeri di Catalan.
$ $\sum_{i=0}^n C_iC_{n-1-i}=C_n $
Sono il cuoco della nazionale!

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 20 feb 2010, 17:34

Complimenti per l'OWN, hai riscritto la definizione dei numeri di Catalan. :?
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 20 feb 2010, 17:39

Suvvia Tibor, può darsi che dario2994 sia arrivato da solo alla sommatoria, non è detto che sia stata un'apparizione di Catalan a suggerirgliela.
Sono il cuoco della nazionale!

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 20 feb 2010, 17:45

Non metto in dubbio la sua buona fede, ci mancherebbe. E' questa moda dell'OWN ad essere ridicola.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
ghilu
Messaggi: 177
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 20 feb 2010, 22:15

Facciamolo senza numeri di Catalan, per induzione.
Passo base: n=1 facile facile.
Con più o meno i primi passaggi di Anér e sostituendo con 'a' e 'b' $ \ i\ e \ (n-i) $ si trova:
$ $LHS+\binom{2n}{n}=\sum_{a+b=n-1}\frac{2}{a+1}\binom{2a}{a}\binom{2b}{b}=\sum_{a+b=n-1}\frac{1}{(a+1)(b+1)}\binom{2a}{a}\binom{2b}{b} $.
Poniamo di aver dimostrato che i tre membri, per 'n', valgano $ \binom{2n}{n} $.
Dimostriamolo per (n+1).
$ $\sum_{a+b=n}\frac{2}{a+1}\binom{2a}{a}\binom{2b}{b}-\frac{2}{n+1}\binom{2n}{n}=\sum_{a+b=n-1}\frac{2}{a+1}\binom{2a}{a}\binom{2(b+1)}{b+1}= $
$ $=\sum_{a+b=n-1}\frac{4(2b+1)}{(a+1)(b+1)}\binom{2a}{a}\binom{2b}{b}= $
$ $=\sum_{a+b=n-1}\left( \frac{8}{a+1}-\frac{4}{(a+1)(b+1)}\right) \binom{2a}{a}\binom{2b}{b}= $
$ $=4\binom{2n}{n} -\frac{4}{n+1}\binom{2n}{n} $
Infine:
$ $\sum_{a+b=n}\frac{2}{a+1}\binom{2a}{a}\binom{2b}{b}=\frac{4n+2}{n+1}\binom{2n}{n}=\binom{2(n+1)}{n+1} $.
Non si smette mai di imparare.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 20 feb 2010, 22:30

Bien :)
Comunque la mia dimostrazione passava per i numeri di Catalan ma differentemente... nel senso che sfruttavo il fatto che i numeri Catalan sono i percorsi sotto la bisettrice (ne conosco una dimostrazione che non passa per questa formula... Callegari docet xD) e che i percorsi sotto la bisettrice rispettavano una certa ricorrenza, che è proprio questa riscritta e riadattata :)
@ Tibor: uff... sei noioso, è ovvio che i miei non sono OWN come li intendi tu, non mi aspetto di aver trovato un'identità (per quanto strana) che non abbia mai notato nessuno in secoli di matematica... ma questo non mi impedisce di timbrarlo così, soprattutto se non conosco quell'identità, che comunque non mi pare poi così nota (ma questo è relativo).
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

fph
Site Admin
Messaggi: 3511
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 21 feb 2010, 13:25

Complimenti per l'OWN, hai riscritto la definizione dei numeri di Catalan. :D

Nel senso: complimenti per aver trovato (ok, ritrovato, ma fa niente) tutto da solo un'identità non banale che ai matematici è sfuggita fino al 1800 e rotti.

Divertente come la stessa frase in bocca a persone diverse possa assumere senso completamente diverso. --- per esempio sapendo che TG è solito avere la lingua affilata si tende a interpretare come un commento sarcastico e sprezzante tutto quello che dice (e spesso, ahimé, si indovina).

Ok, giusto per non andare troppo OT, vi faccio notare che dovrebbe esserci anche una soluzione di "generating-functionology", in questo modo.
1) trasformo la relazione da provare in $ \sum_{n=0}^\infty\left(\sum_{i=0}^n{2i\choose i}{2(n-i)\choose n-i}\frac{1}{2i-1}\right)x^n=-1 $ (uguaglianza tra somme formali) (notare che il "-1" discende dall'osservazione che per n=0 non funziona, già fatta da Anér)
2) trasformo questa relazione in $ F(x)G(x)=-1 $, dove $ F(x)=\sum_{n=0}^\infty {2n\choose n}\frac{1}{2n-1}x^n $ e $ G(x)=\sum_{n=0}^\infty {2n\choose n} x^n $
3) mi trovo una formula chiusa per F(x) e G(x). Se uno "si è portato la casa" la dimostrazione per trovare la serie generatrice dei Catalan, sa che $ C(x)=\frac{1-\sqrt{1-4x}}{2x} $ (dove C(x) è la serie generatrice dei numeri di Catalan). Moltiplicando per x e derivando la sommatoria termine a termine, si ha che $ (xC(x))'=\sum_{n=0}^\infty {2n\choose n} x^n=G(x) $. Da questa relazione segue una formula chiusa (=senza sommatorie) per G(x), che se non sbaglio i conti (probabile) è $ G(x)=(1-4x)^{-1/2} $
4) F(x) è un po' più incasinata: si può calcolare come $ F(z^2)=z\int_0^z y^{-2}G(y^2)dy $ (dovete moltiplicare per l'esponente giusto e integrare per far sì che l'integrale termine a termine si "mangi" quel 2n-1), e verrà un integrale di una funzione incasinata con le radici quadrate. In realtà però non bisogna calcolare davvero quest'integrale "alla cieca", perché se la tesi è vera sappiamo già quanto fa. Basta quindi verificare che $ F(z^2)=\frac{-1}{G(z^2)} $, e questo è più facile: dobbiamo controllare che $ -\sqrt{1-4z^2}=\frac{-1}{G(z^2)}\stackrel{hope}{=}F(z^2)=z\int_0^z y^{-2}\frac{dy}{\sqrt{1-4y^2}} $. Portando la z di là e derivando da entrambi i lati, abbiamo
$ \frac{d}{dz}\frac{-\sqrt{1-4z^2}}{z}\stackrel{hope}{=}\frac{1}{z^2\sqrt{1-4z^2}} $, che è solo un "conto della serva".

Sembra un contazzo senza senso? Forse. Ma la cosa importante è che è automatico: se uno conosce la "generating-functionology", sa che è questa la strada su cui andare, e tra lui e la fine c'è solo un conto di mezz'oretta. E questo in gara è importante. E' come quando sapete il bunching e riuscite a ricondurre una disuguaglianza a un conto lungo ma automatico.

[esercizio: la fine del punto 4 contiene un errore che si aggiusta facilmente ma che mi farebbe perdere un punto: quale?]

[il post qui sopra può contenere errori di segno, derivazioni sbagliate, e tracce di noci]
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 21 feb 2010, 13:51

Alur... con grossi sforzi ho capito buona parte della tua soluzione. Mi rimane assolutamente oscuro il motivo di questa uguaglianza:
$ $ F(z^2)=z\int_0^zy^{-2}G(y^2)dy $
che mi pare uno dei punti chiave... contando che io non so assolutamente nulla di analisi (quindi tantomeno di integrali) c'è un modo semplice per spiegarmelo??? Altrimenti vado sulla fiducia senza nessun problema :) E ci ripenserò tra qualche anno (mese???) quando ne saprò qualcosa.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

fph
Site Admin
Messaggi: 3511
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 21 feb 2010, 17:34

Hai ragione, quel passaggio non è spiegato per niente.
In G hai dei termini del tipo $ {2n \choose n}x^n $ e vuoi ottenere dei termini del tipo $ {2n \choose n}\frac1{2n-1}x^n $.
Con un po' di esperienza, uno sa che il modo più semplice di far comparire dei fattori che assomigliano a quello è derivando/integrando termine a termine. Se integri un addendo del tipo $ {2n \choose n}x^n $ ti viene $ {2n \choose n}\frac1{n+1}x^{n+1} $, con il denominatore sbagliato. Come si fa ad aggiustare questo denominatore? Cambi la potenza di x in modo che l'esponente venga 2n-2: cioè consideri $ y^{-2}G(y^2)=\sum {2n \choose n} y^{2n-2} $. Adesso hai una potenza 2n-2-esima a destra, e quindi quando integri ottieni $ \int_0^z y^{-2}G(y^2)dy=\sum_n {2n \choose n} \int_0^z y^{2n-2}dy= \sum_n {2n \choose n} \frac1{2n-1} z^{2n-1} $. Adesso questa serie ha gli stessi coefficienti di F(x) ma le potenze sbagliate. Per sistemarle, scrivi come serie di potenze $ z^{-1}F(z^2) $, che ha gli stessi coefficienti di F(z) ma gli esponenti aggiustati come serviva a noi.

Se vuoi approfondire queste tecniche, qui http://www.math.upenn.edu/~wilf/DownldGF.html trovi un libro online che ne parla. Sono molto potenti se uno le sa usare bene, ma difficili da imparare -- ci vuole un po' di calma. [in particolare, non è una lettura da affrontare tre giorni prima della partenza per una gara, casomai tu fossi in questa situazione ;) ]
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 21 feb 2010, 18:16

fph ha scritto:Nel senso: complimenti per aver trovato (ok, ritrovato, ma fa niente) tutto da solo un'identità non banale che ai matematici è sfuggita fino al 1800 e rotti.
Questa è un'interpretazione decisamente OWN. :o
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 21 feb 2010, 19:07

Chiarissimo, il libro gia lo conoscevo ed in realtà gia l'avevo anche scaricato (quando piever bruciò un problema per me tostissimo sfruttando le funzioni generatrici) ma non ho mai avuto il coraggio di leggerlo seriamente xD Ho giusto leggiucchiato le basi mesi fa...
Comunque in effetti, assumendo di conoscere un poco di "trucchetti di base", il tuo modo di procedere è molto straightforward. Può far comodo e poi non sono così tanti i conti 8)
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

fph
Site Admin
Messaggi: 3511
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph » 21 feb 2010, 19:33

Bene.
Se hai voglia di perderci su qualche minuto, c'è ancora da stanare questo bachetto nel punto 4:
fph ha scritto:[esercizio: la fine del punto 4 contiene un errore che si aggiusta facilmente ma che mi farebbe perdere un punto: quale?]
(ok, più che "la fine del punto 4" è "tutto il punto 4 dall'inizio alla fine")
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Rispondi