Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

récurrence forte recurrence faible

Posté par
oubah
18-02-14 à 22:34

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 n_{o} (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>=n_{0}

Récurrence forte

Initialisation : Montrons que la propriété est vrai au rang n_{o} (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>=n_{0}


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

Posté par
lafol Moderateur
re : récurrence forte recurrence faible 18-02-14 à 22:38

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"

Posté par
oubah
re : récurrence forte recurrence faible 18-02-14 à 22:45

Merci j'en prends note

Posté par
carpediem
re : récurrence forte recurrence faible 19-02-14 à 11:17

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 :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !