La récurrence forte

[Mikaël (TS)]

Bonjour aux professeurs du forum.

Je souhaiterais comprendre la démonstration du principe de la récurrence forte, qui d'après mes diverses recherches documentaires, peut être déduit du principe de récurrence simple.

Principe de récurrence forte
On considère une proposition \(P(n)\) définie sur N.
\(Q(n)\) est la proposition : "Pour tout entier naturel k tel que \(n_0\leq{k}\leq{n}\), \(P(k)\)".
Si \(P(n_0)\) est vraie et si "\(Q(n)\) implique \(Q(n+1)\)" est vraie alors pour tout entier naturel,\(P(n)\) est vraie.

Donc, d'après ce qu'ils disent, démontrer P(n) par récurrence forte revient à démontrer Q(n) par récurrence simple.
Mais comment justifier cela ?

Je reste en attente d'une réponse... merci !

[SoS-Math(30)]

Bonjour Mikaël,

Je t'indique ce lien qui doit répondre à ta question :
http://mpsi.daudet.free.fr/maths/polys/ ... eForte.pdf

SoSMath

[SoS-Math(34)]

Bonjour MIckaël

Une récurrence forte, c'est sensiblement pareil dans la forme que la récurrence "faible" :

1°) On montre que la propriété Pn est vraie pour n=0 ( ou 1, ou 2 .... )
2°) On suppose que la propriété est vraie, pour tous les indices k allant de 0 à n, puis on montre qu'elle est vraie pour n+1

Cela peut être utile pour montrer par exemple pour une certaine suite u que , pour tout n, u(n+1) = u(n) + u(n-1).

On a besoin de la récurrence forte dans ce cas là car pour montrer la propriété au rang (n+1), on a besoin que ce soit vrai pour les indices précédents n et n-1 !

Bonne continuation
Sosmaths