Comptes Rendus MATh.en.JEANS 99-10

Soit la propriété suivante

P( n) :  A( p) = 2^p-1 pour p n-1

Que se passe t-il au rang n ? [Prenons P( n) comme hypothèse de récurrence et montrons que P(n) implique P(n+1) ].

Selon les résultats précédents, nous avons :

A(n) = 1 + A(1) + A(2) + Š + A(n-1)

Or d'après l'hypothèse de récurrence [P( n)], nous avons : A(1) = 2⁰ et A(2) = 2¹ [et ... ] et A( n) = 2^n-2, soit [d'où] :

A(n) = 1 + 2⁰ + 2¹ + Š + 2^n-2.

Nous reconnaissons 2⁰ + 2¹ + Š + 2^n-2 comme la somme d'une suite géométrique de raison 2, [sa valeur est (2.2^n-2-1)/(2-1) soit 2^n-1-1]. Donc :

A(n) = 2^n-1,

[ ce qui, avec l'hypothèse P( n), entraîne P( n+1) ]

La propriété [P(n)] est [donc] héréditaire : [on a P( n), entraîne P( n+1) ].
Elle est vraie pour n = 1, donc elle est vraie pour tout n1.

On en conclut ainsi que la propriété A(n) = 2^n-1 est vraie pour tout  n ^*.