Une démonstration par récurrence

bonjour dans cette vidéo on va faire quelque chose d'assez important on va s'entraîner à utiliser le raisonnement par récurrence en fait on va démontrer une formule par récurrence alors le raisonnement par récurrence un raisonnement vraiment très très utile quand tu as par exemple l'intuition d'une formule si tu fait quelques essais et tu te rends compte que telle formule est probablement vrai eh bien il faut le prouver que c'est vrai et ça on peut souvent le faire par récurrence alors pour ne pas parler trop dans le vide et de manière trop abstraite je vais prendre tout de suite un exemple les prendre une fonction s de haine ou n est un entier naturel positif et on va dire que cette fonction la sdn donc l'image de haine par cette fonction là eh bien c'est la somme de tous les nombres entiers somme de tous les entiers positif quand je dis positif ça veut dire non nul ça veut dire positif et non nul donc à partir de 1 jusqu'à n jusqu'à n voilà alors pour bien visualiser ce que c'est que cette fonction l'arbre calculer une de ses valeurs par exemple s ii iii et bien c'est la somme de tous les anciens positif jusqu'à 3 donc le premier entier positif c'est un plus le deuxième qui est 2 + 3 qui est le suivant et je m'arrête là puisque je vais jusqu'à n donc s 2 3 c'est un plus de +31 plus de +3 ça fait 6 tu veux on peut en calculer un deuxième on peut calculer s24 s24 ça sera un + 2 + 3 + 4 donc ça fait 6 + 4 ça fait 10 voilà donc s 2 nc la somme de tous les anciens positif jusqu'à n donc c'est un + 2 + 3 ainsi de suite jusqu'à m va démontrer dans cette vidéo que s de haine notre but ça va être de démontrer que s ii ncn facteur de haine + 1 / 2 voilà donc ça c'est notre but ici de démontrer cette formule alors pour ça on va utiliser donc le raisonnement par récurrence qui seront quoi ça consiste ce raisonnement par récurrence et bien c'est un raisonnement qui va se dérouler en deux étapes deux étapes toutes les deux très importantes je vais faire un prêt ici pour séparer la première étape l'étape 1 elle va consister à trouver un entier une valeur de haine pour lequel cette formule-là est vrai donc c'est juste un cas particulier comprend en général on prend le premier cas la première valeur de haine possible donc on va prouver en fait un cas initial inca initial voilà donc un cas de départ qui est pas forcément la première valeur c'est pas forcément inégal 1 ça peut être un autre cas et la deuxième étape c'est celle qui est vraiment porte le nom de récurrence la deuxième étape c'est la récurrence en fait on va supposer que la propriété qu'on cherche à démontrer est vrai pour un certain entier suppose que la propriété est vrai pour un entier un certain entier donc on suppose que la propriété est vrai à un moment d'en donner donc pour un entier k1 entier cas positifs et on prouve que si cette propriété vrai pour k alors elle est vraie alors elle est vraie pour l'entier suivant donc pour capucins on prouve que la propriété est vrai aussi pour capucins est vrai pour l'entier cac +5 et l'entier suivant alors on va observer un petit peu ce raisonnement donc ici je vais prendre mes entier donc je vais avoir l'entier un ensuite j'ai 2 ensuite j'ai trois ensuite g4 ensuite j'ai 5 et ainsi de suite lors la première étape consiste à prouver que notre propriété est vrai un certain moment alors on va dire que par exemple on a réussi à prouver que la propriété vrai pour l'entier 1 donc ça ici on sait que c'est vrai grâce à notre première étape ci et puis ensuite grâce à notre deuxième étape qui nous dit que si la propriété vrai à un moment donné alors elle est vrai au cran suivant donc pour l'entier suivant est bien ici commence et que 1 est vrai ben d'après ce qui est démontré ici c'est vrai aussi pour le 2 pour qu'à égal de l est vrai aussi et puis si elle est vraie pour qu'à égal 2 et bien les vrai aussi pour le suivant donc les vrais pour qu'à égal 3 si elle est vraie pour qu'à égal 3 elle est vrai aussi pour qu'à égale 4 d'après toujours cette partie là de notre raisonnement tu vois que de cette manière là en fait on démontre que la propriété vrai pour tous les entiers naturels à partir bien sûr de notre cas initial voilà alors ça c'est le raisonnement par récurrence maintenant on va l'appliquer à notre cas ici donc on va d'abord passer à l'étape 1 et on va calculer s-21 alors s-21 s-21 c'est la somme de tous les entiers positif jusqu'à 1 donc c'est un ensuite je vais regarder cette formule là je vais remplacer n parent alors cette formule là elle me donne un facteur 2 1 + 1 / 2 alors ça nous donne un x 2 sur 2 2 sur 2 ce qui est égal à 1 donc tu vois que pour un la formule qu'on cherche à démontrer et elle marche 1 c'est la bonne formule mais elle nous donne bien la valeur de s-21 donc notre proposition elle est vraie pour n égale 1-1 voilà alors maintenant on va passer à la deuxième étape qui est celle ci un celle là donc on va prendre un entier cas positifs et on va supposer que notre proposition est vrai pour cette entier donc on suppose que s de cas est-ce de cas bien être donnée par cette formule là c'est donc qu'à facteur de cas plus un sur deux et maintenant on va calculer est-ce de capucins donc s de capucins en fait c'est donc un plus de plus ainsi de suite jusqu'à plus qu'à +1 voilà ça ça veut dire que je fais tout la somme de tous les entier en partant de 1 jusqu'à cas plus évidemment en fait le terme qui est avant cac +1 ccar donc je peux même l'écrire comme ça si tu veux un + 2 + ainsi de suite jusqu'à plus qu'à +4 plus et faire apparaître le cas ici c'est intéressant parce que ça montre bien que ici ce qu'on a ici en fait c est de 40 c'est la somme de tous les entiers de 1 jusqu'à kds deux cas on peut l'écrire comme ça kafka plus un sur deux puisque ça c'est notre hypothèse de récurrence donc finalement notre s2 capucins je vais pouvoir l'écrire comme ça c'est k fois cac +1 le tout divisé par deux plus qu'à +1 voilà j'ai juste remplacer cette partie là par la valeur qui nous est donnée par la formule puisque on va supposer que c'était vrai et donc maintenant je vais mettre ces termes là au même dénominateur pour faire la somme ça me donne qu'à facteur de cas plus un plus deux fois cas + 1 le tout divisé par deux alors maintenant on peut s'apercevoir qu'ils si on a un facteur commun dans les deux termes de notre somme capucins et cac +5 on trouve ici donc je vais le mettre en facteur ce facteur commun ça va me donner cas plus un facteur de alors il va me rester ce cas qui est là et ce deux pieds là donc ça va donner fac cas plus un facteur de cas +2 le tout divisé par deux alors maintenant ici j'ai +1 et la gca plus un plus un donc je vais pouvoir réécrire ça comme ça alors je vais me mettre ici pour reprendre un peu de place gk plus un facteur de je vais mettre des crochets comme ça puisque je vais avoir ici qu'à plus un plus un voilà le tout divisé par deux et donc là on fait ce qu'on a fait c'est exprimer s2 capucins sous cette formule à qui est exactement la même que celle ci si tu remplaces ici n parc à +1 tu vas retrouver exactement ça donc finalement ce qu'on a fait c'est que on va démontrer que s-21 était vrai on a démontré que si c'était vrai pour un certain entier cas alors c'était vrai aussi pour le suivant et du coup on peut en conclure qu'on a démontré par récurrence que la somme de tous les entiers positif jusqu'à n est bien cn fois n + 1 sur 2