Démonstration par récurrence

Loading Viewer…

Démonstration par récurrence 1 Principe de récurrence Principe de récurrence L’idée est la suivante : Soit une ligne infinie de dominos. Le premier domino fait tomber le second, c’est l’étape d’initialisation ou d’ancrage. Le raisonnement par récurrence nous affirme que si le domino n tombe (hypothèse) alors il fera tomber le domino n + 1 et ceci pour n quelconque, c’est l’hérédité. La récurrence se base sur les axiomes de Péano qui définissent l’ensemble des nombres naturels de la façon 1. L’élément appelé zéro et noté 0 est un entier naturel. 2. Tout entier naturel n a un unique successeur, noté s(n) qui est un entier naturel. 3. Aucun entier naturel n’a 0 pour successeur. 4. Deux entiers naturels ayant le même successeur sont égaux. 5. Si un ensemble d’entiers naturels contient 0 et contient le successeur de chacun de ses éléments, alors cet ensemble est N. Le cinquième axiome traduit le principe de récurrence des nombres naturels. PRINCIPE DE RÉCURRENCE Avant de définir ce principe, il faut définir ce qu’est une proposition. Une proposition P est une expression mathématique qui peut être soit vraie soit fausse. Le principe de récurrence sur une proposition P n (proposition qui dépend d’un nombre naturel n ) se fait en trois étapes distinctes, qui sont : i) L’ancrage ou initialisation : On vérifie que P n est vraie pour n = n 0 . a ii) L’hypothèse : On postule que P n est vraie. iii) L’hérédité : On montre que si P n est vraie pour n quelconque cela implique que P n+1 l’est P n ⇒ P n+1 ou encore si P n alors P n+1 Si ces trois points sont vérifiés, on dira que la proposition P n est vraie pour tout nombre naturel n . a. En général, n 0 est égal à 0 ou à 1, mais ce n’est pas une nécessité, n 0 est l’indice du premier terme apparaissant dans l’énumération. P n est en général une égalité ou une inégalité indicée par n .

Démontrer par récurrence que la somme des n premiers nombres de N∗ est donnée par La somme des 10 premiers nombres de N est 10+9+8+7+6+5+4+3+2+1 = 55. En appliquant la formule donnée, on obtient la même chose, S 10 = 10(10+1) Il faut démontrer que cette formule est valable pour tout n appartenant à l’ensemble des nombres naturels N. On commence par décider de la proposition P n . Ici le plus vraissemblable est : On commence par la procédure d’ancrage en vérifiant que la proposition est vraie pour n = 1 (premier élément de l’ensemble N∗ ). En effet Notre hypothèse sera d’affirmer que P (n) : Pour l’hérédité, on va calculer P (n + 1) de la manière suivante. On a vu plus haut que la somme des 10 premiers nombres donnait 55. Si l’onvoulait la somme des 11 premiers nombre, on calculerait 55 + 11 = 66. Donc, P (10) + 11 = P (11). En posant m = n + 1, on retrouve exactement la structure de départ, à savoir On vient de vérifier l’hérédité en prouvant que P (n) impliquait P (n + 1). Aurement dit que la formule donnant la somme des n premiers termes de N est juste pour tout n .

Montrer à l’aide de raisonnements par récurrence que la suite est croissante et bornée. Ensuite, calculer la limite de la suite, c.-à-d. u n pour n → ∞ à l’aide de la méthode du point fixe. Une suite bornée est une suite minorée par un nombre m et majorée par un autre nombre M . Il semble évident que la suite donnée est croissante, ce qu’il faudra bien sûr le démontrer. Je vais choisir m = 0 et M = 3. J’ai décidé de choisir M = 3 car en calculant quelques termes de la suite, cela semble logique. Attention ! 3 n’est pas la limite de la suite mais simplement un nombre qu’aucun élément u n ne dépassera. J’aurais pu choisir M = 1012 ! Démonstration de la croissance La démonstration peut se faire en vérifiant que u n+1 − u n est plus grand que zéro pour tout n , mais également par récurrence. Il faut décider de la proposition P n que l’on va utiliser. On choisit On commence par vérifier l’ancrage. Dans ce cas n = 0 : L’hypothèse de récurence est tout simplement P n : L’héritage se fait en montrant que P (n) =⇒ P (n + 1). On commence par écrire l’hypothèse, Cette hypothèse est considérée comme juste, donc en ajoutant 4 de chaque côté de l’inégalité, celle-ci ne change pas, le membre de gauche sera toujours plus grand que le membre de droite. Pourquoi j’ajoute 4 ? u n+1 + 4 > u n + 4. Je prends la racine carrée de chacun des membres. La racine carrée est une fonction croissante, dons elle conserve le sens d’une inégalités. Maintenant si l’on regarde bien, on a en fait L’implication a fonctionné, la démonstration est terminée.

