Sommatorie infinite difficilotte [own]

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

Sommatorie infinite difficilotte [own]

Messaggio da dario2994 » 17 ago 2009, 21:11

Calcolare
$ $\sum_{i=1}^{\infty}{\frac{i}{2^i}}$ $
Questo è abbastanza facile... ora passiamo a qualcosa di più complicato:
Calcolare
$ $\sum_{i=1}^{\infty}{\frac{i^2}{2^i}}$ $
Per finire con la generalizzazione con n naturale:
Calcolare
$ $\sum_{i=1}^{\infty}{\frac{i^n}{2^i}}$ $
p.s. Quest'ultimo è un problema abbastanza noto... e abbastanza complicato xD
p.p.s. Sfido 53thebest anche detto julian, anche detto fava a risolvere questo... magari con un'induzione base 4 in uno spazio vettoriale n-Esimo con tanto di trasformata di fourier. EDIT: su consiglio di gioacchino aggiungo che potresti usare anche le derivate mezzesime, sfruttando le tue nozioni puntiformi di analisi xD

Avatar utente
Haile
Messaggi: 515
Iscritto il: 30 mag 2008, 14:29
Località: Bergamo

Messaggio da Haile » 17 ago 2009, 23:22

Guardando la trivialità del primo (e se tu dici che il terzo è noto) che c'azzecca l'own? :shock:
[i]
Mathematical proofs are like diamonds: hard and clear.

[/i]

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

Messaggio da dario2994 » 18 ago 2009, 00:01

L'own c'azzecca che il problema prima l'ho inventato e poi ho scoperto essere noto ;)

Avatar utente
karl
Messaggi: 926
Iscritto il: 01 gen 1970, 01:00

Messaggio da karl » 19 ago 2009, 13:49

Se interessa un modesto excursus di teoria delle differenze finite
ecco una possibile soluzione.
Detto $ u_k $ una quantità numerica dipendente dall'indice k,introduciamo
i due operatori $ \displaystyle \Delta,E $ così definiti:
$ \displaystyle \Delta u_k=u_{k+1} -u_k,E u_k=u_{k+1} $
Fra di essi sussiste l'ovvia relazione simbolica :
(1) $ \displaystyle E=1+\Delta $
Ora abbiamo :
$ \displaystyle u_1=E u_o,u_2=E u_1 =E\cdot E u _0=E^2 u_o $
In generale è:
(2) $ \displaystyle u_i=E^iu_o $
E' da notare che $ E^i $ non è una vera potenza ma indica solo il risultato che si
ottiene applicando "i"volte l'operatore E.
Poniano ora :
$ \displaystyle V(x) =\sum x^i $
Se è |x|<1 allora la sommatoria infinita precedente converge a :
(3) $ \displaystyle V(x) =\frac{1}{1-x} $ e da qui deduciamo che :
$ \displaystyle V'(x) =\frac{1!}{(x-1)^2},V''(x) = \frac{2!}{(x-1)^3} $
Ed in generale :
(4) $ \displaystyle V^n(x)=\frac{n!}{(x-1)^{n+1}} $

