Home

MPSI/PCSI

Maths

Analyse

Logique

Dans ce cours, Paul explique comment utiliser le raisonnement par récurrence pour démontrer une relation de récurrence forte. Il donne l'exemple d'une suite u1 définie par u1 = 3 et la somme des n premiers termes de la suite divisée par deux fois n pour toute n. On veut démontrer que pour toute n, u1 est égale à 3n. Paul définit une propriété pn (récurrence forte) pour montrer que tous les uk sont égaux à 3k et pas seulement u1 = 3n. Il effectue ensuite une initialisation (n = 1) et démontre l'hérédité pour n + 1 en deux cas: k appartient à 1 à n et k = n + 1. Lorsque k appartient à 1 à n, la propriété est prouvée car on sait que tous les uk sont égaux à 3k grâce à pn. Ensuite, en remplacant les ui par 3j, on obtient la somme des j allant de 0 à n, qui est égale à n(n+1)/2. Après avoir simplifié, on obtient 3n, ce qui prouve que pn + 1 est vrai. Ainsi, pn est vrai pour tout n et un est égal à 3n pour tout n.

Salut c'est Paul, et on se retrouve dans une nouvelle vidéo sur le raisonnement par récurrence, ici pour voir ce que c'est qu'une récurrence forte et dans quel cas l'utiliser avec cet exemple. Donc l'exercice commence par soit un, la suite définie par u1 égale à 3, et pour toute n, du coup un est la somme des n premiers termes de la suite divisé fois 2 sur n. Donc, et démontrer que pour toute n appartenant à n étoiles on a un égale à 3n. Donc ici vous l'aurez compris on a une relation de récurrence et on veut démontrer quelque chose pour toute n, et bien on va utiliser un raisonnement par récurrence. Donc on raisonne par récurrence, et donc on définit pn, donc la propriété pour toute n appartenant à n étoiles, donc le domaine sur lequel on veut démontrer, par pn égale quelque soit k appartenant à 1 de 1 à n, uk égale 3k. Alors pourquoi j'ai pas marqué directement un égale 3n et je me suis embêté avec ce quelque soit k appartenant à 1 à n? En fait c'est ça qu'on appelle la récurrence forte. Donc ça c'est une récurrence forte et c'est forte parce que dans la propriété on dit que ce qu'on veut montrer, donc un égale 3n, c'est vrai pour tous les n avant ce n, pour tous les k avant ce n, donc de 1 à n. Et pourquoi je vais en avoir besoin? En fait parce que dans l'hérédité je vais sûrement avoir besoin du fait que tous les uk sont égales à 3k et pas seulement un égale à 3n. Et pourquoi je pense ça? Parce que ici là, vous voyez, un plus un, la relation de récurrence, elle fait intervenir les uk ici de 1 à n. Donc c'est pour ça qu'on va en avoir besoin. Donc c'est parti, on fait l'initialisation. Donc pour n égale à 1, u1 égale à 3, égale à 3 fois 1 par définition grâce à l'énoncé, donc p1 est vrai. Voilà l'hérédité. On prend un n dans n étoiles tel que pn est vrai. On prend un k, donc on veut démontrer que quelque soit k appartenant à 1 à n quelque chose, donc on prend un k d'abord dans 1 n plus 1 parce qu'on veut démontrer pn plus 1, donc de 1 à n plus 1. Et là, deux cas. Soit k appartient à 1 à n, donc une récurrence forte, ça va toujours faire ça. L'hérédité d'une récurrence forte, tu as toujours deux cas de figure. Si k appartient à 1 à n, d'après pn, simplement, vu que pn est vrai, uk égale 3k. Tout simplement, mon a pn est vrai, donc on sait ça. Et là, on n'a plus qu'à traiter le k, où k égale n plus 1. Et là, uk est égal à un plus 1, du coup, est égal à 2 sur n la somme de j allant de 0 à n des uj. Donc là, je ne vous ai pas mis k parce qu'on a déjà utilisé k ici, donc j'ai remplacé le k de l'énoncé ici, le petit k, c'est une vraie muette, ce qu'on appelle, et en fait on peut la remplacer par une variable. Donc quand k est déjà pris, là, c'est une bonne idée de mettre j pour ne pas s'en mêler les pinceaux, pour être plus clair. Donc les variables, en général, qu'on met dans les sommes, c'est k, j ou l, ou i aussi, i quand il n'y a pas de complexe. Donc cette somme ici, là, les ui, on peut les remplacer par 3j, parce qu'on a pn qui est vrai, ainsi, là, on a la somme des j allant de 0 à n, qui est égale à n n plus 1 sur 2. Voilà, ça on doit le savoir absolument. Et on simplifie, ce qui nous donne 3n. Ainsi, pn plus 1 est vrai, et on conclut. Donc, quelque soit n appartenant à n étoiles, pn est vrai, et quelque soit n appartenant à n étoiles, on dit que cpn est vrai, un égale à 3n. Donc on a bien ce qu'on voulait montrer. Voilà, c'est la fin de cet exercice, et on se dit à la prochaine fois!

La récurrence forte

RELATED

Recommended videos

Utiliser les quantificateurs

Ecrire la négation

Equivalence et implication