Bonjour,

Dans la rédaction d'une récurrence ou l'on veut vérifier une propriété P(n.), pourquoi on note parfois dans l'hérédité qu'on suppose qu'il existe un entier k tel que P(k) est vraie alors que d'autres fois on note tout de suite qu'on suppose P(n.) est vrai ?

Par exemple dans :

Initialisation :
u0 = 2 d'où u0 > 0
La propriété est vraie au rang 0, il y a donc initialisation.

Hérédité :
Supposons la propriété vraie au rang k, c’est à dire : uk > 0
Et montrons qu’alors, la propriété est vraie au rang p+1, c’est à dire : uk+1 > 0
uk > 0 Donc : 5uk + 4 > 0 D'où uk+1 > 0 et il y a donc hérédité.

Conclusion : Par récurrence, la propriété est vraie pour tout n.

Bonjour,
c'est le choix de la lettre qui te perturbe ?
Parce qu'elle est muette, donc peu importe.
Pour l'hérédité, tu peux supposer H_k (pour un entier k fixé) et chercher à montrer H_{k+1} ou supposer H_n (pour un entier n fixé) et chercher à montrer H_{n+1}...

Pour l'hérédité ma prof fait comme ça :

On suppose pour un entier naturel n quelconque fixé que n+1 > 0 : P(n). Montrons que P(n) => P(n+1)
Par hypothèse de récurrence, n+1 > 0
=> n+2 > 1
=> n+2 >0 (par transitivité)

Donc le choix de la lettre importe peu.
Je pensais que comme on voulait démontrer une propriété Pn c'était un peu bizarre de reprendre un indice "n" dans l’hérédité pour démontrer que Pn+1 vrai.

Merci.

Le 28 mars 2021 à 17:49:08 Kikile1kiki a écrit :
Donc le choix de la lettre importe peu.
Je pensais que comme on voulait démontrer une propriété Pn c'était un peu bizarre de reprendre un indice "n" dans l’hérédité pour démontrer que Pn+1 vrai.

Merci.

Tu as raison que ça peut paraître un peu bizarre, et c'est pour ça que certains profs préfèrent utiliser une lettre différente pour éviter toute ambiguïté. Mais techniquement, c'est pas problématique de réutiliser la lettre "n".

La propriété qu'on veut démontrer, ce n'est pas « P(n) », c'est « pour tout n, P(n) ».
On dit que la variable n est liée par le quantificateur "pour tout"; ce qui veut dire qu'on peut la renommer sans changer le sens de la propriété :
« pour tout n, P(n) »
⇔ « pour tout k, P(k) »
⇔ « pour tout ☭, P(☭) »

Autrement dit, cette variable n « n'existe pas vraiment », elle n'a pas de sens en dehors de l'assertion « pour tout n, P(n) ». C'est pour ça qu'on s'autorise à réutiliser le même nom "n" dans l'hérédité pour désigner autre chose.

Dans l'hérédité, quand tu dis « Supposons la propriété vraie au rang n », là tu es en train d'introduire une nouvelle variable n (une variable libre), et dans la suite de ta preuve tu auras le droit de dire des choses à propos de ce n.

Un autre exemple qui te parlera peut être où on rencontre des variables libres et liées :

Parfois on définit une fonction en disant « Soit f la fonction définie par f(x) = 2x-1 »
Ce x est une variable liée / muette, ça ne désigne pas un x en particulier, c'est juste un nom. Si on remplace tous les x par des y, ça reste la même fonction.

Si ensuite on dit « Soit x un nombre réel positif tel que f(x) = x² », alors là on a introduit un nombre qu'on appelle x, et on va pouvoir par exemple se demander quelle est sa valeur. Ce "x" n'a rien à voir avec celui qui a servi à définir la fonction f. C'est une variable libre.