Fonction partie entière
Bonjour,
J'essaye actuellement de résoudre la complexité d'un algoritme informatique.
Mon problème est que je n'arrive pas à trouver la valeur de :
n
Σ E(i/2)
i=1
en fonction de n.
J'ai consulté la page sur Wikipédia consacrée à la fonction partie entière, sans résultat...
Est-ce possible de réduire cette somme ?
Merci à vous de m'aider.
Tu verras aisément que ta suite ressemble à :
0, 1, 1, 2, 2, 3, 3, 4, 4, 5 ...
On va donc distinguer n pair où ça s'arrête après n/2 après avoir additionné 2 fois tous les nombres de 1 à n/2 - 1. On trouve n²/4 en appliquant la formule classique de la somme des nombres de 1 à N = N(N+1)/2
Pour les impairs, c'est 2 fois tous les nombres de 1 à (n-1)/2 et ça donne (n²-1)/4
En posant In={impairs<=n}
Or, il est plus que classique que 1+2+...+n=n(n+1)/2 et card(In)=E((n+1)/2) (obtenu par tatonnement il y en a environ n/2, reste à ajuster).
Ainsi
Sn=n(n+1)/4-(n+1)/4=(n²-1)/4 si n est impair
Sn=n(n+1)/4-n/2=n²/4 si n est pair
En une seule formule :
avec partie entière : Sn=E(n²)/4
avec puissance de -1 : Sn=n²/4-(1-(-1)n)/8.
