Bonsoir
En travaillant sur la récurrence forte je me suis mis un doute sur l'hérédité de ma récurrence faible
pourriez vous me corriger merci
Récurrence faible
Initialisation : Montrons que la propriété est vrai au rang (généralement 0,1,p)
Hérédité et démonstration : supposons la propriété vrai au rang n et montrons la au rang n+1
CCl :La propriété est vrai pour n>=
Récurrence forte
Initialisation : Montrons que la propriété est vrai au rang (généralement 0,1,p)
Hérédité et démonstration : supposons la propriété vrai au rang k<=n et montrons la au rang n+1
CCl :La propriété est vrai pour n>=
Qu'en pensez vous ?
est ce correct et a peu près rigoureux devrais je déclarer les variables k et n je vous remercie
bonsoir
pour la faible j'aurais mis "soit n supérieur ou égal à n0, supposons etc"
et pour la forte "supposons la propriété vraie aux rangs n0, n0+1, ..., n, montrons la etc"
salut
lorsqu'on sait ce qu'est exactement le principe de récurrence il est sans intérêt de distinguer récurrence faible ou forte ....
principe de récurrence ::
soit P(n) une proposition dépendant d'un entier n ::
alors le principe de récurrence est de montrer que l'implication P(n) ==> P(n + 1) est vraie lorsqu'on suppose P(n) vraie
tout le problème est de savoir ce qu'on met dans P(n) :: parfois prendre n suffit, parfois il est nécessaire d'y inclure un certain nombre d'entiers précédent n .... (*)
ensuite on se moque du premier terme :: il existe des propriétés héréditaires toujours fausses
tout le pb évidemment, et une fois qu'on a l'hérédité, c'est de pouvoir initialiser pour pouvoir avoir une propriété P(n) vraie pour tout n supérieur à un certain entier
je n'ai plus d'exemple en tête ou on montre qu'une propriété est héréditaire pour tout n et qu'il faut initialiser à n = 3 pourtant ...(alors que l'hérédité est vraie sans condition sur n)
mais voici un exemple ou la démonstration de l'hérédité impose une condition sur n ::
P(n) :: 2n >= n2
2n+1 = 2.2n >= 2n2
or 2n2 - ( n + 1)2 = n2 - 2n - 1 = (n + 1)2 - 4n - 1
et (n + 1)2 - 4n - 1 >= 0 <== n > 4
ici montrer l'hérédité impose une condition sur n : n > 4
et pourtant P(4) est vraie
pour revenir à (*) et revenir à ce qu'on appelle la "récurrence forte" un exemple ::
pour le suites récurrentes d'ordre m il est parfois nécessaire de prendre pour propriété ::
P(n) :: pour tout k =< n : P(k) est vraie
c'est en général essentiellement un problème de français pour bien définir ce qu'est la proposition P(n)
...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :