NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 30/12/2020 Orientation générale  DicoMot Math Atlas Actualités M'écrire Barre de recherche DicoCulture Index alphabétique Références Brèves de Maths
	LOGIQUE
Débutants Logique	RAISONNEMENT			Glossaire Démonstrations Glossaire Logique
INDEX Logique Itérations	Raisonnements	Démonstrations	Récurrence	Automatisation
		Sommaire de cette page >>> Approche comparée >>> Somme des nombres entiers >>> Formalisation >>> Exemples de démonstrations

Démonstration par induction

ou

Raisonnement par récurrence

ou, plus précisément

Démonstration par induction sur une formule de récurrence

Le raisonnement par récurrence est une forme particulière

du raisonnement par induction

Comment facilement prouver une affirmation

sans la prouver dans le cas général

mais en montrant que la propriété se transmet de proche en proche.

Français: récurrence ou induction.

Anglais: induction; to apply induction to the recursion formula.

Analogies à titre d'introduction

1. Sachant qu'un domino tombant fait tomber le suivant;

2. Si je pousse le premier domino:

Alors, tous les dominos tombent.

1. Si on sait monter d'une marche à la suivante;

2. Et mettre le pied sur une marche:

Alors, on sait monter tout l’escalier.

Voir Brève de maths n°1

Approche comparée
Escalier	Formule de récurrence
Soit un robot qui doit monter un escalier de N marches.	Soit à trouver la somme de N entiers (par exemple).
Je dispose du robot : il bouge les pieds alternativement.	On me donne une formule : ½ N (N+1)
On me dit qu’il sait monter l’escalier.	On me dit qu’elle permet de calculer rapidement la somme des entiers.
Il me faut le tester et être sûr qu’il monte toutes les marches.	Il me faut démontrer que cette formule fonctionne pour toute les valeurs de N
Je m’y prends de la manière suivante.	Je procède en deux temps.
1) – Je vérifie que,	1) – Je vérifie que,
Supposant le robot sur une marche quelconque,	Supposant la formule vraie pour N,
Le mouvement des pieds correspond bien à l’action de gravir une marche	Elle est alors vraie pour N + 1 Voir démonstration
2) – Je teste que	2) – Je teste que
En posant le robot sur une des marches, c’est bon.	La formule est bonne dans UN cas.
3) En résumé
Si le robot sait monter d’une marche à l'autre.	Si je sais passer du calcul de N à N+1.
En le posant sur une marche.	En connaissant une valeur de la formule.
Il sait monter tout l’escalier.	La formule est vraie dans tous les cas.

Somme des nombres entiers
1) – Je vérifie que,	1) – Je vérifie que,
Supposant la formule vraie pour N,	On suppose que la somme des entiers jusqu’à N est Tn = ½ N (N+1) C’est notre formule de récurrence pour N On a noté la somme T, car il s'agit en fait du calcul des nombres triangulaires
Elle est alors vraie pour N + 1	La somme des entiers jusqu’à N+1 est égale à la somme jusqu’à N, à laquelle on ajoute N+1. Tn+1 = Tn + N+1
Développons cette relation	Tn+1 = ½ N (N+1) + N+1 Tn+1 = ½ (N² +N + 2N+2) Tn+1 = ½ (N +1) (N + 2)
	Or c’est justement la formule de récurrence pour N+1 Formule initiale dans laquelle n devient n+1
2) – Je teste que	2) – Je teste que
La formule est bonne dans UN cas	Prenons N = 1, alors S1 = 1 On vérifie que T1 = ½ x 1 x (1+1) T1 = 1 C’est bon
3) En résumé
Si je sais passer du calcul de N à N+1	La formule reste vraie pour N+1, si je suppose qu’elle est vraie pour N.
En connaissant une valeur de la formule.	La formule est vraie pour N = 1.
La formule est vraie dans tous les cas.	Elle sera vraie pour 1 + 1 = 2, Et ensuite pour 2 + 1 = 3 Etc. pour tous les nombres jusqu’à l’infini.

Voir Somme des entiers, carrés cubes … Démonstration par récurrence

FORMALISATION
RAISONNEMENT par INDUCTION	MATHEMATICAL INDUCTION
Objet Soit une affirmation P(n) relative au nombre entier n. Il s'agit de prouver que cette affirmation est vraie pour tout nombre entier.	Subject Let P(n) be a statement involving the natural number n. To prove that P(n) is true for all natural numbers n, we proceed as follows:
Premier principe d'induction 1. Vérifiez que P(1) est vraie; 2. Supposez que P(k) est vraie; et 3. Dans ces conditions, démontrez que P(k+1) est vraie.	First principle of mathematical induction 1. Prove that P(1) is true; 2. Assume that P(k) is true; and 3. Using steps 1 and 2, prove that P(k+1) is true.
Second principe d'induction (forte) 1. Vérifiez que P(1) est vraie; 2. Supposez que P(k) est vraie pour 1 ≤ n ≤ k; et 3. Dans ces conditions, démontrez que P(k+1) est vraie.	Second principle of mathematical induction (strong) 1. Prove that P(1) is true; 2. Assume that P(n) is true for all 1 ≤ n ≤ k; and 3. Using steps 1 and 2, prove that P(k+1) is true.

Principe général pour aborder la démonstration de l'étape 3.

Écrivez l'expression en changeant k par k+1: m = P(k) m' = P(k+1) Dans cette nouvelle expression, isolez l'expression en k, ou une fonction de celle-ci: m' = f(m) + H Montrez que H à les propriétés requises de divisibilité, par exemple.

Exemples de démonstrations
100…01^n = ligne n du triangle de Pascal	>>>
Autres démonstrations de divisibilité	>>>
Consécutifs en division	>>>
Divisibilité par 11 de formes polynomiales	>>>
Divisibilité par 5 de formes polynomiales	>>>
Divisibilité par 8 de formes polynomiales	>>>
Entiers et formes polynomiales Inverses et formes polynomiales	>>> >>>
Factorielle moins un = un produit	>>>
La somme des cubes de trois nombres consécutifs est divisible par 9	>>>
Les deux couleurs	>>>
Montrez que 3 divise l'expression suivante m = n (2n² + 7)	>>>
Montrez que 24 divise l'expression suivante m = 2 . 7^n + 3 . 5^n – 5	>>>
Nombre de Fermat – Unité en 7	>>>
Nombre de Fermat = produit des précédents + 2	>>>
Paires divisibles dans un ensemble de nombres	>>>
Pesée avec des 4 et des 7	>>>
Puissance de 2 et 2n (simple) / idem avec cubes	>>>
Quantité de partitions	>>>
Somme des entiers, carrés, cubes …	>>>
Somme des inverses des proniques	>>>
Tour de Hanoï	>>>

Voir d'autres démonstrations faciles en	Théorie des nombres pour débutants
Retour	Types de démonstrations dont récurrence
Voir aussi	Bon ordre Boucle infernale Calcul mental Construction des entiers naturels Divisibilité par 6 de n^3 - n Divisibilité par 7 Divisibilités diverses Géométrie – Index Inventaire des outils mathématiques Méthode de Newton Récursivité Somme des cubes des entiers Somme des entiers, carrés, cubes … Somme des puissances de 2 Suite de Fibonacci Suite itératives Théorie des nombres
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Recurren.htm