Salut,
Une récurrence "usuelle", ça consiste à montrer qu'une certaine propriété
)
(dépendant d'un entier
) est vrai pour un entier
donné puis que, si elle est vrai pour un certain entier
alors elle est aussi vraie pour l'entier suivant
. Et on en déduit que la propriété est vraie pour tout les entiers
.
Dans une récurrence "forte", on initialise de la même façon (i.e. on montre que c'est O.K. pour un certain
) mais ensuite, pour l'hérédité, on suppose que, pour un certain
donné, non seulement la propriété est vrai pour ce
, mais qu'elle est aussi vrai pour tout les entiers
tels que
. Et la conclusion est bien sûr la même.
Et en fait, c'est la même chose qu'une récurrence usuelle, mais avec la proposition
)
qui dit "
)
est vraie pour tout
tels que
"
Et là, dans ton exo, tu as effectivement besoin d'un truc de ce style vu que la formule du 3) te dit que, pour montrer quelque chose concernant
, il faut non seul savoir des choses concernant
mais aussi
. Et ça, ça s'appelle en général une "récurrence double" : on suppose que le bidule à montrer est vrai pour les
deux termes qui précèdent celui où on fait le raisonnement. Et bien sûr, dans ce cas là, il faut, au départ, montrer "à la main" que la propriété est vraie pour les
deux premiers termes pour ensuite pouvoir utiliser l'hérédité.
EDIT : pas vu le message de Catamat avant d'envoyer le mien . . .
.