[Maths] Somme exposants 2

Salut,

En calculant la complexité d'un algo (en version naïve) pour un futur logiciel GPL, j'ai remarqué que Somme[i=0 à n]( 2^i ) = 2^(n+1) - 1
où ^ est l'exposant.

ça se démontre très facilement par récurrence, mais existe-il une démonstration sans connaître d'avance le résultat ?

c'est équivalent à la suite:
U0 = 1
Un+1 = Un + 2^(n+1) pour n entier > 0

Voilà, sinon, pour info, la complexité de mon algo était:
Somme[i=1 à n] ( 2^i (2^n - 2^(n-i) + 1) 2^(n-i) ) = o( n 2^n ) quand n est grand.

Salut,
Somme[i=0 à n]( 2^i ) c'est tout simplement la somme d'une suite géométrique de raison 2 :
premier terme * ((1-raison^(nbre de terme))/(1-raison))

Ce n'est pas une recurrence que je fais :
Soit S=sum(i=0,n ; q^i)=1+sum(i=1,n ; q^i) avec q<>1
alors q*S=sum(i=0,n,q^(i+1))=sum(i=1,n+1,q^i)=sum(i=1,n,q^i)+q^(n+1)

Donc qS-S=q^(n+1)-1 donc S=[q^(n+1)-1]/[q-1]

Y a pas plus direct comme méthode, et il n'y a aucune récurrence.

PS : il n'y a aucune astuce, la démo est assez naturelle car on se débrouille pour que la 2e somme soit "décallée" d'un cran par rapport à la premiere pour qu'en soustrayant les 2, on élimine tous les termes "du milieu" afin de ne garder que le premier et le dernier terme...