Data ora la serie infinita (supposta convergente) $ \displaystyle \sum x^iu_i $
per la (2) si ha :
$ \displaystyle \sum x^iu_i=\sum x^iE^iu_o=\sum (xE)^i u_o=V(xE)u_o $
e per la (1):
$ \displaystyle \sum x^i u_i=V(x+x\Delta)u_o $
Sviluppando in serie di Taylor:
$ \displaystyle \sum x^i u_i=V(x)u_o+\frac{V'(x)}{1!}x\Delta u_o+\frac{V''(x)}{2!}x^2\Delta^2u_o+.... $
Ovvero per le (3) e (4):
$ \displaystyle \sum x^i u_i=\frac{1}{1-x}u_o+\frac{x}{(1-x)^2}\Delta u_o+\frac{x^2}{(1-x)^3}\Delta^2 u_o+.... $
in particolare, per $ x=\frac{1}{2},u_i=i^n $ , tenuto conto che $ \displaystyle i^n $è un polinomio e che pertanto le differenze si annullano dopo la ennesima,abbiamo:
(5) $ \displaystyle \sum\frac{i^n}{2^i}=2[u_o+\Delta u_o+\Delta^2u_o+\Delta^3u_o+...+\Delta^n u_o] $

Ora è :
$ \displaystyle u_i=i^n,u_o=0,\Delta u_o=u_1-u_o=1^n-0^n $
$ \displaystyle \Delta^2u_o=\Delta(\Delta u_o)=(u_2-u_1)-(u_1-u_o)=u_2-2u_1+u_o=2^n-2\cdot 1^n+0^n $
Analogamente:
$ \displaystyle \Delta^3u_o=u_3-3u_2+3u_1-u_o=3^n-3\cdot 2^n+3\cdot 1^n-0^n $
Ed in generale :
$ \displaystyle \Delta^n u_o=n^n-C_{n,1}(n-1)^n+C_{n,2}(n-2)^n+...+(-1)^n0^n $
Sostituendo in (5) si ha la formula attesa:
$ \displaystyle \sum\frac{i^n}{2^i}=2\cdot[(1^n-0^n)+(2^n-2\cdot1^n+0^n)+(3^n-3\cdot2^n+3\cdot1^n-0^n)+ $$ \displaystyle ....+(n^n-C_{n,1}(n-1)^n+C_{n,2}(n-2)^n+...+(-1)^n0^n)] $
In particolare per n=1,2,3 abbiamo:
$ \displaystyle \sum \frac{i}{2^i}=2\cdot[(1^1-0^1)]=2 $
$ \displaystyle \sum \frac{i^2}{2^i}=2\cdot[(1^2-0^2)+(2^2-2\cdot1^2+0^2)]=6 $
$ \displaystyle \sum\frac{i^3}{2^i}=2\cdot[(1^3-0^3)+(2^3-2\cdot 1^3+0^3)+(3^3-3\cdot 2^3+3\cdot 1^3-0^3)]=26 $

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

Messaggio da dario2994 » 21 ago 2009, 16:20

Devo ammettere che non mi sono letto tutta la dimostrazione perche´ ci sono dei punti che non capisco ma la parte che ho visto sembra funzionare... in ogni caso io ho una soluzione piu'olimpica ;)
p.s. scusate per gli strani accenti ma scrivo da una tastiera non italiana.

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 21 ago 2009, 16:49

dario2994 ha scritto:in ogni caso io ho una soluzione piu'olimpica
secondo me questo esercizio di olimpico ha ben poco
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Generatingfunctionology!

Messaggio da FeddyStra » 21 ago 2009, 19:54

Generatingfunctionology!

Definiamo la funzione (formal power serie, visto che non converge sempre) $ \displaystyle S_n(x)=\sum_{k=0}^{\infty} k^nx^k $. Il problema consisterà allora nel calcolare $ S(1/2) $.
Vogliamo dimostrare che questa somma si può scrivere anche come $ \displaystyle S_n(x)=\sum_{k} k! \mathcal{S}_n^{(k)} \frac{x^k}{(1-x)^{k+1}} $, dove $ \mathcal{S}_n^{(k)} $ indica i numeri di Stirling di seconda specie.
Chiaramente, una volta nota la formula, si potrà dare anche una dimostrazione diretta basata sull'induzione, ma io preferisco farvi vedere come l'ho ricavata perché lo ritengo un istruttivo esempio di come utilizzare le funzioni generatrici.

Iniziamo con calcolare $ S_0(x) $, che, noncuranti delle perplessità sollevate dal porre $ 0^0=1 $, definiamo essere $ \displaystyle S_0(x)=1+x+x^2+\dots+x^k+\dots=\frac1{1-x} $.
A questo punto, vorremmo passare a $ S_1(x) $. Per farlo, dobbiamo moltiplicare ogni coefficiente per il relativo esponente di $ x $. Questa operazione ci fa venire il sospetto che si possa sfruttare la derivazione. In effetti, si nota (e si dimostra, facilmente) che $ \displaystyle S_k(x)=x\frac{d}{dx}S_{k-1}(x) $.
Indichiamo per comodità con $ \vartheta $ l'operatore $ \displaystyle x\frac{d}{dx} $ e con $ \vartheta^{(m)} $ la composizione di $ \vartheta $ con se stesso $ m $ volte. A questo punto, possiamo dire che $ \displaystyle S_n(x)=\vartheta^{(k)}\left( \frac{1}{1-x} \right) $.

Cerchiamo ora un modo conveniente per calcolare questa espressione. Per farci un po' le idee, calcoliamo con questo metodo le prime tre funzioni:
$ \displaystyle S_1(x)=\frac{x}{(1-x)^2} $,
$ \displaystyle S_2(x)=\frac{x}{(1-x)^2}+2\frac{x^2}{(1-x)^3} $,
$ \displaystyle S_3(x)=\frac{x}{(1-x)^2}+6\frac{x^2}{(1-x)^3}+6\frac{x^3}{(1-x)^4} $.
Notiamo facilmente che contengono espressioni del tipo $ \displaystyle \frac{x^k}{(1-x)^{k+1}} $ con un opportuno coefficiente. Chiamiamo $ N^n_k $ il coefficiente di $ \displaystyle \frac{x^k}{(1-x)^{k+1}} $ in $ S_n(x) $. Dimostriamo ora questo fatto e ricaviamo una formula ricorsiva per $ N^n_k $.
Applicando $ \vartheta $ a ogni termine si ha che $ \displaystyle \vartheta\left( \frac{x^k}{(1-x)^{k+1}} \right) = k \frac{x^k}{(1-x)^{k+1}} + (k+1) \frac{x^{k+1}}{(1-x)^{k+2}} $, come è facile verificare (lasciato al lettore). Questo significa che $ S_n(x) $ stesso ha la forma richiesta.
Inoltre, ricaviamo la relazione ricorsiva $ N^n_k=kN^{n-1}_k+kN^{n-1}_{k-1} $. Sappiamo anche che $ N^n_k=0 $ per $ k<1 \lor k>n $ e $ N^0_0=1 $. Queste condizioni determinano completamente i coefficienti.
Definiamo le funzioni generatrici $ \displaystyle G_k(x)=\sum_{n} N^n_k x^n $. Dalla relazione tra i coefficienti appena ricavata, deduciamo che $ N^n_k x^n = k x N^{n-1}_k x^{n-1}+k x N^{n-1}_{k-1} x^{n-1} $, da cui segue la relazione tra le funzioni $ G_k(x)=kxG_k(x)+kxG_{k-1}(x) $, ovvero $ \displaystyle G_k(x)=\frac{kx}{1-kx}G_{k-1}(x) $.
Del resto, sappiamo che $ G_0(x)=1 $, quindi per induzione $ \displaystyle G_k(x)=\prod_{j=1}^{k} \frac{jx}{1-jx}=k!\prod_{j=1}^{k} \frac{x}{1-jx} $.
Ma $ \displaystyle \prod_{j=1}^{k} \frac{x}{1-jx} $ è la funzione generatrice dei numeri di Stirling di seconda specie, quindi si ha che $ N^n_k=k!\mathcal{S}_n^{(k)} $.

Ora, $ \displaystyle S_n(x) = \sum_{k} N^n_k \frac{x^k}{(1-x)^{k+1}} = \sum_{k} k! \mathcal{S}_n^{(k)} \frac{x^k}{(1-x)^{k+1}} $.

Il problema originario consisteva nel calcolare $ S_n(1/2) $, il quale è $ \displaystyle 2\sum_{k}k!\mathcal{S}_n^{(k)} $.

I primi valori, per $ n $ che va da $ 1 $ a $ 10 $, sono $ 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126,\dots $
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

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

Messaggio da dario2994 » 22 ago 2009, 21:02

a Maioc92: se non sai risolverlo non rosicare (non mi veniva nulla di piu´ gentile) ;) Ti posso assicurare che io l´ho risolto solo con i miei mezzi (che sono prettamente olimpici... per assicurartelo ti dico che sono di primo liceo ;))
A Feddystra: non posso leggere la tua dimostrazione perche' sono in un internet point e ho finito il tempo... appena torno a casa prometto di leggere tutto ;)

