Home

MPSI/PCSI

Maths

Analyse

Logique

Dans cette vidéo, Paul explique comment démontrer que pour tout entier n supérieur ou égal à 1, cet entier peut s'écrire comme la somme de puissances de 2 toutes distinctes. Il propose d'utiliser la récurrence forte pour prouver cette propriété. Il montre que pour k appartenant à 1n, k peut s'écrire comme la somme de puissance de 2 toutes distinctes en utilisant la décomposition de p, un nombre inférieur ou égal à n. Si n+1 est paire, l'idée est de trouver un nombre p et d'ajouter 1 à toutes les puissances de 2 de sa décomposition pour prouver que n+1 peut s'écrire comme une somme de puissances de 2 distinctes. Si n+1 est impaire, il suffit de réutiliser la décomposition de p pour montrer que n+1 peut s'écrire comme une somme de puissances de 2 distinctes. Ainsi, pour toute entière n supérieure ou égale à 1, on peut s'écrire comme une somme de puissances de 2 distinctes.

Salut c'est Paul, on se retrouve dans cette nouvelle vidéo sur la logique où on va attaquer un exercice un peu plus compliqué que les autres qui consiste à prouver quelque chose mais là on vous tient plus la main, vous devez trouver le type de raisonnement par vous même. Donc on doit démontrer que pour tout entier n supérieur ou égal à 1, cet entier peut s'écrire comme la somme de puissance de tous les distincts. Donc la première question qu'on doit se poser c'est quel type de raisonnement on va utiliser. Et on doit prouver ici une existence, on doit prouver que cette somme de puissance existe pour ce n donné. Donc cette décomposition de n ici existe. Et bien on pourrait penser d'abord par l'absurde que c'est une bonne piste. Comme ça là, prouver une existence par l'absurde c'est une mauvaise piste déjà parce que voilà, supposer que le nombre n'existe pas et on va pas pouvoir faire grand chose avec, c'est assez compliqué de manipuler une insertion logique qui dit que cette décomposition n'existe pas. Je vous le déconseille. Là on voit qu'on a des n, donc on pourrait se dire récurrence. Bon voilà, ça va être la bonne façon. Et une façon de se convaincre que la récurrence c'est la bonne manière c'est de passer directement de calculer un peu l'hérédité. On sait déjà que notre propriété n, donc on va dire que notre que notre somme de puissance de 2 existe pour un n donné ici. Donc notre n du coup c'est une somme de puissance alpha k, donc les alpha k sont tous distincts. Et on veut essayer de prouver que n plus 1 c'est aussi une somme de puissance mais un peu différente. Et bien en fait si on fait n plus 1 et qu'on utilise le fait qu'on sait que n est égal à la somme de puissance alpha k, on a 2 puissance 0 donc 1 plus n ici. Là on voit qu'on a un 2 puissance 0 donc la question ça va être est ce que 0 ici est dans ces puissances là et s'il y est comment on va faire pour se débrouiller dans ce cas là. On va voir comment on s'en sort. Mais donc ça paraît bien parti parce que là on n'a plus qu'à, c'est beaucoup plus simple en fait, on a juste à prouver que ici là ce 0 ne fait pas partie des alpha k. Et si quand même il en fait partie il faudrait prouver qu'il existe une autre décomposition du même style. On va voir ça ensemble. Et donc c'est parti. On commence par exemple par récurrence donc on énonce la propriété. La propriété il va falloir dire, c'est simple, là en fait on va utiliser une récurrence forte parce que vous allez voir on aura besoin après. Donc par quel que soit k appartenant à 1n, k peut s'écrire comme la somme de puissance de 2 toutes distinctes. Donc cette récurrence forte suppose que ce qu'on veut démontrer ici est vrai pour tous les cas inférieurs à n. Donc l'initialisation 1 égale 2 puissance 0 ainsi p2 est vrai. Et donc maintenant on prend n tel que p2n. Donc là comme une récurrence forte on prend k dans 1 n plus 1 dans ce cas là. Voilà un k dans 1 n plus 1 et dans le cas où si k appartient à 1n donc d'après pn, k peut s'écrire comme la somme des puissances de 2 toutes distinctes donc c'est bon. Vu que pn est vrai et maintenant on a le vrai challenge entre guillemets. C'est le k égale n plus 1. Donc en fait là l'astuce ça va être de distinguer si n plus 1 est paire ou impaire. Donc une bonne façon d'avoir des informations sur n, en fait là on voit que le cas n est paire ou impaire ça va être crucial parce que si n est paire, n va s'écrire deux fois un autre nombre. Donc en fait si cette décomposition existe pour cet autre nombre, il s'agit de la décomposition de n plus 1. Donc si cette décomposition existe pour cet autre nombre, on a deux fois cette décomposition donc on va pouvoir ajouter 1 à toutes les puissances de 2. Et s'il est impaire, là ça va être différent. Mais bon, paire ou impaire ça fait apparaître des 2, des fois 2, des divisibles par 2, donc les puissances de 2 ça a un rôle. Donc il existe p appartenant à n, donc tel que n plus 1 égale 2p. Voilà si n plus 1 est paire. Et donc comme p est inférieur ou égal à n, d'après pn, p peut s'écrire comme la somme de puissances de 2 toutes distinctes. Donc on exprime une telle décomposition. Donc il existe k appartenant à n étoiles, donc c'est un k différent ici, je vais juste appeler k parce que c'est plus simple. Et il existe alpha 1, alpha k, donc ça c'est le nombre de puissances de 2 par laquelle il va être... comment dire... c'est pour indexer les alphas de 1 à un certain entier, parce que ça on ne connaît pas le nombre des puissances. Appartient à n puissance k, ils sont distincts. Et p tel que p d'égale la somme de 1k des 2 puissances alpha i. Donc là c'est la décomposition en puissances toutes distinctes. Ainsi n plus 1, vu que n plus 1 est égal à 2p comme on a vu, on peut rajouter plus 1 à toutes ces puissances. Comme elles étaient toutes distinctes initialement, si on leur ajoute plus 1, elles sont toujours toutes distinctes. Avec les alpha 1 plus 1, alpha k plus 1, tous distincts. Et donc on a bien prouvé que n plus 1 s'écrit comme une décomposition, une somme de puissances de 2 distinctes. Sinon, dans le cas où n est impaire, n égale 2p plus 1, on va réutiliser cette décomposition, p égale i allant de 1 à k. Ce n'est pas le même p mais on utilise les mêmes notations. On reprend les notations du kpair, comme ça vous économisez du travail de notation. n plus 1 est égal à la somme de i allant de 1 à k de 2 puissances alpha i plus 1. Donc c'est notre 2p ici, plus 2 puissances 0. Ces puissances sont des nombres entiers, positifs. Elles sont supérieures ou égales à 0. Toutes ces alpha i plus 1 sont supérieures ou égales à 1. Ainsi, 0 n'est pas dans les alpha i plus 1. Donc, la famille alpha i plus 1, alpha k plus 1 et 0 sont distinctes. C'est une famille avec aucun égaux entre eux. On a bien décomposé n plus 1 en puissances de 2 distinctes. Pn plus 1 est vrai. Dans les deux cas, on a traité le k n, pair et impaire. Dans les deux cas, on avait une décomposition distincte. On a donc bien montré par récurrence que pour toute entière n supérieure ou égale à 1, on peut s'écrire comme une somme de puissances de 2 distinctes. C'est la fin de cet exo. On se dit à la prochaine fois!

Langage binaire

RELATED

Recommended videos

Utiliser les quantificateurs

Ecrire la négation

Equivalence et implication