La suite est bornée La suite est strictement croissante donc elle est minorée par u 0 = 0. En effet il ne peut pas y avoir de terme plus petit que 0. Il faut donc uniquement démontrer que M = 3 est un majorant de cette suite. On utilise à nouveau la récurrence avec la proposition suivante : L’ancrage est vérifié : L’hypothèse est à nouveau P (n). Pour l’héritage, j’ajoute 4 et je prends la racine carrée : La dernière ligne est en fait L’implication a à nouveau fonctionné car de P (n) on est arrivé naturellement à P (n + 1). Pour calculer la limite ℓ de la suite on utilise le fait qu’elle est strictement croissante et bornée ! Etant toujours croissante mais ne dépassant jamais une certaine valeur, elle va forcément s’ »écraser » en un point limite. Mais comment calculer ce point ? On utilise une variante du théorème du point fixe. Notre suite est donnée par u n+1 = u n + 4. Pour n très grand, on aura forcément u n+1 très proche du u n . On va donc poser u n = u n+1 = ℓ ℓ2 − ℓ − 4 = 0 L’unique solution positive de la dernière équation quadratique est C’est la limite que l’on désirait. Fig. 1 – La suite implicite

est croissante et bornée. L’exercice qui suit a été donné en 1999 à l’examen Analyse I aux élèves de la section de physique de l’EPFL. Montrer que les deux suites (x n ) et (y n ) définie par x n+1 = x n y n , convergent vers la même limite. Il faut commencer par analyser les suites données. Le terme général de la suite (x n ) donne la moyenne géométrique des valeurs x n et y n . Le terme général de la suite (y n ) donne la moyenne arithmétique de x n et y n . On sait que la moyenne géométrique de deux nombres différents est plus petite que leur moyenne arithmétique. Si les nombres sont identiques, les deux moyennes coïncident. Voilà la démonstration : Démonstration. Soit l’expression suivante, vraie pour tout a et b de R plus grand que zéro : On développe et on réarrange les termes : La moyenne arithmétique est supérieure à la moyenne géométrique, ce pour tout a , b plus grand que x n est défini comme étant une moyenne géométrique et y n est défini comme moyenne arithmétique. De ce fait on va prétendre que x n < y n et ce pour tout n de N. On va étudier par récurrence la proposition P (n) : x n < y n (hypothèse) et voir ce qu’elle peut nous apprendre. Pour l’ancrage, il n’y a pas de problème, on nous dit dans l’énoncé que x 0 est plus petit que y 0 . L’hypothèse étant posée, on passe à l’hérédité que l’on va implémenter en deux étapes.

La première de étapes est la suivante : xn · xn < y n · xn On sait maintenent que pour tout n , on a xn < x n+1 . La deuxième étape est Donc, pour tout n , on a y n+1 < y n En utilisant la démonstration sur l’ordre des moyennes géométrique et arithmétique vue plus haut, on peut finalement écrire que : 0 < x 0 < x n < x n+1 < y n+1 < y n < y 0 . Ce résultat est important, car on peut en tirer que (xn ) est strictement croissante et bornée supérieurement par y 0 , de même, on peut déduire que y n est strictement décroissante et bornée inférieurement par x0 . Le calcul de la limite utilise la méthode du point fixe et le fait que toute suite strictement croissante et bornée possède une limite. Ici, on a deux suites strictement monotones qui ont la même limite. On a ainsi démontré que les deux suites (x n ) et (y n ) convergent vers la même limite.