Avatar utente
Maioc92
Messaggi: 778
Iscritto il: 21 apr 2009, 21:07
Località: REGGIO EMILIA

Messaggio da Maioc92 » 22 ago 2009, 21:52

tu dici che il problema è olimpico: ti sfido a trovare un qualsiasi problema preso da una gara olimpica che sia simile a questo. Poi il fatto che si possa risolvere in modo elementare o no è un altro discorso. In ogni caso in attesa della dimostrazione elementare che dici di avere ho visto le 2 postate finora che di elementare hanno poco. Poi puoi pensare quello che ti pare, ma è meglio se non ti monti troppo la testa 8)
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 23 ago 2009, 18:46

Non so se è la stessa soluzione di Feddy, però si potrebbe fare così:

Definiamo $ $S_n(x)=\sum_{i=1}^{\infty} i^nx^i $ e vogliamo calcolare $ $S_n\left(\frac{1}{2}\right) $

Come si fa? Beh, $ S_n'(x)x+1=S_{n+1}(x) $ quindi calcolando le derivate di $ S_0(x) $ in $ $x=\frac{1}{2} $ possiamo calcolare ricorsivamente $ $S_n\left(\frac{1}{2}\right) $

ciaociao
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 23 ago 2009, 19:04

julio14 ha scritto:Non so se è la stessa soluzione di Feddy, però si potrebbe fare così:

