Estimation d'une somme

par **The Void** » 03 Jan 2011, 19:04

Bonjour,

Je cherche à donner un equivalent (ou O) simple de:

quand

En majorant k par n, on trouve un O(n), mais je suis presque sûr que c'est O(

), savez vous comment le démontrer? (j'ai pensé à une inégalité du type Hoeffding mais bof..)

par **geegee** » 03 Jan 2011, 21:21

par **Ben314** » 03 Jan 2011, 23:59

Salut,
Si

alors

et on doit trouver une bonne approximation en utilisant le fait que

(stirling)

par **The Void** » 04 Jan 2011, 10:57

Ben314 a écrit:

Comment trouves tu cette égalité?

par **Ben314** » 04 Jan 2011, 11:03

En regardant d'un peu plus prés, on a :

donc

par **Ben314** » 04 Jan 2011, 11:08

The Void a écrit:Comment trouves tu cette égalité?

En utilisant le fait que

puis en multipliant par

et en sommant de

à

.