Soir pour n ∈ N le nombre de Fermat Fn := 2(2 ) + 1. Démontrer, pour n ∈ N∗ , la relation de récurrence On commence toujours par calculer quelques termes. Pour commencer utilisons la définition du nombre de Fermat Fn := 2(2 ) + 1 : F 0 := 2(2 ) + 1 = 3 F 1 := 2(2 ) + 1 = 5 F 2 := 2(2 ) + 1 = 17 F 3 := 2(2 ) + 1 = 257 F 4 := 2(2 ) + 1 = 65537 A présent on utilise F n = F k + 2 qui est la relation qu’il faut démontrer à l’aide de la définition F 2 = F 0 · F 1 + 2 = 17 F 3 = F 0 · F 1 · F 2 + 2 = 257 F 4 = F 0 · F 1 · F 2 · F 3 + 2 = 65537 On voit que ça marche » ! On cherche à former la proposition de récurrence P n . Le plus simple est de récrire F n = F n − 2 = F 0 · F 1 · F 2 …F n−1 La proposition à démontrer par récurrence est par conséquent F n − 2 = F 0 · F 1 · F 2 …F n−1 . L’ancrage a largement été vérifié ci-dessus avec les calculs de F1 à F4 . L’hypothèse de récurrence est P n : F n − 2 = F 0 · F 1 · F 2 …F n−1 . On suppose que P n est vraie. Pour vérifier l’hérédité, il faut montrer que P n implique P n+1 .

F n+1 − 2 = (F 0 · F 1 · F 2 …F n−1 ) · F n (On multiplie par Fn des deux côtés) = (F n − 2) · F n (On utilise l’hypothèse de récurrence) = 2(2 ) + 1 − 2 2(2 ) + 1 (On utilise la définition du nombre de Fermat) = 2(2 ) − 1 2(2 ) + 1 = |2(2 {z) + 1} −2

Démontrer par récurrence la formule du binôme de Newton : x, y ∈ R et n ∈ N∗ La proposition de récurrence, qui est de manière générale l’hypothèse de récurrence, est La démonstration par récurrence commence toujours par l’ancrage. Il faut montrer que P (1) 1 est une proposition vraie. Cela donne, L’hérédité s’implémente, en partant de l’hypothése qui est considérée comme vraie. On multiplie de chaque côté par (x + y) afin d’obtenir (x + y)n+1 . x k y n−k (x + y). On commence par distribuer la somme dans le facteur (x + y), On procède à une petite étape de réécriture, x (k+1) y (n+1)−(k+1) + A présent on incrémente k de 1 dans le premier des deux membres ci-dessus. Cela implique que k +1 devient k , que k devient k − 1. En faisant ceci on obtient des termes x k y (n+1)−k identiques dans les deux sommes. Maintenant, les indices des symboles sommes sont différents. Pour y remédier, on extrait de la première somme le terme d’indice k = n + 1 et de la deuxième somme, on extrait le terme d’indice 0, x k y (n+1)−k + y n+1 . On peut mettre en évidence de la manière suivante, x k y (n+1)−k + y n+1 . 1. L’ensemble de départ des indices est N∗ et non N.

En utilisant une identité d’analyse combinatoire 2 , on arrive à x k y (n+1)−k + y n+1 . Pour la dernière étape, il suffit de voir que le facteur x n+1 est le terme d’indice k = n + 1 de la somme et que que le terme y n+1 est le terme d’indice k = 0 de cette même somme. On peut donc les inclure sous le symbole somme pour finalement arriver à l’expression : L’hérédité a bien fonctionné car en partant de l’hypothèse P (n), on a pu obtenir de manière logique, la proposition P (n + 1). On a : Cela signifie que le binôme de Newton est valable pour toute valeur de n , si n ∈ N∗ .

EXCM-001-recurences.pdf ¡ n ¢ ¡n ¢ ¡n+1¢

Démonstration par récurrence

Subscribe