Definiamo $ $S_n(x)=\sum_{i=1}^{\infty} i^nx^i $ e vogliamo calcolare $ $S_n\left(\frac{1}{2}\right) $

Come si fa? Beh, $ S_n'(x)x+1=S_{n+1}(x) $ quindi calcolando le derivate di $ S_0(x) $ in $ $x=\frac{1}{2} $ possiamo calcolare ricorsivamente $ $S_n\left(\frac{1}{2}\right) $

ciaociao
FeddyStra ha scritto:$ \displaystyle S_k(x)=x\frac{d}{dx}S_{k-1}(x) $.
Indichiamo per comodità con $ \vartheta $ l'operatore $ \displaystyle x\frac{d}{dx} $ e con $ \vartheta^{(m)} $ la composizione di $ \vartheta $ con se stesso $ m $ volte. A questo punto, possiamo dire che $ \displaystyle S_n(x)=\vartheta^{(k)}\left( \frac{1}{1-x} \right) $.
L'idea è la medesima: tutto ciò che segue nella mia dimostrazione è un modo per scrivere in forma chiusa la ricorsione.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 24 ago 2009, 13:00

Ci tengo a far sapere che chi ha scritto era il caro piever.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 24 ago 2009, 14:58

Lo si sapeva già: lui possiede il 30% degli account del forum! :lol:
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 24 ago 2009, 20:44

Maioc, olimpico vuol dire che si puo' risolvere con mezzi olimpici.
Il fatto che non sia mai stato incluso qualcosa di simile non vuol dire che non sia olimpico.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

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

Messaggio da dario2994 » 24 ago 2009, 21:45

Alur... sono tornato a casuccia con la mia tastiera quindi posso rispondere un po a tutti:
Maioc92: Cito solo quello che dice Skz perchè mi ha rubato le parole di bocca... ritenere un problema non olimpico perchè non viene da nessuna gara o è simile ad uno esistente mi pare davvero stupido :|

a Karl: ho tentato di seguire la dimostrazione, ma alcune cose mi piacerebbe se me le spiegassi (sono abbastanza ignorante in materia), così almeno le capisco:
Come fai a derivare (sempre che quelle siano derivate) V(x)?
Mi potresti dire che è la serie di taylor... che non l'ho mai capito...
Cosa sono $ C_{k,m}(z) $?
Ovviamente se qualcosa ti pesa spiegarmelo basta che mi linki qualcosina sull'argomento :)

A julio14: pur non sapendo come completare o dimostrare quanto hai detto lo ho capito in pieno ;) chiarissimo e anche conciso xD

A Piever/FeddyStra: mi sono arreso nella lettura (non mantenendo la promessa) perchè non capivo onestamente un emerito cazzo xD Purtroppo mi mancano molte conoscenze e la simbologia mi risulta un mistero xD Mi scuso ma tanto conoscendo l'autore e vedendo i risultati dò per scontata l'esattezza xD

p.s. lascio ancora un po di giorni poi scrivo la mia dimostrazione... che sicuramente è più facile da capire ;)

Rispondi