Retour à la page précédente

La récurrence à l'envers : solution

Soit P(n) une propriété définie sur N* et vérifiant

• i) P(1),
• ii) pour tout n de N*, P(n) => P(2 n),
• iii) pour tout n de N*, P(n+1) => P(n),

par quelle condition « minimale » remplacer la condition ii) ?

Si on note la nouvelle condition : pour tout n de N*, P(n) => P(f(n)), on voit que :

• f(n) = k n et f(n) = n + k (k entier fixé) conviennent
• f(n) de limite infinie ne convient pas (prendre f(n)=n pour tout n),
• f(n)>n pour tout n suffit, mais n'est pas nécessaire (prendre f(n)=2n pour n puissance de 2, f(n)=n sinon),

et on trouve la réponse dans Wikipedia : http://fr.wikipedia.org/wiki/Raisonnement_par_récurrence

prendre comme condition ii) : pour tout n de N* [ P(n) => il existe p de N, (n<p et P(p)) ].