Les démonstrations par récurrence

Le raisonnement par récurrence (avec deux r s'il vous plait) est une méthode de démonstration d'une conjecture, c'est à dire d'une supposition. Une fois la récurrence terminée et la conjecture prouvée, elle deviendra une assertion vraie (sachant qu'une assertion peut-être vraie ou fausse mais pas les deux, c'est le principe dit du "tiers-exclu". Toutefois, les différentes définitions des termes de logique mathématique peuvent parfois différer légèrement et sont sujettes à débat.

Le "tiers-exclu" en logique mathématique correspond à la disjonction des propositions p / non p. En clair, sur les deux propositions, l'une des deux est forcément vraie (si p est vraie, alors p est vraie et si p est fausse, non p est vraie...)

Si la proposition est vraie à un certain point fixe (ex: n=1) et, sachant qu'elle est vraie pour un n quelconque elle est aussi vraie pour le n suivant, alors la proposition est vraie pour tous les n plus grand que le point fixe d'initialisation.

Une analogie communément usitée est celle de l'escalier infini. Il existe une première marche (si si, tous les escaliers ont une première marche) et si je prend une marche quelconque de mon escalier, j'en trouverais une après (on suppose que l'escalier est infini).

Une démonstration par récurrence se fait en trois étapes : l'initialisation, l'hérédité et la conclusion. Le principe d'une récurrence est le suivant :

L'initialisation :

Vérifions que la proposition P(n) est vraie pour un entier n fixé.
 ...
Sachant que (par exemple) P(0) est vraie, alors la proposition est initialisée.

L'hérédité :

Supposons que la propriété P(n) est vraie pour un certain entier n et vérifions que la propriété P(n+1) est aussi vraie.

L'astuce ici consiste à partir de P(n+1) - cela ne marche pas forcément dans tous les cas - puis de reconnaitre dans une partie de l'expression de P(n+1) l'expression de P(n). On procède par égalité ou par équivalence.

Conclusion :

Sachant que la propriété P(n) est vraie pour un entier n fixé, héréditaire depuis ce rang, alors P(n) est vraie pour tout n.


Clément
Fondateur du blog Point Carré et philognoseur. Écrit sur des sujets variés, essentiellement pour ses études et parfois juste par plaisir !

Articles populaires

Les sommes : la sommation par paquets

Le principe de la sommation par paquet est de séparer une somme initiale en une somme de sommes (je sais, c'est bizarre !). Par exemple, on peut séparer une somme banale avec d'un côté les nombres pairs et de l'autre les nombres impairs. Cela peut-être d'une aide bienvenue en trigonométrie ou avec $(-1)^k$. Exemple : $$\sum_{k=0}^{2n} k = \sum_{\lceil{k=\frac{0}{2}}\rceil}^{\lfloor{\frac{2n}{2}}\rfloor} 2k + \sum_{\lceil{k=\frac{0}{2}}\rceil}^{\lfloor{\frac{2n-1}{2}}\rfloor} 2k + 1 = \sum_{k=0}^{n} 2k + \sum_{k=0}^{n-1} 2k + 1$$ Le processus pas à pas : Je commence par construire le membre des nombres impairs en soustrayant -1 à droite (j'ajoute donc +1 à gauche). $$\sum_{k=-1}^{2n-1} k + 1$$ Puis, je remplace k par 2k, et donc je divise -1 et 2n par 2. $$\sum_{k=\frac{-1}{2}}^{\frac{2n-1}{2}} 2k + 1$$ Et je termine par les arrondis supérieurs et inférieurs : $$\sum_{k=\lceil{\frac{-1}{2}}\rceil}^{\lfloor{\frac{2n-1}{2}}\rfloor} 2k + 1$$ Je pa
Continuer la lecture

Mo et Mb, différences et conséquences

Image
Vous avez probablement déjà remarqué que l'on parlait tantôt de MégaBits (Mb) et tant ôt de MégaOctet (Mo). Pourquoi cette différence et quelles sont les conséquences pour nous, usager d'internet ? Il suffit pour cela de comprendre la différence entre Byte et Bit. En effet, Mb = Mégabit et MB = Mégabyte. Un bit est la plus petite unité du système informatique (celle qui prend alternativement la valeur 0 ou 1 - le ou est important car dans les ordinateurs quantique, il se transforme en et mais c'est une autre histoire...). Une byte vaut 8 bits. Et un byte vaut également un octet. Pour faire simple, quand il y a un B majuscule, on parle de Byte et quand il y a un b minuscule on parle de bit. Par conséquent, il y a 8 fois moins de "quantité de donnée" dans un Mo que dans un Mb. Or, les Mb sont utilisés pour définir le débit internet. Ainsi, la vitesse maximum d'une carte réseau "standard" (id est équipant la majorité des terminaux
Continuer la lecture