Raisonnement par récurrence

Toto.le.zero · May 2006

Bonjour à tous, j'ai un problème d'ordre logique qui me turlupine et qui concerne le raisonnement par récurrence.

En fait, j'ai besoin de montrer par récurrence une propriété qui doit être vérifié pour tous les entiers plus petits qu'un certain nombre entier bien défini, disons 1000.

Je veux montrer par récurrence, que pour tout n inferieur ou égal à n ma propriété est vraie. Pourquoi le raisonnement par récurrence est légal dans ce cas quand on veut montrer une proposition jusqu'à un entier fixé ? merci de vos réponses.

Toto.le.zero · May 2006

correction: " je veux montrer par récurrence que pour tout n inferieur ou égal à 1000"

Yama · May 2006

Où est le probleme?

Tu vas montrer P(0) Vraie

Puis pour tout n compris entre 0 et 1000, P(n) implique P(n+1)

Toto.le.zero · May 2006

ouais mais bon si n à la malheur de valoir n=1000 alors P(1000) implique P(1001)

guiguiche · May 2006

Pour tout n compris entre 0 et 999 (puisque P(999)=>P(1000)).

Toto.le.zero · May 2006

mouais.

jp8 · May 2006

Pourquoi penses tu que la propriété P(n) n'est plus vraie pour n > 1000 ?

Si c'est la cas, l'hérédité de la propriété (P(n) implique P(n+1)) ne sera plus vraie à partir d'un certain rang...

Toto.le.zero · May 2006

ok donc formellement, le cheminement d'une demonstration par un telle recurrence est analogue à une recurrence banale c'est bien ça ?

Crou! · May 2006

Question bête : si tu sais que ce n'est plus valable à partir d'un certain rang, c'est donc que tu es en mesure de montrer P(1000) ???

Tu initialises avec P(1000) et ensuite, tu pourrais peut-être faire une récurrence descendante ?

Ce qui me paraît bizarre dans cette histoire c'est que si montrer P(1000) ne pose pas de problème, je ne vois pas (a priori) pourquoi on ne montre pas directement P(n), pour un entier n entre 1 et 1000 directement....

Après tout, tout dépend de la tête de P....

Toto.le.zero · May 2006

j'ai jamais dit que montrer P(1000) ne posait pas de problème.

Crou! · May 2006

ben je m'en doutais un peu ! Je soumettais cette idée au cas où la récurrence descendante serait possible, c'est tout (c'est plus joli que de devoir limiter n dans la récurrence "classique").

Te voilà donc forcé de montrer P sur un sous-ensemble de N comme cela t'est suggéré...