$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Raisonnement par récurrence

  Comment faire pour grimper en haut d'une échelle? Il suffit de savoir remplir deux conditions : atteindre le premier barreau, et être capable de passer d'un barreau au barreau suivant.

  Le raisonnement par récurrence, ou par induction, c'est exactement la même chose! Si on souhaite démontrer une propriété Pn dépendant de l'entier n, il suffit de :
  • initialiser : prouver que la propriété P0 est vraie (ou P1,... si la propriété ne commence qu'au rang 1).
  • hériter : prouver que si Pn est vraie, alors Pn+1 est vraie.
Dans ce cas, Pn est vraie pour chaque entier n. Donnons un exemple. Soit Sn=1+...+n la somme des n premiers entiers. Prouvons qu'elle vaut n(n+1)/2. On a en effet S1=1=1×(1+1)/2. Supposons maintenant que Sn=n(n+1)/2 (ie supposons que la propriété est vraie au rang n). Il faut montrer que la propriété est vraie au rang n+1, c'est-à-dire que Sn+1=(n+1)(n+1+1)/2. Mais en effet, Sn+1=n(n+1)/2+n+1=(n+1)(n/2+1)=(n+1)(n+2)/2.

Il ne faut pas oublier l'initialisation! On peut prouver que la propriété Pn : "3 divise 4n+1" est héréditaire.... mais toujours fausse!

  Il existe toute une variété de raisonnement par récurrence :

  • les récurrences doubles : on procère 2 par 2, c'est-à-dire que l'on prouve que P0 et P1 sont vraies, et on suppose que Pn, Pn+1 sont vraies pour prouver que Pn+1 et Pn+2 sont vraie.
  • les récurrences descendantes : on prouve qu'à un certain rang k, Pk est vraie, et on montrerque si Pn est vraie, alors Pn-1 est vraie. Alors les propriétés P0,...,Pk sont vraies!
C'est à Pascal quel'on doit la première utilisation du raisonnement par récurrence, dans le Traité du triangle arithmétique. Ses correspondances permettent même de dater la découverte avec précision, entre le 29 juillet et le 29 aout 1654. Pour Poincaré, le raisonnement par induction est LE raisonnement mathématique par excellence. A l'opposé de la vision intuitionniste de Poincaré, il est parfois possible de faire des raisonnement par récurrence (ou tout comme...) dans des ensembles non dénombrables, en utilisant le lemme de Zorn.